Misplaced Pages

This is an old revision of this page, as edited by Kenny Moens (talk | contribs) at 10:08, 2 December 2003 (Scheme). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a linked list is one of the simplest data structures used in computer programming. It consists of a number of nodes, each containing one element and one (or more) links to other nodes. Linked lists permit insertion and removal of nodes at any point in the list in O(1) time, and a list can be traversed in order in O(n) time, where n is the size of the lists. Random access on linked lists, however, also requires O(n) time. Arrays have the opposite tradeoff.

Types of 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. This kind of list allows sequential access to elements only in one direction (from front to back).

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. This allows sequential access to the list in both directions. A curious space-saving implementation of doubly linked lists is Xor linked lists.

There are two significant variations to the types mentioned above. First is a circularly linked list, where the first and last nodes are linked together. This can be done for both singly and doubly linked lists. The other variation is the addition of a sentinel node at the beginning of the list. This node represents before the first node and/or after the last node of the list. It also makes it possible to have an empty list.

A type of linked list with performance similar to a binary tree is the skip list, which adds extra pointers that move along the list in large increments. These links facilitate faster (O(log n)) random access. Maintaining these links comes at a price, however: insertion and removal are slowed.

Programming Language Support

Many programming languages, such as LISP and Scheme have linked lists built in. In other languages it is simple to create the data structure using pointers or references to implement links between list nodes. For example, in C:

typedef struct Person
{
    struct Person **prev; // <--- previous person in list
    struct Person *next; // <--- next person in list
    char name;
    int age;
};

An example of code that uses this structure:

Person first; // first item in the linked list
Person *p = &first;

while(!feof(stdin)) // there's still input
{
    p->next = (Person *)malloc(sizeof(Person));   // first link
    p = p->next;
    printf("Enter name and age:\n");              // Ask for input
    scanf("%s %d", &(p->name), &(p->age));        // Use it
}

Linked Lists On The Web

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

• Introduction to Linked Lists
• Linked List Problems