Linked List: Advanced Implementation (Singly Linked List)
A singly linked list is a list, where each element has a next pointer that points to the next node in the list. Typically, the first node of the linked list is referred to as the "head" and the last node is referred to as the "tail" of the list. For the sake of simplicity, we will call the singly linked list as linked list. We interchangeably refer to an element of a linked list as a node.
The following figure shows a simple linked list. Each node of the list is connected to their next neighbor using the "next" pointer; for the tail node, the "next" pointer points to NULL since the tail node is the last node.
Figure: A Singly Linked List
Each element of a linked list is represented by a data structure; we show an example below. The structure contains a "next" pointer -- it is this pointer that allows a node to connect to the next! Equally important, the structure has a "value" member that allows us to store integer values with each link.
typedef struct linkedlist_node {
struct linkedlist_node *next;
void *value;
} linkedlist_node_t;
Note that the compiler would not complain that we define the next as a pointer to the struct linkedlist_node, even though the definition of the structure is not complete yet. This is okay because the storage of a pointer is fixed and the compiler allocates that much storage for it. But, if we were to keep the full structure as a variable inside the structure (e.g. "struct linked_node next"), then the compiler would grudgingly complain that the next field has an incomplete type!
Linked lists allow us to store data on a dynamic basis and do useful things with it. For that purpose, linked lists support a range of operations like traversing elements of the list, inserting newer nodes into the list, searching for a given element in the list, and deleting an existing element from the list.
So, with that, let us test the waters and provide an implementation of a linked list. The implementation provides various C functions that provide the above operations. The implementation on this page has generic elements like storing a "void *" value instead of an integer, and using a header file to publish linked list APIs. If you would like to see a simpler implementation that does the same, you can find it here: Simple Implementation of Singly Linked Lists. If you are trying to get started with linked list, we would recommend that you should read the above first!
Basic Operations
Traversing the list
Traversing a singly linked list is simple. We start at the first node (head or tail) and then using the next pointer (or the prev pointer) go towards the other end of the list. Let us see the basic approach for doing that using a simple loop provided in the pseudo-code below.
linkedlist_node_t *node;
for (node = head; node != NULL; node = node->next) {
// Do whatever needs to be done with this node.
}
The above pseudo-code traverses the linked list by using the next field of the current node; the for loop starts by pointing the linked list node to the head, and then using the next field, it traverses the list. In this pseudo-code, the "head" variable is the head of the linked list. When the loop reaches the last node of the list, the node pointer will point to NULL and the loop terminates.
Most of the operations of a linked list, in fact, do involve traversal. For example, when we are trying to search 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, since we have to search for the node first, before we can delete it.
Searching a list
Searching a node in the list is a good example of a linked list traversal. When we have to search for a node, we use the next pointer to traverse the list and look for the node of interest.
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
When inserting a node in a list, we simply need to insert it at the tail of the list. When doing so, we would also need to allocate the new link using malloc() call. We also need to make the next of the last element (in the figure, the node with value 280) and make it point to the new element. Likewise, we need to take the prev of the new element and make it point to the earlier element (the earlier tail).
Figure: Inserting into a Linked List
Deleting a node
For deleting a node, we need to rearrange the next pointer of the node before the node being deleted and make it point to the next (or previous) node of the node being deleted. If there are multiple such items that match the criteria, then we can delete them one by one.
Let us revisit our earlier example to understand deletion better. In this case, we delete the node with value 880 from the linked list. 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).
Figure: Deleting a node from a Linked List
Advanced Implementation
After describing the individual mechanisms for the linked list data-structure, let us bring them all under one umbrella. Accordingly, we provide an implementation below that defines various has various. Our implementation comes in the form of three files: a header file that publishes the linked list functions (as APIs), an implementation file that implements the published APIs, and a main file that calls these APIs published via the header file. With this approach, any application can merely take the implementation file and the header file and use it.
The header file publishes data structures for linked list and APIs that allow us to initialize the linked list structure (linkedlist_init), insert an element (linkedlist_insert), delete an element (linkedlist_delete), search an existing element in the linked list (linkedlist_search), and to free the entire linked list (linkedlist_free).
linkedlist_init(): Initializes the global variables for linked list linkedlist_free(): Frees the entire linked list linkedlist_insert(): Add a new element in the linked list linkedlist_delete(): Deletes an element from the linked list linkedlist_search(): Searches the linked list and if found, returns the element
So, let us start by looking at the header file.
#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__
/* Node in the Linkedlist */
typedef struct linkedlist_node {
struct linkedlist_node *next;
void *value;
} linkedlist_node_t;
/* Representation of the Linkedlist */
typedef struct linkedlist_ {
struct linkedlist_node *head;
struct linkedlist_node *tail;
int (*compare_func)(const void *, const void *);
} linkedlist_t;
int linkedlist_init(linkedlist_t *linkedlist,
int (*compareFunc)(const void *, const void *));
int linkedlist_free(linkedlist_t *linkedlist);
linkedlist_node_t *linkedlist_search(linkedlist_t *linkedlist, void *val);
int linkedlist_insert(linkedlist_t *linkedlist, void *val);
int linkedlist_insert_sorted(linkedlist_t *linkedlist, void *val);
void linkedlist_delete(linkedlist_t *linkedlist, void *val);
#endif /* __LINKEDLIST_H__ */
The above header file starts with two data-structures. The first structure is linkedlist_node_t; this structure represents each node in the list. It has a next pointer (to point to the next) and a value member with a type of "void *". Defining this is a generic pointer means that we can store any type of data with it. The second data-structure that represents the entire linked list itself (linkedlist_t). The structure holds both the head and the tail of linkedlist. In addition, the linkedlist_t structure also contains a callback function, compare_func; the purpose of this function (this is a callback function and would need to be passed by the application) is to allow the application to specify how the comparison rule for two elements. Since the linked list nodes are going to store (void *), the core implementation of linked list would not know how to do the comparison; we need the comparison when we have to search or delete an element in the linked list. Keeping another structure for the entire linked list means that we can encapsulate linked list level attributes locally in one structure -- this way, multiple applications can reuse the same implementation.
Now that we have seen the data-structures and the API, let us see the actual implementation of the above APIs. For that we provide the linked-list implementation file ("linkedlist.c" ) below.
#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"
int linkedlist_init (linkedlist_t *linkedlist,
int (*compare_func)(const void *, const void *)) {
if (!linkedlist) {
return (-1);
}
linkedlist->head = linkedlist->tail = NULL;
linkedlist->compare_func = compare_func;
return 0;
}
int linkedlist_free (linkedlist_t *linkedlist) {
linkedlist_node_t *node, *prev_node;
if (!linkedlist) {
return (-1);
}
node = linkedlist->head;
while (node) {
prev_node = node;
node = node->next;
free(prev_node);
}
linkedlist->head = linkedlist->tail = NULL;
return 0;
}
linkedlist_node_t *linkedlist_search (linkedlist_t *linkedlist,
void *search_value) {
linkedlist_node_t *node;
if (!linkedlist || !search_value) {
return NULL;
}
for (node = linkedlist->head; node != NULL; node = node->next) {
if (linkedlist->compare_func(node->value, search_value) == 0) {
/* Found the node, return. */
return node;
}
}
return NULL;
}
int linkedlist_insert (linkedlist_t *linkedlist, void *value) {
linkedlist_node_t *node, *new_node;
new_node = (linkedlist_node_t *)malloc(sizeof(linkedlist_node_t));
if (new_node == NULL) {
printf("Malloc Failure\n");
return (-1);
}
new_node->value = value;
new_node->next = NULL;
if (linkedlist->head == NULL) {
/* new_node is the head and the tail, both. */
linkedlist->head = linkedlist->tail = new_node;
return 0;
}
/* This node is the tail */
linkedlist->tail->next = new_node;
linkedlist->tail = new_node;
return 0;
}
void linkedlist_delete (linkedlist_t *linkedlist, void *value) {
linkedlist_node_t *node = linkedlist->head;
linkedlist_node_t *prev = linkedlist->head;
linkedlist_node_t *node_to_free = NULL;
if (!value) {
return;
}
/* List has only one node */
if ((node == linkedlist->head) && (node == linkedlist->tail)) {
free(node);
linkedlist->head = linkedlist->tail = NULL;
return;
}
while (node) {
if (linkedlist->compare_func(node->value, value) == 0) {
node_to_free = node;
if (node == linkedlist->head) {
prev = linkedlist->head = node->next;
} else if (node == linkedlist->tail) {
linkedlist->tail = prev;
prev->next = NULL;
} else {
prev->next = node->next;
}
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 linkedlist_insert() inserts an element at the tail of the linked list and in most of the cases, this is what we would need. The linkedlist_insert() function mallocs a new element of type linkedlist_node_t and then makes the value field point to the passed value. If the element being inserted is the first element, then we make both head and tail pointers point to that. Otherwise, we always updated the tail pointer.
This linkedlist_search() function uses a simple while loop to traverse nodes from head to tail, checking each node to see if the node's stored value is same as that of the passed value; it uses the compare_func() to compare the elements. When the function finds the node that matches the passed value, it returns a pointer to the node (link) immediately; otherwise, it continues its journey. When it hits the end of the list without finding the node, it returns NULL. The caller of linkedlist_search() should note that a return value of NULL means that the value was not found.
The linkedlist_delete() deletes a node that has the value same as that of the passed one. Since the value passed is of the "void *" and so is the value stored in the node, the linkedlist_delete() function uses the help of the compare_func() callback passed by the application. If the two values are same, then then callback should return 0 and the linkedlist_delete() function uses that to identify the element that needs to be deleted. Note that in this implementation, we support multiple nodes with the same value. If needed, we adjust head and (or) the tail pointers.
Before we move further, let us talk about two things.
First, for insertion, we can add a node at possibly three different locations. First, we can insert a node at the head of the linked list and the linkedlist_head pointer would need to be readjusted. Second, we can insert a node at the tail of the linked list and the tail pointer (if any) would need to be readjusted (which is what we are doing here). The third case is when we insert a node somewhere in the middle of the linked list -- a use case for this would be, if we have a sorted linked list.
Second, the above code 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.
Now that we have seen the header file and the implementation file for the generic version, let us look at the main file that will call the API published by the "linkedlist.h" header file.
#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"
int linkedlist_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 linkedlist_print (linkedlist_t *linkedlist) {
linkedlist_node_t *node;
printf("Linked List: ");
for (node = linkedlist->head; node != NULL; node = node->next) {
printf("%d ", *(int *)node->value);
}
printf("\n");
}
int main (int argc, char *argv[]) {
int input_array[] = {680, 880, 280, 780, 980};
int len = sizeof(input_array)/sizeof(input_array[0]);
linkedlist_node_t *node, *ret_node, *prev_node;
int val_to_search, random_counter, i;
linkedlist_t linkedlist;
linkedlist_init(&linkedlist, linkedlist_compare_for_me);
for (i = 0; i < len; i++) {
linkedlist_insert(&linkedlist, (void *)&input_array[i]);
}
linkedlist_print(&linkedlist);
val_to_search = 980;
ret_node = linkedlist_search(&linkedlist, (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]);
linkedlist_delete(&linkedlist, (void *)&input_array[random_counter]);
linkedlist_print(&linkedlist);
/* In the end, free the linkedlist */
linkedlist_free(&linkedlist);
return 0;
}
The above main() function starts by calling linkedlist_init() and passing a pointer to the linkedlist variable. It also passes linkedlist_compare_for_me() as the callback to do the comparison. Since the core implementation ("linkedlist.c") does not know the type of the element, the above file also provides linkedlist_print() implementation that prints the value of the linkedlist. To compile all of these together, we pass both of these C files to gcc as "gcc linkedlist.c main_linkedlist.c -o linkedlist" and then to get the output, run it as "./linkedlist".
user@codingbison $ gcc linkedlist.c main_linkedlist.c -o linkedlist user@codingbison $ ./linkedlist Linked List: 680 880 280 780 980 Found: 980 Let us delete the value (780) from the linkedlist Linked List: 680 880 280 980 user@codingbison $