| contact us | ||||
| articles | e-books | software | services | |
A linked list is a flexible abstract data structure or collection that is useful for relatively short lists where items are frequently added and removed from the list. Items within the list are connected using links, references, or pointers. Because of today's modern programming libraries such as the C++ standard template library (STL) and Java's 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 and kernel developers.
If asked, 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 nor shown the correct way to write one. Computer programmers are almost 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 code like this.
typedef struct slnode {
struct slnode *next;
int which;
/* Other data here. */
} SinglyLinkedNode;
typedef struct sllist {
SinglyLinkedNode *head, *tail;
} SinglyLinkedList;
/* Initializes a linked list to be empty. */
void initializeList(SinglyLinkedList *list) {
list->head = list->tail = NULL;
}
/* Creates and initializes a linked list. */
SinglyLinkedList *createList(void) {
SinglyLinkedList *list = malloc(sizeof(SinglyLinkedList));
initializeList(list);
return list;
}
/* Inserts a node at the beginning of this list. */
void insertNode(SinglyLinkedList *list, SinglyLinkedNode *node) {
node->next = list->head;
list->head = node;
if (list->tail == NULL)
list->tail = node;
}
/* Adds a node at the end of this list. */
void appendNode(SinglyLinkedList *list, SinglyLinkedNode *node) {
if (list->head == NULL) {
list->head = list->tail = node;
}
else {
list->tail->next = node;
node->next = NULL;
}
}
/* Removes a node from this list. */
void removeNode(SinglyLinkedList *list, SinglyLinkedNode *node) {
if (list->head == node) {
/* The node to be removed is at the beginning
* of the list. Remove the node. */
list->head = node->next;
if (list->tail == node)
list->tail = NULL;
node->next = NULL;
}
else {
/* Traverse the list to find the node that
* comes before the one to be removed. */
SinglyLinkedNode *prev = list->head;
while (prev != NULL) {
if (prev->next == node)
break;
prev = prev->next;
}
/* Remove node. */
if (prev != NULL) {
prev->next = node->next;
if (list->tail == node)
list->tail = prev;
node->next = NULL;
}
}
}
Notice the complexity of the insert, append, and remove functions (especially the remove function). Because we have taken a node centric approach when writing this linked list, we must write if statements to handle special cases such as when the node to be removed is at the beginning of the list or when the list has only one element in it. 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 above code is correct.
The correct way to write a 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 and executes faster than node centric code.
typedef struct slnode {
struct slnode *next;
int which;
/* Other data here. */
} SinglyLinkedNode;
typedef struct sllist {
SinglyLinkedNode *head, **tailp;
} SinglyLinkedList;
/* Initializes a linked list to be empty. */
void initializeList(SinglyLinkedList *list) {
list->head = NULL;
list->tailp = &list->head;
}
/* Creates and initializes a linked list. */
SinglyLinkedList *createList(void) {
SinglyLinkedList *list = malloc(sizeof(SinglyLinkedList));
initializeList(list);
return list;
}
/* Inserts a node at the beginning of this list. */
void insertNode(SinglyLinkedList *list, SinglyLinkedNode *node) {
node->next = list->head;
list->head = node;
if (list->tailp == &list->head)
list->tailp = &node->next;
}
/* Adds a node at the end of this list. */
void appendNode(SinglyLinkedList *list, SinglyLinkedNode *node) {
*list->tailp = node;
list->tailp = &node->next;
}
/* Removes a node from this list. */
void removeNode(SinglyLinkedList *list, SinglyLinkedNode *node) {
/* Traverse the list to find the next pointer of the
* node that comes before the one to be removed. */
SinglyLinkedNode *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 append and remove functions are much less complex when using a pointer centric approach (2nd example). You may be thinking, "The node centric approach (1st example) would not be so complex if you used a doubly linked list or a circular list or if you used C++." Try it. No matter what you try, if you need to implement a linked list and you need to write code to find elements in the list or remove elements from the list, the pointer centric approach (2nd example) 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
void dumpList(SinglyLinkedList *list) {
SinglyLinkedNode *curr = list->head;
while (curr != NULL) {
printf("%d ", curr->which);
curr = curr->next;
}
printf("\n");
}
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);
dumpList(list);
insertNode(list, node1);
dumpList(list);
removeNode(list, node1);
dumpList(list);
appendNode(list, node3);
dumpList(list);
insertNode(list, node2);
insertNode(list, node1);
appendNode(list, node4);
dumpList(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.