Linked List

From Algorithmist
Jump to: navigation, search

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.

Example[edit]

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);
}

Variations[edit]

Circular Lists[edit]

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 start
        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.

Doubly Linked Lists[edit]

One of the problems with a linked list is that it can be 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

References[edit]

  • 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".