Linked list

Table of contents

1 Variants 1.1 Singly linked lists 1.2 Doubly-linked list 1.3 Circular lists 1.4 Sentinel nodes 2 Applications of linked lists 3 Tradeoffs 3.5 Linked lists vs. arrays 3.6 Double-linking vs. single-linking 3.7 Circular lists 3.8 Sentinel nodes 4 Linked List Operations 4.9 Singly-linked lists 4.10 Doubly-linked lists 4.11 Circularly-linked lists 5 Language Support 6 Linked Lists On The Web

Variants

Singly linked lists

The simplest kind of linked list is a singly linked list, which has one link per node. This link points to the next node in the list, or to a null value if it is the last node.

A singly linked list containing three integer values

Doubly-linked list

A more sophisticated kind of linked list is a doubly linked list. Each node has two links, one to the previous node and one to the next.

An example of a doubly linked list.

Xor-linking is an elegant alternative to doubly-linked lists, where the two pointers fields are replaced by a single field.

Circular lists

Sentinel nodes

Applications of linked lists

The "data" field of a node can be another linked list. By this device, one can emulate arbitrary linked data structures with lists — a principle which is fundamental to the Lisp programming language, where linked lists are the primary (if not the only) data structuring mechanism.

Sometimes, linked lists are used to implement associative arrays, and are in this context called association lists. There is very little good to be said about this use of linked lists; they are easily outperformed by other data structures such as self-balancing binary search trees even on small data sets (see the discussion in associative array). However, sometimes a linked list is dynamically created out of a subset of nodes in such a tree, and used to more efficiently traverse that set.

Tradeoffs

As for most choices in computer programming and design, no method is well suited to all circumstances. A linked list data structure might work well in one case, and cause problems in another. This is a list of some of the common tradeoffs involving linked list structures.

Linked lists vs. arrays

On the other hand, compared to an array, the chief disadvantage of a linked list is that it only allows sequential access to elements, and only in one direction (from front to back). In particular, when removing or inserting an element in the middle of the list, one needs to know the address of the preceding element.

Another disadvantage of linked lists is the extra storage needed for the address fields, which often makes them impractical for lists of small data items such as characters or boolean values. Even more significant is the time cost of allocating memory separately for each new element (and, in some systems, of locating and recycling elements that cannot be reached; see garbage collection). There are a number of techniques to reduce this overhead, such as using a free list or memory pool, storing the data itself inside the nodes, and CDR coding.

Double-linking vs. single-linking

Circular lists

Sentinel nodes

Linked List Operations

When manipulating linked lists in-place, care must be taken to not use values that you have invalidated in previous assignments. This makes algorithms for inserting or deleting linked list nodes somewhat subtle. This section gives pseudocode for adding or removing nodes from singly, doubly, and circularly linked lists in-place. Throughout we will use null to refer to an end-of-list marker or sentinel, which may be implemented in a number of ways.

Singly-linked lists

Our node data structure will have two fields:

• data -- The data being stored in the node
• next -- A reference to the next node

node := head
while node not null
   

   node := node.next

insertAfter(node, newNode)
   newNode.next := node.next

   node.next    := newNode

insertBeginning(newNode)
   newNode.next := head

   head         := newNode

removeAfter(node)
   nodeBeingRemoved := node.next

   node.next := node.next.next

   destroy nodeBeingRemoved


removeBeginning(node)
   nodeBeingRemoved := head

   head := head.next

   destroy nodeBeingRemoved

Doubly-linked lists

With doubly-linked lists there are even more pointers to update, but also less information is needed, since we can use backwards pointers to observe preceding elements in the list. This enables new operations, and eliminates special-case functions. We will add a prev field to our nodes, pointing to the previous element, and a tail variable which always points to the last node in the list. Both head and tail are null for an empty list.

Iterating through a doubly linked list can be done in either direction. In fact, direction can change many times, if desired.

Forwards

node := head
while node not null
   

   node := node.next

node := tail
while node not null
   

   node := node.prev

insertAfter(node,newNode)
   newNode.prev := node

   newNode.next := node.next

   if node.next is null

       tail := newNode

   else

       node.next.prev := newNode

   node.next    := newNode


insertBefore(node,newNode)
   newNode.prev := node.prev

   newNode.next := node

   if node.prev is null

       head := newNode

   else

       node.prev.next := newNode

   node.prev    := newNode

insertBeginning(newNode)
   if head is null

       head := newNode

       tail := newNode

       newNode.prev := null

       newNode.next := null

   else

       insertBefore(head, newNode)

insertEnd(newNode)
   if tail is null

       insertBeginning(newNode)

   else

       insertAfter(tail, newNode)

remove(node)
   if node.prev is null

       head = node.next

   else

       node.prev.next = node.next

   if node.next is null

       tail := node.prev

   else

       node.next.prev = node.prev

   destroy node

A curious way of implementing doubly linked lists that uses half as much space for pointers is the xor linked list.

Circularly-linked lists

Circularly-linked lists can be either singly or doubly linked. For both, their circular versions, which link all the nodes into a continuous circle without using null, benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing head and tail, although if the list may be empty we need a special representation for the empty list, such as a head variable which points to some node in the list or is null if it's empty; we use such a head here.

This representation significantly simplifies adding and removing nodes into a non-empty list, but empty lists are a special case. Assuming that someNode is some node in the list, this code iterates through that list starting with someNode:

Forwards

node := someNode
do
   

   node := node.next

while node not someNode

Backwards

node := someNode
do
   

   node := node.prev

while node not someNode

Notice the postponing of the test to the end of the loop. This is important for the case where the list contains only the single node someNode.

This simple function inserts a node into a doubly-linked circularly linked list after a given element:

insertAfter(node, newNode)
   newNode.next := node.next

   newNode.prev := node

   node.next.prev := newNode

   node.next      := newNode

Inserting an element in a possibly empty list requires a special function:

insertBeginning(node)
   if head is null

       node.prev := node

       node.next := node

   else

       insertAfter(head.prev, node)

   head := node

Finally, removing a node must deal with the case where the list empties:

remove(node)
   if node.next is node

       head := null

   else

       node.next.prev := node.prev

       node.prev.next := node.next

   destroy node

Language Support

Many programming languages, such as Lisp and Scheme have singly linked lists built in. In other languages it is simple to create the data structure using references. For example, here is a complete example in C which adds the numbers 1 through n using a linked list:

struct node {

    int value;

    struct node *next; /* next node in list */

};

int add_up_to(int n) {

    struct node first_node; /* first item in the linked list */

    struct node *p = &first_node;

    int i, sum;

    p->next = NULL;

    /* Add the numbers 1 through n to the linked list */

    for(i=1; i <= n; i++) {

        struct node *new_node =

            (struct node *)malloc(sizeof(struct node));

        p->value = i;

        new_node->next = NULL;

        p->next = new_node;

        p = new_node;

    }

    /* Iterate through the list, summing up the values */

    sum = 0;

    for(p = &first_node; p != NULL; p = p->next) {

        sum = sum + p->value;

    }

    return sum;

}

Linked Lists On The Web

Some linked list materials are available from the Stanford Computer Science department:

• Introduction to Linked Lists
• Linked List Problems