Linked List
From Algorithmist
A list implemented by each item (called a node) linking to the next item. It is one of the fundamental data structures (other examples are arrays and trees). The head of a linked list is its first node. Borrowing C's syntax, we can refer to the next node after the head (i.e. the second node) as head->next, the third node as head->next->next, and so on. The final node of a list traditionally points to null (usually equivalent to zero) which is an address that can never house a list node.
Advantages linked lists have over arrays include O(1) insertion and removal, but at the cost of slower random access time, O(n). Sometimes a program needs only to access a list sequentially: the perfect place to use a linked list. Furthermore, you need not allocate all the memory required for a linked list at once like you do for an array.
By far the most common type of linked list is the singly linked list, which this article describes, though variations do exist, each with their own advantages and disadvantages. Some of the popular variations are described below.
Contents |
[edit] Example
Here's are a few example declarations and functions in C of a linked list that keeps track of players in a game. The unusual struct declaration is a result of the self-referential nature of linked lists. Note that, outside of the struct, the list nodes are referred to as "player" but inside, they are "player_node".
typedef struct player_node
{
struct player_node* next; /* Link to the next player */
char name[20];
int level;
} player;
player* head = NULL; /* Link to the first player, who is currently nonexistent */
void add_player(player* newplayer)
{
/* Sometimes we don't care about the order of a list -- this makes insertion very easy. */
newplayer->next = head;
head = newplayer;
}
void send_message_to_all_players(char* message)
{
player* p;
/*
* The following line of code is a convenient way to traverse a linked list
* but don't attempt to change the list infrastructure (i.e. add or remove
* items) while this loop is active, which could be disastrous.
*/
for (p = head; p != NULL; p = p->next)
send_message_to_one_player(p, message);
}
[edit] Variations
[edit] Circular Lists
Normally the last node in a linked list points to null. The tail node of a circularly linked list points to the head node. The advantage this offers is that, given any node, you can traverse the entire linked list. (Normally, you can access only items that follow a given node.) When you revisit the given node, you know you've traversed the entire list. This of course means the list head is less important. The disadvantage is that it is slightly more complicated to add an item to a list. Circular list insertion is made easier by adding the item after the head, as opposed to before it (as in a stack). The item is inserted between head and head->next. The following function should illustrate this point.
function add_node_circular(head, node)
if head is null
head = node
node->next = node
else if head->next is null
node->next = head
head->next = node
else
node->next = head->next
head->next = node
end function
The programmer of a circular list must be extra vigilant about segfaults. If the error checking in the pseudocode above was absent, the program would segfault when trying to add a node to a zero- or one-element list.
[edit] Doubly Linked Lists
One of the problems with a linked list is that it can difficult to remove an arbitrary node without traversing the list. This is because you have to find the element in the list that directly precedes it so you can change its next pointer. The singly-linked-list node removal operation might be coded as follows.
function remove_node_singly(head, node)
tempnode = head
while (tempnode->next != node)
tempnode = tempnode->next
tempnode->next = node->next
end function
With a doubly linked list, every node stores both a pointer to the next node and a pointer to the previous node. This makes the removal of an arbitrary node O(1) instead of the usual O(n), at the cost of having to use twice as much memory for list infrastructure. The doubly-linked-list node removal operation might be coded as follows.
function remove_node_doubly(node)
node->prev->next = node->next
node->next->prev = node->prev
end function
[edit] References
- Donald Knuth. "The Art of Computer Programming", Volume 1: "Fundamental Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3: "Linked Allocation", 2.2.4: Circular Lists, and 2.2.5: "Doubly Linked Lists".
