Linked Lists


Image

A linked list is a data structure in which objects are arranged in linear order, similar to an array. However, unlike an array which uses array indices to determine the order of elements, the order of a linked list is derived from a series of pointers.

Arrays vs Linked Lists



Image

Linked lists offer some advantages over arrays. Inserting and deleting elements within a linked list can be more efficient than an array. In some programing languages arrays are immutable and because of this they can not grow in size. This can become problematic when creating programs in which you do not know the amount of data that you will need to store. Linked lists can get around this limitation by dynamically allocating storage at run time.

When should you use a linked list over an array? Linked lists excel when a large amount of insertions or deletions are required. However, arrays are far superior to linked lists whenever a large amount of random access to elements is required.

If you know the index of an element you can access it in O(1) time within an array, but linked lists generally require you to traverse the list in O(n) time in order to the find an element. In situations where storage size is an issue arrays are more compact than linked lists. Having to store a pointer to each element comes with a built in storage overhead.

Linked List Components


Node

Image

A linked list is essentially a connected series of cells or nodes, like links on a chain or beads on a necklace. Each node contains a pointer to the next node in the chain.

Image

Although it is easier to imagine a linked list as a series of contiguous elements it is important to remember that due to the nature of dynamic allocation the various elements that comprise the list are actually scattered throughout the computer’s memory. Because of this the only way to track the location of each element is through a series of pointers.

Here is an implementation of a linked list node in C:

    typedef struct node {
        int data;
        struct node *next;
    } node;

Head and Tail

Image

The head and tail are pointers to the begining and the end of the list. Unless the list is circularly linked the head will not have any predecessors and the tail will not have any successors. If the head is NULL then the list is empty. The head pointer will generally be our entry point into the list.

    node *head, *tail;

    head = (node *) malloc (sizeof(struct node));
    head->next = NULL;
    head->data = 0;

    tail = head;

Types


Singly Linked

Image

Each node within a singly linked list points to the next via a pointer. Following this chain allows you to traverse the list from beginning to end. Singly linked lists only allow you to travel in one direction. This article will primarly be about singly linked lists.

Doubly Linked

Image

Unlike a singly linked list a doubly linked list allows you to travel back and forth within the list. This is accomplished by storing two pointers within a node, one that points to the next node and another that points to the previous.

Circularly Linked

Image

In a circularly linked list the head’s previous pointer points to the tail, and the tail’s next pointer points the head. This creates a circular ring of nodes.

Methods


Search

Image

In order to find a specific element within a list we must check each node one after the other. If we find the element we can return a pointer to it, otherwise we can return NULL. Searching through a list can take O(n) time in the worst case.

    node *search(node *head, int x) {
        if (!head || !x) {
            return NULL;
        }

        node *current = head;

        while (current) {
            if (current->data == x) {
                return current;
            }

            current = current->next;
        }

        return NULL;
    }

Insert

Image

Before we can insert a node into a linked list you must decide if your implementation will allow duplicates. Perhaps you prefer not to have duplicates because you are implementing a dictionary. If you decide that you will not allow duplicates then you must first search to see if the node you wish to add does not already exist, if it does then you do nothing.

Otherwise you can simply add the new node after the head, or at the end of the list of you prefer. Keep in mind that although adding duplicates will make insertion easier, deleting elements will always require you to completely traverse the list in order to find all the duplicates.

To add a node after the head you will need to set the head’s next pointer to the node you wish to insert, and set the inserted node’s next pointer to the node that used to be after the head. To add it to the end of the list you must set the tail’s next pointer the node you wish to insert, and set the inserted node’s next pointer to NULL.

The following example simply inserts the element at the front of the list.

    bool insert(int x, node **head) {
        if (!x || !head) {
            return false;
        }

        node *new = (node *) malloc(sizeof (node));
        if (!new) {
            return false;
        }

        new->data = x;
        new->next = *head;

        *head = new;

        return true;
    }

Delete

Image

To delete a node from the list we must disconnect it from the chain. As we traverse the list we need to store a reference to the current node (A). If the next node (B) matches the node we wish to delete then we must set A’s next pointer to the node after B.

If the node to be removed is the head then the next node after the head will take its place. Conversely if the node to be removed is the tail then the new tail’s next pointer should be set to NULL.

    bool delete(node **head, node *toDelete, node **tail) {
        if (!head || !*head || !toDelete) {
            return false;
        }

        if (toDelete == *head) {
            *head = (*head)->next;
            free(toDelete);
            return true;
        }

        node *current = *head,
             *previous;


        while (current) {
            if (current == toDelete) {

                if (!current->next) {
                    previous->next = NULL;
                    *tail = previous;
                } else {
                    previous->next = current->next;
                }

                free(toDelete);
                return true;
            }

            previous = current;
            current = current->next;
        }

        return false;
    }

Source Code


Download Source

Resources


  • Foundations of Computer Science: C Edition - Alfred V. Aho and Jeffery D. Ullman
  • Introduction to Algorithms: Second Edition - Thomas H. Corman, Charles E Leiserson, Ronald L. Rivest, Clifford Stien
  • Mastering Algorithms with C - Kyle Loudon

comments powered by Disqus