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.
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 when writing code to add, find, and remove elements from a linked list, resulting in C code for a non-circular singly linked list like this.
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). Because we have taken a node centric approach when writing this linked list, we must write if statements to handle two special cases: when the list is empty and 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.
The correct way to write a singly linked list is to visualize the list in a pointer centric way, focusing on the links (pointers) between the nodes. Pointer centric thinking results in code that uses the address of the head pointer and next pointers. Such code requires less special case handling, is easier to test because it has less paths through the code, and executes slightly faster than node centric code. Each line that differs from the previous example is highlighted in bold font.
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 a pointer centric approach (example 2). You may be thinking, “The node centric approach (example 1) would not 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, the pointer centric approach (example 2) will always be less complex.
Here is some additional C code that you can use to test both the node centric and pointer centric linked list code. Simply combine in a single file this test code with the code from one of the examples above, then compile and run the program. I used gcc with these two commands to compile my tests.
gcc -W -Wall -Wstrict-prototypes -ansi -O -o nodeCentric nodeCentric.c
gcc -W -Wall -Wstrict-prototypes -ansi -O -o pointerCentric pointerCentric.c
/* 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;
}
Maia L.L.C. and its employees have used their best efforts in preparing this article. These efforts include the development, research, and testing of the theories and computer programs in this article to determine their correctness. Maia L.L.C. makes no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this article. Maia L.L.C. shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.