Linked List implementation in C

Even-though arrays are a super cool super fast way to store and use data, You need to know the exact amount of data you need to store at the beginning of the programme. So the solution for size restriction of arrays is Linked list data structure.

Even-though implementing Linked List is an easy task with a high level, Object-oriented programming language, It still been a challenge to do the same task with a low-level programming language just like C.

If you still need to clear out concepts about Linked List, get a refreshment about your Linked List knowledge from here.

Most of the linked list implementations of linked lists in C are just consist of a node Structure. Which limit your programme the number of the linked list you can use in the programme to 1. Here you can find an implementation with a linked list structure which lifts your limitations to as much as your memory can hold.

Before stepping into the step by step guide, of implementing the Linked List from scratch, Here I'm going to introduce you the complete code of linked list implementation. Maybe figure it out yourself, with the help of well-commented code without the step by step guide.

If it is difficult, to figure it out, you don't need to spend hours with this the step by step guide is just under the 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

#include <stdio.h> #include <stdlib.h> // Defining the node structure with a value and reference typedef struct node{ int value; struct node * next; }nodeS; // Defining the linked list structure with two references head and tail struct linkList{ nodeS* head; nodeS* tail; }; /* This function is almost optional If you do not have a problem with initially making head and tail null manually simply you do not need this*/ void makeList( struct linkList * linList ){ (*linList).head = NULL; (*linList).tail = NULL; } void insertLast( struct linkList * linList,int value ){ if ( (*linList).head == NULL ){ (*linList).head = malloc(sizeof(nodeS)); (*((*linList).head)).value = value; (*linList).tail = (*linList).head; }else{ (*((*linList).tail)).next = malloc(sizeof(nodeS)); (*((*((*linList).tail)).next)).value = value; (*linList).tail = (*((*linList).tail)).next; } /*You always have to make tails next reference "NULL" every time you replace the tail as it is the condition that checks when traversing the list*/ (*((*linList).tail)).next = NULL; } // This is the function to insert elements at the end of the list void printList(struct linkList linList){ nodeS current; current = *(linList.head); printf("%d -> ", current.value); while (current.next != NULL){ printf("%d -> ", (*(current.next)).value); current = *(current.next); } printf("\n"); } // Removing elements with a specific value void removeByValue(struct linkList * linList, int value){ nodeS * current; current = (*linList).head; /* You have to use "Current" as a reference to head node otherwise you just have a copy of head reference within the function which will does't allow you to traverse though the list*/ if ((*current).value == value){ (*linList).head = (*((*linList).head)).next; }else{ while ( (*current).next != NULL){ if ( (*((*current).next)).value == value ){ if ( (*((*current).next)).next == NULL){ /*In case you got to delete the tail of the list you will lost your tail reference too if does not include this if statement here */ (*linList).tail = current; } (*current).next = (*((*current).next)).next; break; } current = (*current).next; } } } int main() { // Making the first link list from our implementation struct linkList first; makeList(&first); /* You have to include this two lines of code if you does't define the function makeList first.head = NULL; first.tail = NULL; */ insertLast(&first,5); insertLast(&first,8); insertLast(&first,3); insertLast(&first,0); removeByValue(&first,8); insertLast(&first,1); insertLast(&first,9); printf("Our First linked list Currently have these int values\n"); printList(first); // Making the another link list from our implementation struct linkList last; makeList(&last); /* You have to include this two lines of code if you does't define the function makeList last.head = NULL; last.tail = NULL; */ insertLast(&last,2); insertLast(&last,9); removeByValue(&last,2); insertLast(&last,1); insertLast(&last,4); insertLast(&last,8); insertLast(&last,3); insertLast(&last,7); insertLast(&last,6); removeByValue(&last,6); printf("Our Last linked list Currently have these int values\n"); printList(last); }

Don't worry about using so many brackets, in the code. Those brackets will help you to understand each term in separate, which will give you a much better understanding.

Even though there are missing functions in the implementation, Studying these will give you the ability to implement rest of them yourself. So without too much talk let's get into the step by step process of implementing this.

1. Defining a Node structure

1 2 3 4 5 6

// Defining the node structure with a value and reference typedef struct node{ int value; struct node * next; }nodeS;

Node is the building unit of the Linked list. So, first of all, we must have a structure to create nodes. Node is contained of two major components, a variable to hold it's value and reference to another node.

Which we have used an int variable and a pointer to its own structure as the reference to another node. If you are uncomfortable with your knowledge about pointers sharpen it from here, which will be very useful in order to continue this guide.

After successfully implementing this much, make sure to play little with these nodes, making linked lists manually before trying to automate everything.

2. Defining the Structure for Linked List

1 2 3 4 5 6

// Defining the linked list structure with two references head and tail struct linkList{ nodeS* head; nodeS* tail; };

Here is the extra structure that you might not be able to find out within other implementation you may find on the internet.This structure allows us to create as much as linked lists we need within our programme.

As you already know, there must be a reference as the starting point of the list, which we mostly used as the head reference. Even though, the tail is optional I also include it too.

Our head and tail must be directed to nodes, So make sure to use node structure type pointers to point those.

3. (Optional) making a function to point head and tail to "NULL"

1 2 3 4 5 6 7 8 9

/* This function is almost optional If you do not have a problem with initially making head and tail null manually simply you do not need this*/ void makeList( struct linkList * linList ){ (*linList).head = NULL; (*linList).tail = NULL; }

Making head and tail references "NULL" at the beginning is very important, as It is the condition we have to check in the insertion of nodes to the list.

In C structures unlike in Object-Oriented language's classes we can't include a constructor neither we can initialize the values of variables with a default value.

So we have to make head and tail references "NULL" at the start either by doing manually or with the use of a function. In any way, you are good to go.

Within most of the functions we are going to define, we need to use a pointer to the linked list as the argument to the function( Call by reference ), otherwise, it just parses a copy of the linked list which will not apply the desired modifications on the original Linked List.

So we dereference the pointer and get the original list within the function and make it's pointers point to "NULL".

4. The functions to Insert items to the Linked List

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

// This is the function to insert elements at the end of the list void insertLast( struct linkList * linList,int value ){ if ( (*linList).head == NULL ){ (*linList).head = malloc(sizeof(nodeS)); (*((*linList).head)).value = value; (*linList).tail = (*linList).head; }else{ (*((*linList).tail)).next = malloc(sizeof(nodeS)); (*((*((*linList).tail)).next)).value = value; (*linList).tail = (*((*linList).tail)).next; } /*You always have to make tails next reference "NULL" every time you replace the tail as it is the condition that checks when traversing the list*/ (*((*linList).tail)).next = NULL; }

We can define many types of insertion functions to linked list. Inserting at the beginning inserting at the end inserting before or after an exact value. However, I thought one is enough for learning, you define any of them as you need with a proper understanding.

Here I have defined a function for inserting elements at the end of the linked list. Which we most probably used if we use the linked list for implement Stack or Queue.

Implementation is pretty simple as we use a tail reference. We initially check is the head is "NULL" or not, if the head is "NULL" we point both head and tail to that node. Else we add the new node to tails next and make it the new tail.

Here unlike in other programming languages, you can't make the node and then point the reference to it with C. You have to navigate to the exact position you need to add the node and then allocate memory for a Node there and change the values after that.

It is very important to set the tails next reference to "NULL" every time you update the tail, as it is the condition we check when we traverse the Linked List. So make sure to include that piece of code too.

As I mentioned earlier, you have to parse the reference to the Linked List here too. Otherwise, you are not modifying the original linked list. So your skills with pointers must be sharp enough to dereference things get into the exact position you need, in order to make those edits.

5. Let's print the List we made

1 2 3 4 5 6 7 8 9 10

void printList(struct linkList linList){ nodeS current; current = *(linList.head); printf("%d -> ", current.value); while (current.next != NULL){ printf("%d -> ", (*(current.next)).value); current = *(current.next); } printf("\n"); }

Here you have the freedom to chose whether you use Linked List structure or pointer of it as the argument to the function.

As no modification is done on the list, A copy of the linked list also works fine with printing things. All you need is a while loop which ends when the currents next hit the "NULL". "current" is a tempory holder of a Node which initially set as list's head goes Node by Node.

Now you may realize the importance of pointing the tails next to "NULL". Otherwise, all you got is an infinite loop.

6. Removing Nodes from the Linked 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

// Removing elements with a specific value void removeByValue(struct linkList * linList, int value){ nodeS * current; current = (*linList).head; /* You have to use "Current" as a reference to head node otherwise you just have a copy of head reference within the function which will does't allow you to traverse though the list*/ if ((*current).value == value){ (*linList).head = (*((*linList).head)).next; }else{ while ( (*current).next != NULL){ if ( (*((*current).next)).value == value ){ if ( (*((*current).next)).next == NULL){ /*In case you got to delete the tail of the list you will lost your tail reference too if does not include this if statement here */ (*linList).tail = current; } (*current).next = (*((*current).next)).next; break; } current = (*current).next; } } }

As in Insertion, in deletion too, there are many ways we perform. And here you have the function to remove elements with the value you prefer.

So the arguments for the function are the value to be deleted and a reference to the Linked List. As we need to deal with the original Linked List and remove items from it "current" variable which is made of struct node within the function will not work for us. So unlike in printing the list here, we need a node structures pointer variable to traverse within the Linked List.

In this function, we basically check whether we have to delete the head of the list or not If it is head we simply make head's next to the new head. Else we traverse until our current pointer points to the node which exists right before the Node to be deleted. Then we make its next to its next's next, Which will remove desired nodes connection from the list.

Summary

Even-though you code Linked List with C, the Linked List doesn't change. It remains the same, due to the fewer facilities in this low-level programming language, you have to divide the problem into much smaller parts and search solutions for them. Apart from that, you need a good understanding of the Linked List data structure and also about basic C programming.

So it will be a good exercise to implement the missing functions here. If any problem raised just comment it below, we and help each other.

So finally all I need to Know is how was it. Was it helpful, let me know?

Wish you Happy codings.