Linked List: Advanced Implementation (Doubly Linked Lists)
With a doubly linked list, each node has two pointers: (a) a "next" pointer that connects it with the next node in the list and (b) a "prev" pointer that connects it with the previous node in the list. A doubly linked list also has two main pointers, a head and a tail. The head points to the first node of the list and the tail points to the last node of the list. We interchangeably refer to an element of a linked list as a node.
The following figure illustrates the usefulness of the next and prev pointers; the next pointer allows us to navigate from the head to the tail. The prev pointer allows us to navigate from the tail to the head. Together, they provide a bi-directional traversal. For the tail node, the next field points to a NULL since there is no node after that. Likewise, for the head node, the prev field points to a NULL since there is no node before that.
Figure: A Doubly Linked List
Each element of a doubly linked list is represented by a data structure. As per the above figure, the structure contains both next and prev pointers. The structure also has a member "value" that stores "void *" values and thus, allows us to store any opaque application data. As per
typedef struct doublylinkedlist_node {
struct doublylinkedlist_node *next;
struct doublylinkedlist_node *prev;
void *value;
} doublylinkedlist_node_t;
Note that the compiler would not complain that we define both the next and prev as pointers to the struct doublylinkedlist_node. This works because the storage of a pointer is fixed and the compiler allocates that much storage for it. However, if we were to keep the full structure as variable inside the structure (e.g. "struct doublylinkedlist_node next" followed by "struct doublylinkedlist_node prev"), then the compiler would not like it and complain that the next and the prev fields are incomplete types!
Basic Operations
Doubly Linked lists allow us to store data on a dynamic basis and do useful things with it. For that purpose, doubly linked lists support a range of useful operations; these operations are similar to that of a singly linked list. Some of these operations are traversing elements of the list, inserting nodes into the list, searching for a given element in the list, and deleting an existing element from the list.
Traversing the list
Traversing a linked list is a fairly straightforward task. We can traverse a doubly linked list in two ways. First, we can start at the head node and then traverse the nodes in the forward direction. Alternatively, we can start at the tail and then traverse the nodes in the reverse direction. Most of the linked list operations do involve traversal. For example, if we are searching for a specific node, then we need to traverse the list, till we find the node that we are looking for. Same logic applies when we are trying to delete a specific node.
Searching a node
Searching a node is a good example of node traversal in a linked list. The steps involve a while loop to walk the linked list, starting from the head (or the tail) and as we do the walk, we compare each node with the passed value.
One side note. Since lookups involve traversal, their time complexity becomes O(n). So, if your system spends most of its time in lookup operations and if you dealing with a large number of elements, then you should also consider alternative data-structures like a hash table or a balanced binary tree. A hash-table usually takes O(1) average time for a lookup, but the worst-case time-complexity is same as that of arrays (O(n). A balanced binary tree takes O(logn) for a lookup.
Inserting a node
Inserting a node in a list is simply a matter of allocating the new node and adding it at the end of the tail. To do that, we need to manipulate a handful of pointers. This involves updating the pointers (both next and previous) of neighboring nodes such that the new node becomes a new link in the list. Of course, there is one corner case. When we add a node, and if it is the first node of the list, then we should make both head and tail of the list point to this new node.
We illustrate inserting a node for a doubly linked list using the figure provided below. The following figure shows a list consisting of four nodes with values of 680, 880, and 280. Next, we add a new element with value 780.
Figure: Inserting into a Doubly Linked List
Deleting an element
Like insertion, when we delete a node, then we need to update both next and prev pointers of the neighboring nodes of the node being deleted. With deletion, we should also free the memory allocated for the node.
The following figure illustrates deletion of the node with value 880. For this, we simply make the next pointer of the node before 880 (which has value 680), point to the node after 880 (which has value 280). In addition, we make the prev pointer of the node with value 280, point to of the node with value 680.
Figure: Deleting a node from a Doubly Linked List
When deleting, we have to take into account that if the node being deleted is the head/tail itself; if so, then it updates the doublylinkedlist_head/doublylinkedlist_tail accordingly.
Advanced Implementation
Now that we are done with the introduction, let us get cracking and implement various pieces of a doubly linked list. Our implementation comes into the form of three files: (a) a header file that publishes the data-structure and APIs, (b) a C file that has the implementation of all the APIs that are published in the above header file, and (c) another C file that contains the main() function, which calls various linkedlist APIs. BTW, if you would like to see a simpler implementation for doubly-linked list, then we recommend that you start here: Simple Implementation of Doubly Linked Lists.
Let us start with our header file. This file (provided below) begins with the definition of the doublylinkedlist_node_t structure. As illustrated earlier, the structure has both next and prev pointers. Next, the header file adds another structure (doublylinkedlist_t) that is used for encapsulating the head and the tail pointers. In addition, the structure also adds a comparison callback function. We need applications to provide this function since applications can provide their own data type and the core implementation does not get to see what is inside the "void *". Therefore, the implementation really does not know how to compare two values. Keeping this with the application allows us to provide a more flexible implementation.
The header file also publishes a bunch of APIs. We provide their summary below.
doublylinkedlist_init(): Initializes the global variables for linked list doublylinkedlist_free(): Frees the entire linked list doublylinkedlist_insert(): Add a new element in the linked list doublylinkedlist_delete(): Deletes an element from the linked list doublylinkedlist_search(): Searches the linked list and if found, returns the element
These above APIs accept a pointer to a doublylinkedlist_t structure, since it is this structure that now holds the head and the tail pointers. Since each application of this doubly-linked list can now define and pass their own doublylinkedlist_t pointer, this means that we can reuse the same code for many applications.
With that, we provide below the header file ("doublylinkedlist.h").
#include <stdio.h>
#include <stdlib.h>
#ifndef __DOUBLYLINKEDLIST_H__
#define __DOUBLYLINKEDLIST_H__
/* Node in the Doubly-Linkedlist */
typedef struct doublylinkedlist_node {
struct doublylinkedlist_node *next;
struct doublylinkedlist_node *prev;
void *value;
} doublylinkedlist_node_t;
/* Representation of the Doubly-Linkedlist */
typedef struct doublylinkedlist_ {
struct doublylinkedlist_node *head;
struct doublylinkedlist_node *tail;
int (*compare_func)(const void *, const void *);
} doublylinkedlist_t;
int doublylinkedlist_init(doublylinkedlist_t *doublylinkedlist,
int (*compareFunc)(const void *, const void *));
int doublylinkedlist_free(doublylinkedlist_t *doublylinkedlist);
doublylinkedlist_node_t *doublylinkedlist_search(
doublylinkedlist_t *doublylinkedlist,
void *search_value);
int doublylinkedlist_insert(doublylinkedlist_t *doublylinkedlist, void *value);
void doublylinkedlist_delete(doublylinkedlist_t *doublylinkedlist, void *value);
#endif /* __DOUBLYLINKEDLIST_H__ */
Now, that we have seen the header file, let us go through the core implementation file ("doublylinkedlist.c").
#include <stdio.h>
#include <stdlib.h>
#include "doublylinkedlist.h"
int doublylinkedlist_init (doublylinkedlist_t *doublylinkedlist,
int (*compare_func)(const void *, const void *)) {
if (!doublylinkedlist) {
return (-1);
}
doublylinkedlist->head = doublylinkedlist->tail = NULL;
doublylinkedlist->compare_func = compare_func;
return 0;
}
int doublylinkedlist_free (doublylinkedlist_t *doublylinkedlist) {
doublylinkedlist_node_t *node, *prev_node;
if (!doublylinkedlist) {
return (-1);
}
node = doublylinkedlist->head;
while (node) {
prev_node = node;
node = node->next;
free(prev_node);
}
doublylinkedlist->head = doublylinkedlist->tail = NULL;
return 0;
}
doublylinkedlist_node_t *doublylinkedlist_search (doublylinkedlist_t *doublylinkedlist,
void *search_value) {
doublylinkedlist_node_t *node = NULL;
if (!doublylinkedlist || !search_value) {
return NULL;
}
for (node = doublylinkedlist->head; node != NULL; node = node->next) {
if (doublylinkedlist->compare_func(node->value, search_value) == 0) {
return node;
}
}
return NULL;
}
int doublylinkedlist_insert (doublylinkedlist_t *doublylinkedlist, void *value) {
doublylinkedlist_node_t *node, *next, *new_node;
new_node = (doublylinkedlist_node_t *)malloc(sizeof(doublylinkedlist_node_t));
if (new_node == NULL) {
printf("Malloc Failure\n");
return -1;
}
new_node->value = value;
new_node->next = new_node->prev = NULL;
if (doublylinkedlist->head == NULL) {
/* new_node is the head and tail */
doublylinkedlist->head = new_node;
doublylinkedlist->tail = new_node;
return 0;
}
/* Make the next of the current tail point to the new node */
doublylinkedlist->tail->next = new_node;
/* Make the previous of the new node point to the current tail */
new_node->prev = doublylinkedlist->tail;
/* Make the new node, the new tail */
doublylinkedlist->tail = new_node;
return 0;
}
void doublylinkedlist_delete (doublylinkedlist_t *doublylinkedlist, void *value) {
doublylinkedlist_node_t *node = doublylinkedlist->head;
doublylinkedlist_node_t *prev = doublylinkedlist->head;
doublylinkedlist_node_t *next, *node_to_free = NULL;
while (node) {
if (doublylinkedlist->compare_func(node->value, value) == 0) {
node_to_free = node;
next = node->next;
if (node == doublylinkedlist->head) {
prev = doublylinkedlist->head = node->next;
prev->prev = NULL;
} else if (node == doublylinkedlist->tail) {
doublylinkedlist->tail = node->prev;
prev->next = NULL;
} else {
prev->next = node->next;
next->prev = prev;
}
node = node->next;
free(node_to_free);
/* There may be more nodes with the same value, so continue. */
continue;
}
prev = node;
node = node->next;
}
}
The doublylinkedlist_init() should be called before using the doublylinkedlist_t structure since it this API initializes the head, the tail, and also sets the compare_func callback function. The doublylinkedlist_free() should be called in the end to free the earlier malloced elements.
The doublylinkedlist_search() also walks through each node and compares (using the compare_func() callback) the value of the current node with the passed value -- the moment, it finds the node with a value that matches the passed value, it returns.
The doublylinkedlist_insert() adds the node straightaway to the tail of the list -- pretty simple! The insert function allows us to add multiple nodes with the same value.
Lastly, doublylinkedlist_delete() also does a walk, searching for the element that needs to be deleted; once again, it relies on the compare_func() callback to do the comparison. When it finds a node with that value, then it deletes that node. The deletion means that the next pointer of the previous node points to the next node of the current node. In addition, it also makes the previous pointer of the next node point to the previous node of the current node.
Note that the above file includes "stdlib.h" header file for the malloc() call; this include file is a standard C header that contains declaration for functions like malloc(), calloc(), free() etc. On some systems, you might find "malloc.h" as well that will contain these definitions -- but, we should refrain from including "malloc.h" since it is not standard and may not be available on all systems; we recommend doing a "man stdlib.h" for more details.
The above two files ("doublylinkedlist.h" and "doublylinkedlist.c") is pretty much all we need as an implementation of a doubly-linked list. However, to complete the story, we also add a simple application that uses this implementation. Here is the file ("main_doublylinkedlist.c"),
#include <stdio.h>
#include <stdlib.h>
#include "doublylinkedlist.h"
int doublylinkedlist_compare_for_me (const void *value1, const void *value2) {
if ( *(int *)value1 < *(int *)value2 ) {
return -1;
} else if ( *(int *)value1 > *(int *)value2 ) {
return 1;
} else {
return 0;
}
}
void doublylinkedlist_print (doublylinkedlist_t *doublylinkedlist) {
doublylinkedlist_node_t *node = doublylinkedlist->head;
printf("Linked List (from head): ");
for (node = doublylinkedlist->head; node != NULL; node = node->next) {
printf("%d ", *(int *)node->value);
}
printf("\n");
printf("Linked List (from tail): ");
for (node = doublylinkedlist->tail; node != NULL; node = node->prev) {
printf("%d ", *(int *)node->value);
}
printf("\n");
}
int main (int argc, char *argv[]) {
doublylinkedlist_node_t *node, *ret_node, *prev_node;
int input_array[] = {680, 880, 280, 780, 980};
int len = sizeof(input_array)/sizeof(input_array[0]);
int val_to_search, random_counter, i;
doublylinkedlist_t doublylinkedlist;
doublylinkedlist_init(&doublylinkedlist, doublylinkedlist_compare_for_me);
for (i = 0; i < len; i++) {
doublylinkedlist_insert(&doublylinkedlist, (void *)&input_array[i]);
}
doublylinkedlist_print(&doublylinkedlist);
random_counter = random() % len;
val_to_search = input_array[random_counter];
ret_node = doublylinkedlist_search(&doublylinkedlist, (void *)&val_to_search);
if (ret_node == NULL) {
printf("Not Found: %d\n", val_to_search);
} else {
printf("Found: %d\n", val_to_search);
}
random_counter = random() % len;
printf("Let us delete the value (%d) from the linkedlist\n",
input_array[random_counter]);
doublylinkedlist_delete(&doublylinkedlist, (void *)&input_array[random_counter]);
doublylinkedlist_print(&doublylinkedlist);
/* All done! Free the doubly-linkedlist */
doublylinkedlist_free(&doublylinkedlist);
return 0;
}
In this above file, we start by calling doublylinkedlist_init() and pass pointer to a doublylinkedlist structure. We also pass a custom compare function. For the sake of simplicity, the example uses values that are integer but makes them a "void *" by typecasting. The comparison function is pretty simple -- it compares the two void values by casting them as integers -- if the first one is bigger, then it returns 1, if the first one is smaller, then it returns -1, and 0, if otherwise. Since the "void *" value is opaque for the core implementation, the application file also defines its own print function: doublylinkedlist_print(). Once this is done, this file then uses various APIs for doing operations like insert, search, delete, and print.
Now that we have put together all the three pieces, let us compile them and get the output. To compile these files, we would need to pass both files to gcc: "gcc doublylinkedlist.c main_doublylinkedlist.c -o doublylinkedlist" and to run it, we can use "./doublylinkedlist". Here is the output:
user@codingbison $ gcc doublylinkedlist.c main_doublylinkedlist.c -o doublylinkedlist user@codingbison $ ./doublylinkedlist Linked List (from head): 680 880 280 780 980 Linked List (from tail): 980 780 280 880 680 Found: 780 Let us delete the value (880) from the linkedlist Linked List (from head): 680 280 780 980 Linked List (from tail): 980 780 280 680 user@codingbison $
Note that, if we have another application ("main_doublylinkedlist2.c"), then we can pass the same doublylinkedlist.c file as well: "gcc doublylinkedlist.c main_doublylinkedlist2.c -o doublylinkedlist2". This demonstrates that the header file and the implementation file remains across different application files and thus, if we have a generic application, then we can reuse it. For "main_doublylinkedlist.c" file, the output is same as before, we omit it.