An Elegant and Efficient Linked List Implementation

A linked list is a flexible abstract data structure that is useful for relatively short lists where items are frequently added and removed from the list. Items within the list are connected using pointers or references. Because of today’s modern programming libraries such as the C++ standard template library (STL) and the Java collections found in the package java.util, few programmers need to write a linked list. However, there are still some programmers that are required to write them, most notably students, library developers, and kernel developers.

Inefficient Single Pointer Iteration

Most programmers would consider writing a linked list, singly or doubly linked, circular or non-circular, as trivial. Unfortunately, almost all programmers write linked lists inefficiently and incorrectly because they have never been taught the correct way to write one. Computer programmers are almost always taught to visualize a linked list in a node centric way. They are taught to focus on the nodes and to use single pointer iteration. This results in C code for a non-circular singly linked list similar to the code in example 1.

/* Example 1 */

typedef struct slnode {
    struct slnode *next;
    /* Programmer defined data goes here. */
    int which;
} LinkedNode;


typedef struct sllist {
    LinkedNode *head, *tail;
} LinkedList;


/* Creates and initializes a linked list. */
LinkedList *createList(void) {
    LinkedList *list = malloc(sizeof(*list));
    list->head = list->tail = NULL;
    return list;
}


/* Inserts a node at the beginning of this list. */
void insertNode(LinkedList *list, LinkedNode *node) {
    node->next = list->head;
    list->head = node;
    if (list->tail == NULL) {
        list->tail = node;
    }
}


/* Appends a node at the end of this list. */
void appendNode(LinkedList *list, LinkedNode *node) {
    if (listIsEmpty(list)) {
        list->head = list->tail = node;
    }
    else {
        list->tail->next = node;
        list->tail = node;
    }
    node->next = NULL;
}


/* Removes a node from this list. */
void removeNode(LinkedList *list, LinkedNode *node) {
    LinkedNode *prev = list->head;
    if (prev == node) {
        /* The node to be removed is at the beginning
         * of the list.  Remove the node. */
        removeFirst(list);
    }
    else {
        /* Traverse the list to find the node that
         * comes before the one to be removed. */
        LinkedNode *prev = list->head;
        while (prev != NULL) {
            if (prev->next == node) {
                /* We found the node, so remove it. */
                LinkedNode *next = node->next;
                prev->next = next;
                if (next == NULL) {
                    /* We are removing the node at the end
                     * of the list, so change the tail. */
                    list->tail = prev;
                }
                node->next = NULL;
                break;
            }
            prev = prev->next;
        }
    }
}

Notice the complexity of the appendNode and removeNode functions (especially the removeNode function which even includes a call to the removeFirst function). The code is complex because when writing the code, the author focused on the nodes and used single pointers (for example: LinkNode *next;) to iterate through the list. Because the author used single pointers, the author had to write if statements to handle two special cases: 1) when the list is empty and 2) when the node to be removed is at the beginning of the list. The complexity of this code, especially the remove function makes it difficult to code correctly and to test completely. In fact, I’m not 100% sure that the preceding code is correct.

Elegant and Time Efficient Double Pointer Iteration

The correct way to write a singly linked list is to visualize the list in a pointer centric way, focusing on the pointers (links) between the nodes. Pointer centric thinking results in code that uses the address of pointers or in other words double pointers (for example: LinkedNode **pnp;). Such code requires less special case handling, is easier to test because it has fewer paths through the code, and executes slightly faster than single pointer iteration. Example 2 contains an implementation of a singly linked list that uses double pointer iteration. Each line in example 2 that differs from the code in example 1 is highlighted in bold font.

/* Example 2 */

typedef struct slnode {
    struct slnode *next;
    /* Programmer defined data goes here. */
    int which;
} LinkedNode;


typedef struct sllist {
    LinkedNode *head, **tailp;
} LinkedList;


/* Creates and initializes a linked list. */
LinkedList *createList(void) {
    LinkedList *list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tailp = &list->head;
    return list;
}


/* Inserts a node at the beginning of this list. */
void insertNode(LinkedList *list, LinkedNode *node) {
    node->next = list->head;
    list->head = node;
    if (list->tailp == &list->head) {
        list->tailp = &node->next;
    }
}


/* Appends a node at the end of this list. */
void appendNode(LinkedList *list, LinkedNode *node) {
    *list->tailp = node;
    list->tailp = &node->next;
    node->next = NULL;
}


/* Removes a node from this list. */
void removeNode(LinkedList *list, LinkedNode *node) {
    /* Traverse the list to find the next pointer of the
     * node that comes before the one to be removed. */
    LinkedNode *curr, **pnp = &list->head;
    while ((curr = *pnp) != NULL) {
        if (curr == node) {
            /* We found the node, so remove it. */
            *pnp = node->next;
            if (list->tailp == &node->next) {
                list->tailp = pnp;
            }
            node->next = NULL;
            break;
        }
        pnp = &curr->next;
    }
}

Notice that the appendNode and removeNode functions are much less complex when using double pointer iteration (example 2). You may be thinking, “The single pointer iteration (example 1) wouldn’t be so complex if you used a circular list or if you wrote it in C++ instead of C.” Try it. No matter what you try, if you need to implement a singly linked list and you need to write code to append elements to a list or remove elements from a list, double pointer iteration (example 2) will always be less complex.

Example 3 contains additional C code that you can use to test both examples 1 and 2. Simply combine the code in example 3 with the code from example 1 or example 2 in a single file. Save the combined file. Then compile the combined file and run the program. I used gcc with these two commands to compile my tests.

gcc -W -Wall -Wstrict-prototypes -ansi -O -o singlePointer singlePointer.c
gcc -W -Wall -Wstrict-prototypes -ansi -O -o doublePointer doublePointer.c

/* Example 3 */

/* Prints the contents of a list. */
void printList(SinglyLinkedList *list) {
    SinglyLinkedNode *curr = list->head;
    while (curr != NULL) {
        printf("%d ", curr->which);
        curr = curr->next;
    }
    printf("\n");
}


/* Creates and returns a node. */
SinglyLinkedNode *createNode(int which) {
    SinglyLinkedNode *node = malloc(sizeof(SinglyLinkedNode));
    node->next = NULL;
    node->which = which;
    return node;
}


int main(void) {
    SinglyLinkedList *list = createList();
    SinglyLinkedNode *node1 = createNode(1);
    SinglyLinkedNode *node2 = createNode(2);
    SinglyLinkedNode *node3 = createNode(3);
    SinglyLinkedNode *node4 = createNode(4);
    printList(list);
    insertNode(list, node1);
    printList(list);
    removeNode(list, node1);
    printList(list);

    appendNode(list, node3);
    printList(list);

    insertNode(list, node2);
    insertNode(list, node1);
    appendNode(list, node4);
    printList(list);

    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(list);
    return 0;
}

An Elegant and Efficient Linked List Implementation

Inefficient Single Pointer Iteration

Elegant and Time Efficient Double Pointer Iteration

Further Reading