Linked List: 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;
int 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. In the end, we put all of these functions together using a main() function.
Basic Operations
Traversing the list
Traversing a singly linked list is simple. We start at the head node and then using the next pointer (or the prev pointer) go towards the other end of the list, one link at a time. 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. That's all!
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
Implementation
After describing the individual operations for the linked list data-structure, let us bring them all under one umbrella. Accordingly, we provide an implementation below that has functions for above operations. These functions help us add a new element in the linked list (linkedlist_insert()), delete an element from the linked list (linkedlist_delete()), search the linked list for an element (linkedlist_search()), free the entire linked list (linkedlist_free()), and print elements of the linked list (linkedlist_print()). We keep all of the these functions along with main() function, in one file (provided below).
Some more notes about the above functions before we get into the implementation. The linkedlist_insert() adds a node to the tail of the list. If the element happens to be the very first, then the implementation also updates the head. The linkedlist_delete() deletes a node from the linked list. 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. The caller of linkedlist_search() should note that a return value of NULL means that the value was not found. In the end, the main() calls the linkedlist_free() function to free each node of the linked list.
#include <stdio.h>
#include <stdlib.h>
typedef struct linkedlist_node {
struct linkedlist_node *next;
int value;
} linkedlist_node_t;
linkedlist_node_t *linkedlist_head = NULL; /* head of the linked list */
linkedlist_node_t *linkedlist_tail = NULL; /* tail of the linked list */
void linkedlist_print () {
linkedlist_node_t *node = NULL;
printf("Linked List: ");
for (node = linkedlist_head; node != NULL; node = node->next) {
printf("%d ", node->value);
}
printf("\n");
}
linkedlist_node_t *linkedlist_search (int search_value) {
linkedlist_node_t *node = NULL;
for (node = linkedlist_head; node != NULL; node = node->next) {
if (node->value == search_value) {
/* Found the node, return. */
return node;
}
}
return NULL;
}
void linkedlist_insert (int 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;
}
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;
}
/* This node is the tail */
linkedlist_tail->next = new_node;
linkedlist_tail = new_node;
}
void linkedlist_delete (int value) {
linkedlist_node_t *node = linkedlist_head;
linkedlist_node_t *prev = linkedlist_head;
linkedlist_node_t *node_to_free = NULL;
/* List has only one node */
if ((node == linkedlist_head) && (node == linkedlist_tail)) {
free(node);
linkedlist_head = linkedlist_tail = NULL;
return;
}
while (node) {
if (node->value == value) {
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;
printf("Deleted: %d\n", value);
free(node_to_free);
/* There may be more nodes with the same value, so continue. */
continue;
}
prev = node;
node = node->next;
}
}
void linkedlist_free () {
linkedlist_node_t *node, *prev_node;
if (!linkedlist_head) {
return;
}
node = linkedlist_head;
while (node) {
prev_node = node;
node = node->next;
free(prev_node);
}
linkedlist_head = NULL;
return;
}
int main (int argc, char *argv[]) {
linkedlist_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;
linkedlist_head = NULL;
for (i = 0; i < len; i++) {
linkedlist_insert(input_array[i]);
}
linkedlist_print();
val_to_search = 980;
ret_node = linkedlist_search(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(input_array[random_counter]);
linkedlist_print();
/* In the end, free the linkedlist */
linkedlist_free();
return 0;
}
For linkedlist_delete(), the implementation assumes that there might be multiple nodes in the list with the same value. If that is not the case, then the call can return once the first value is found and has been deleted; a simple way to do this would be to replace the "continue;" statement in the following code with a "return;" statement.
In the end, we compile the file and check the output. Here are the steps/output.
user@codingbison $ gcc 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 Deleted: 780 Linked List: 680 880 280 980 user@codingbison $
Note that the following 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.
Advanced Implementation
Now that we have seen the above implementation, it is possible to add more bells and whistles to transform it into a production-quality software. For that we can (at the very least) apply two changes to the earlier program.
First of all, we can keep the storage more generic -- while the above program stores integers as elements in the linked list, a generic implementation should support storing any type of data.
Second, we should make the implementation more modular by splitting it into three files: a header file, an implementation file, and a main file that calls the APIs published via the header file. With that, any application can merely take the implementation file and the header file and use it.
If you would like to see an implementation that adds the above two recommendations, you can find it here: Advanced Implementation of Singly Linked Lists.