In previous post, we have introduced linked list data structure and discussed about various types of linked lists. We have also covered the applications of linked list data structure and its pros and cons with respect to arrays. In this post, we will discuss various Linked List implementation techniques in detail and construct a singly linked list in C programming language.
Let’s start by discussing about structure of a linked list node. Each node of a linked list contains a single data element and a pointer to the next node in the list.
|
1 2 3 4 5 6 |
// Data Structure to store a linked list node struct Node { int data; // integer data struct Node* next; // pointer to the next node }; |
Memory allocation of Linked List nodes:
The nodes which will make up the body of the list are allocated in the heap memory. We can allocate dynamic memory in C using malloc() or calloc() function. malloc() takes a single argument (the amount of memory to allocate in bytes), while calloc() needs two arguments (the number of variables to allocate in memory, and the size in bytes of a single variable). malloc() does not initialize the memory allocated, while calloc() guarantees that all bytes of the allocated memory block have been initialized to 0. To deallocate the alloted memory we can use free().
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Helper function in C to return new linked list node from heap struct Node* newNode(int data) { // Allocate the new node in the heap using malloc() and set its data struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; // Set the .next pointer of the new node to point to null node->next = NULL; return node; } |
Constructing Linked List:
This section covers various methods to construct a linked list.
1. Naive method
Naive solution would be to construct individual linked list nodes first and rearrange their pointers later to build the list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Helper function to return new linked list node from heap struct Node* newNode(int data) { // Allocate the new node in the heap and set its data struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; // .next pointer of the new node points to nothing node->next = NULL; return node; } // Naive function for Linked List Implementation containing three nodes struct Node* constructList() { // construct three linked list nodes struct Node* first = newNode(1); struct Node* second = newNode(2); struct Node* third = newNode(3); // rearrange the pointers to construct a list struct Node* head = first; first->next = second; second->next = third; // return pointer to first node in the list return head; } |
2. Single line
Above code can be re-written in a single line by passing next node as an argument to the newNode() function –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Helper function to return new linked list node from heap struct Node* newNode(int data, struct Node* nextNode) { // Allocate the new node in the heap and set its data struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; // Set the .next pointer of the new node to point to the current // first node of the list. node->next = nextNode; return node; } // Naive function for Linked List Implementation containing three nodes struct Node* constructList() { struct Node* head = newNode(1, newNode(2, newNode(3, NULL))); return head; } |
3. Generic method
Above discussed methods would become a pain if number of nodes required is very large in the linked list. We can construct a linked list easily using iteration if the keys are given in the form of an array or any other data structure (using its iterator). Below is the implementation of the idea.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Helper function to return new linked list node from heap struct Node* newNode(int data, struct Node* nextNode) { // Allocate the new node in the heap and set its data struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; // Set the .next pointer of the new node to point to the current // first node of the list. node->next = nextNode; return node; } // Function for Linked List Implementation from given set of keys struct Node* constructList(int keys[], int n) { struct Node* head = NULL, *node = NULL; // start from end of the array for (int i = n - 1; i >= 0; i--) { node = newNode(keys[i], node); head = node; } return head; } |
4. Standard Solution
Standard function adds a single node to the head end of any list. This function is called Push() since we’re adding the link to the head end which makes the list look a bit like a stack. Alternately, it could be called InsertAtFront().
Consider below snippet –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
void push(struct Node* head, int data) { // Allocate the new node in the heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct node)); newNode->data = data; // Set the .next pointer of the new node to point to the current // first node (head node) of the list. newNode->next = head; // Change the head pointer to point to the new node, so it is // now the first node in the list. head = newNode; // No, this line does not work! (Why?) } // Function for Linked List Implementation from given set of keys struct Node* constructList(int keys[], int n) { struct Node* head = NULL; // start from end of the array for (int i = n - 1; i >= 0; i--) push(head, keys[i]); // try to push a key on front - doesn't work return head; } |
Above code does not work as changes to local parameters are never reflected back in the caller’s memory. The traditional method to allow a function to change its caller’s memory is to pass a pointer to the caller’s memory instead of a copy. So in C, to change an int in the caller, pass a int* instead. In general, to change an X, we pass an X*. So in this case, the value we want to change is struct Node*, so we pass a struct Node** instead. i.e. the type of the head pointer is “pointer to a struct node.” and in order to change that pointer, we need to pass a pointer to it, which will be a “pointer to a pointer to a struct node”.
Correct Push() Code –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/* push(): Takes a list and a data value and creates a new link with the given data and pushes it onto the front of the list. The list is not passed in by its head pointer. Instead the list is passed in as a "reference" pointer to the head pointer -- this allows us to modify the caller's memory. The parameter has word "ref" in it as reminder that this is a "reference" (struct Node**) pointer to the head pointer instead of an ordinary (struct Node*) copy of the head pointer. */ void push(struct Node** headRef, int data) { // Allocate the new node in the heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // Set the .next pointer of the new node to point to the current // first node of the list. newNode->next = *headRef; // '*' to dereferences back to the real head // Change the head pointer to point to the new node, so it is // now the first node in the list. *headRef = newNode; } // Function for Linked List Implementation from given set of keys struct Node* constructList(int keys[], int n) { struct Node* head = NULL; // start from end of the array for (int i = n - 1; i >= 0; i--) push(&head, keys[i]); return head; } |
5. Make head pointer global
This approach is not recommended as global variables are usually considered bad practice precisely because of their non-locality: a global variable can potentially be modified from anywhere (unless they reside in protected memory or are otherwise rendered read-only), and any part of the program may depend on it. A global variable therefore has an unlimited potential for creating mutual dependencies, and adding mutual dependencies increases complexity. Global variables also make it difficult to integrate modules because software written by others may use the same global names unless names are reserved by agreement, or by naming convention.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Data Structure to store a linked list node struct Node { int data; struct Node* next; }; // global head pointer struct Node* head = NULL; // Takes a list and a data value and creates a new link with the given // data and pushes it onto the front of the list. void push(int data) { // Allocate the new node in the heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // Set the .next pointer of the new node to point to the current // head node of the list. newNode->next = head; // Change the head pointer to point to the new node, so it is // now the first node in the list. head = newNode; } // Function for Linked List Implementation from given set of keys void constructList(int keys[], int n) { // start from end of the array for (int i = n - 1; i >= 0; i--) push(keys[i]); } |
6. Return head from the push() function
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
/* Takes a list and a data value and creates a new link with the given data and pushes it onto the front of the list. */ struct Node* push(struct Node* head, int data) { // Allocate the new node in the heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // Set the .next pointer of the new node to point to the current // first node of the list. newNode->next = head; // return the new node, so it becomes the first node in the list return newNode; } // Function for Linked List Implementation from given set of keys struct Node* constructList(int keys[], int n) { struct Node* head = NULL; // start from end of the array for (int i = n - 1; i >= 0; i--) head = push(head, keys[i]); // update head here return head; } |
Exercise: Modify the push() function to add nodes at the tail of the list.
(Hint – Locate the last node in the list, and then changing its .next field from NULL to point to the new node, or maintain a tail pointer along with head pointer to perform insertion in constant time.)
Continue Reading: Insert onto the tail of the singly linked list
References: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
(3 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use ideone to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Thnank you 🙂
What are the applications of a linked list?
Linked lists are useful when whenever you can’t move around the linked objects in memory. For example, basically every memory allocator is utilizing a linked list of free buffers.
If your operations include insertion/deletion but do not involve iteration/enumeration, linked lists are actually the fastest. Of course, std::list style linked lists are useless and slow. Linux kernel style (“intrusive lists”) are the ones that’re fast.
Linked lists are useful in certain environments, like when you don’t have enough memory to play around with copying your arraylist, you can’t just use a bunch of fixed-size buffer, because you can’t waste memory for the empty space in them, and your processor doesn’t have a cache, so you won’t get the bonus of locality effects when iterating over the list.