Linked list in linux kernel implementation

Linked list in linux kernel implementation

We learned a lot about linked and solve around 30 odd problems : Linked List Problems. However, actual implementation of linked list in linux kernel is very different that what we learned. So, let’s understand how linked list is implemented in linux kernel and how it is used in kernel code.

In simple linked list, we have nodes which contain data and these nodes point to next node of them. In other words, its the list which contains nodes which are linked. Typical example of structure of node of this kind of list is:

struct node {
  int data;
  struct node * next;
} Node;

However, in linked lists in kernel, it’s the other way around, that is linked list is contained inside the node. This means, that there is no next pointer inside node and every node is effectively a head node, nature of linked list circular and it is doubly linked list. Lot of things in one sentence!!

Linked list implementation in Linux

Let’s understand things in detail. As said, linked list is contained inside the node, structure of node is something like this:

struct node {
 int data;
 list_head list; // list is inside the node
};

Here list_head is what defined as :

struct list_head{
  struct list_head *next, *prev;
}

See it has two pointers, essentially, making any node which contains this structure, part of a doubly linked list. Most interesting part of this kind of definition of node is that same node can be part of multiple list without being reallocated for each list. For example, in traditional linked lists, if I need two linked one as odd numbers and other as prime numbers, i would have to define two linked lists , one containing odd numbers and other for primer number. With implementation provided in linux kernel, we can attache the same node to two lists as shown below.

struct numbers {
 int number;
 list_head odd_numbers; // contains all odd numbers
 list_head primer_numbers; // Contains all prime numbers
};

How to access a node in linked list in Linux Kernel

Now that we have changed the node structure, how can we access a give node of linked list. It was simple to do in normal linked list as base address of node was easily accessible. In linked list in linux kernel, we have pointer to list_head structure in next node and not pointer to next node itself, as shown below.

linked list in linux

There is a beautiful trick in C, which is used here to access base address of node whose list_head pointer is given. Once base address of node is found, accessing becomes similar to normal linked list. Trick is that given a pointer to list_head in structure, and to find the base pointer of structure in which it is present, we need to find the offset at which list_head is stored in list. Once, we know the offset, (how many bytes, it is far from base address), then just subtract that offset from the absolute address of the pointer (which is given) and we get the base address. Figure explains

linked list in linux kernel example

Let’s take an example, we will use structure numbers as given above. To get offset of element number in that, code is:

(unsigned long)(&((struct numbers *)0)->number)

Now, that we have offset of number and absolute address of number, we can get the base address of struct numbers as :

((struct numbers *)((char *)(pos) - (unsigned long)(&((numbers *)0)->number)))

ANSI C defines the offsetof() macro in , which lets you compute the offset of field f in struct s as offsetof(struct s, f). If for some reason you have to code this sort of thing yourself, one possibility is

#define offsetof(type, f) ((size_t) \
 ((char *)&((type *)0)->f - (char *)(type *)0))

Above code is not portable and some compilers may have problems with it.

There are some MACROS which are defined in linux kernel which are useful in dealing with linked lists. Below are some examples:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))


#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

Please refer to this file to understand various macros which are used in linux kernel. In next post, using these constructs, we shall create a linked list , access it and delete a list.

Please share if there is something wrong or suggestion for improvements. Also, if you like the content, please share it.

Quicksort on doubly linked list

Quicksort on doubly linked list

To understand quick sort algorithm, please refer to this post : Quicksort algorithm in C, where we discussed how quicksort is applied to arrays to sort elements. In this post, let’s discuss how to apply quicksort on doubly linked list.

To understand quick sort on doubly linked list, first see what are the basics steps in quick sort :

1. Start with entire set of input.
2. Partition input set at a pivot in such a way elements on left of pivot are smaller and on right are greater than pivot.
3. Now independently sort two partitions got in step 2.

There are separate methods to partition input set into two parts in such a way that pivot is at its right place. One of the methods is given below:

1. set pivot  =  a[high]
2. set i = low - 1
3. for j = l; j <= h-1; j++
   3.a check if a[j] <= pivot
       If yes, increment i; i++;
       Swap(a[i],a[j])
4. once for loop breaks, swap(a[i+1], a[high])
5. return i+1, which is partition point.

Let’s understand above method on input set : 5,4,2,7,9,1,6,10,8

We call above algorithm with high as low = 0 and high = 8. Pivot = 8 and i=-1. Now loop runs j = 0 to 9.

j = 0 :  a[j] = 5 which is less than pivot. increment i++, i =0 swap(a[i], a[j]). Since i and j are same, nothing changes.

j = 1 : a[j] =  4 which is less than pivot, increment i++, i =1 swap(a[i], a[j]). Since i and j are same, nothing changes.

Same for j = 2 and j =3.  At this point i =3.

j = 4 : a[j] = 9 Since, a[j] is greater than pivot nothing changes. i remains 3

j = 5 : a[j] = 1, increment i++, i =4 swap(a[4], a[5]). Array becomes  5,4,2,7,1,9,6,10,8

j = 6 : a[j] = 2, increment i++, i =5 swap(a[5], a[6]). Array becomes  5,4,2,7,1,6,9,10,8

j = 7 : a[j] = 10, which is greater than pivot, nothing happens. At this point loop finishes.

Now we swap the pivot and a[i+1] i.e a[8] and a[5+1]. Hence, array becomes : 5,4,2,7,1,6,8,10,9

And we return 6 as partition point. Look closely that all elements on left are less than 8 and on right are greater than 8.

Once this partition is done, two parts : 5,4,2,7,1,6, and 10,9 are sorted separately using same quick sort algorithm.

Quick sort implementation on array is given below

Now, coming back to our original problem that is applying quick sort algorithm on doubly linked list. Code remains same, only thing is we first need to find the last node of list. Rest all remains same as array based implementation, except from the way element data is access which is obvious. Below is quicksort algorithm implementation using doubly linked lists

Quicksort on doubly linked list

Complexity of quicksort on doubly linked list is O(n log n) which is same as implementation on array.

Please share if something is wrong or missing, or if there is any suggestion on improvement. We would love to hear what you have to say.

Skip list implementation and randomization

Skip list implementation

In last post : Skip lists : Part 1 , we discussed what is skip list, how nodes are arranged, complexity improvements over singly linked list and how search is performed on skip lists. In this post, we will learn, how nodes are inserted and removed from skip lists, what randomization and what are various applications of skip lists, basically, the skip list implementation.

Randomization in skip lists implementation

What we saw in last post was exactly balance skip list. That means every node as exactly same number of nodes as was theoretically possible. Every i+1 level will have exactly half the nodes at i level. However, problem with such a  data structure is insertion and removal becomes too cumbersome, as we need to maintain the entire structure at every insertion and deletion in skip list.

In skip list, this problem is solved using randomization. In skip list it is not mandatory that every second node at level i should be promoted to level i+1. Each node’s level is decided by probability, by tossing a coin. If it is “head”, node moves to level above or remains at same level otherwise. Probability of “head” coming up in flipping of coin is 1/2. So ideally, level 1 should have n/2 nodes, level 2 should have n/4 nodes and so on. Also, node at each level is equally distributed and not bunched together at one end. So in ideal world, randomized skip list is same as balance skip list.

Insertion and delete in skip list

To insert a key x node in skip list, do a search on skip list to find predecessor of x.  If x is not in skip list, create a new node and insert is the lowest level and flip the coin. Based on output if coin flip, promote node to next level. Continue till we see “tail” on coin or highest level is reached.

To delete node from skip list is very simple, just remove node from all the levels in skip list.

Insert a node in skip list implementation

Complexity analysis of skip list implementation

As we are discussing though out our discussion, complexity of search on skip list is O(log n). Also, complexity of insertion and deletion is also dominated by O(log n).

To understand these complexities, please see that expected number of levels in skip list with n nodes is log n where no node is missing. (This is very similar to a binary tree with n nodes).

Search complexity is interesting and easy to understand when we look at it in reverse way, sometimes it is called as backward analysis. Look at figure below.

skip list implementation

Observe that whenever a node is at level i+1, path jumps from level i to i+1. Probability of node being promoted to level i+1 from level i is 1/2. Similarly, there 1/2 probability that node remains at the same level. So the recurrence relation for number of jumps to reach level j will  be

c(j) = 1 + 1/2 *C(j-1) + 1/2 * C(j)

Solving equation it becomes

c(j) = 2 + c(j-1) 
which can proved as c(j) = 2j

Since j is number of level in skip lists, hence search complexity becomes O(log n).

Applications of skip lists

1. Skip lists are used as underlying data store for other data structures like ordered set and ordered map.
2. MemSQL uses skip lists as its prime indexing structure for its database technology.
3.Lucene uses skip lists to search delta-encoded posting lists in logarithmic time.
4. Skip lists are used to implement lockless priority queues in distributed systems.

Reference: http://www.cs.umd.edu/~meesh/420/Notes/MountNotes/lecture11-skiplist.pdf
Please share if you know some other applications of skip lists.

Please comment or write if you find something wrong or think can be improved. Also, if you are interested in contributing to community, please share you articles, we will putting it on site with due credit.

Skip list basics : search and insert

What is Skip List?

In last few posts, we discussed about singly linked lists, circular linked lists and doubly linked lists. Today, we will learn something related to singly linked list with something extra. This list is called as Skip List.

To understand skip list, follow one simple example. Example is of any subway or metro railway system. In any metro system, there is concept of fast and slow train. Fast train stops at major stops where as slow one stops at stations which are not covered by fast. Make it clear that slow train also stops on stations on which fast train stops and not every slow train stops at every station. Let’s take below figure as our route map.

skip list examples

Now say I want to go from station A and E. What should I do to reach my destination station as soon as possible. Start at A in fast train, get down at station prior to my destination, take slow train and reach my destination. In above route, I will get down at D and take slow at D to reach E.

skip list implementation

That is the typical concept of skip list. In example, we skip stations which we were sure that are not destinations.

Skip list goals

Skip list starts with goal in mind that how to make search more efficient in list. In typical linked list, to search an item, we need to scan through all nodes of list before the it. This makes complexity of search on list O(N).  Idea is can we skip lot of nodes before node which is to be searched is located. That leads to hierarchy of sorted linked lists.

Skip list is a data structure which can be considered as generalization of singly linked lists. Like in singly linked list, insertion and removal are simple and on top of that, search or retrieval in skip lists is also very efficient as compared to singly linked list.

Skip list looks like this:

search in skip list

Below is comparison chart of complexity of various operations on skip list and normal list :

Operation            Normal list                  Skip list
Insertion            O(N) at end                  O(log N)
                     O(1) at front
Deletion             O(N)                         O(log N)
Retrieval            O(N)                         O(log N)
Ordered traversal    O(N)                         O(N)

How to create skip list?

Problem of above list that it will take a long time before we reach the middle of list. If middle of sorted list can be reached efficiently, we can apply binary search algorithm like in array which will be O(log n) complexity.

To make above list a skip list follow below steps:

1. Start with singly linked list, which is in sorted order
2. Add every alternate node (even node) to level 2. This list skip one node of singly linked list between two nodes.
3. Add every alternate node of list at level 2 to this level. This level will contain n/4 nodes of original list.
4. Continue till h levels where there will be no node to be move to upper level.

How to search an element in skip list?

Algorithm is same as explained in example of subway.

1. Start with the top most level of list.
2. See if there are elements to be searched in it. If yes, check if next element is not null and greater than the key we are looking for? If yes, then move to lower level and repeat step 2.
3. If next element is not null and not less than key, move to next element and repeat step 2.

Let’s say we want to search number 8 in above skip list.

insert in skip list

Start from the top, check next node which is greater than key are looking for. So move down. Check next node which is 5. 5 is less than key 8, hence continue and check next node which is 9, which is greater, so move down at node 5.  Again check next which is 7 and less than key 8, hence move to 7. Check next of 7 at this level, which is 9, greater than key. Hence move down at 7 and check the next node at that level. Next node is 8, the key are looking for. Number of nodes traversed, 1 (to start with), 5, 7 and 8.

In next post, we will discuss how to implement skip lists, their randomized nature, and various applications of skip list.

Please share if you have any suggestion or feedback. Also, if you want to contribute to this blog, it is more than welcome, and paid too. Share if you liked the content, sharing is caring.

Reverse doubly linked list implementation

Reverse doubly linked list

In last two posts : Doubly linked list and Delete a node from doubly linked list, we learned how to insert and delete a node from a doubly linked list. In this post, we will discuss how to reverse doubly linked list. By reversing we mean next pointer should point to previous and previous pointer should point to next node. For example:

Original list : 2->7->6->12->10->1->NULL
Reverse list : 1->10->12->6->7->2->NULL

While reversing singly linked list, two nodes were to be keep track, previous node and next nodes and only one pointer was to be change. Pointer pointing to next node was made to point to previous node.

Difference while reversing doubly linked list is that there are two pointers per node, previous and next. To put node in reverse doubly linked list, next pointer should be made to point to previous node where as previous pointer should be made to point to next node. That is the algorithm, follow it for all nodes.

Algorithm to reverse doubly linked list

1. Check if there is no node or only one node, return
2. While there is node in ddl,
   2.a Save previous node of current node prev = current->prev
   2.b Save next node of current node next = current->next
   2.c Change current node's next to point to prev current->next = prev
   2.d Change current node's prev to point to next current->prev = next
   2.e move current to next node. current = next
3. Change headRef to point to last current node.

Reverse a doubly linked list implementation

Complexity of algorithm to reverse doubly linked list is O(n) as we have to traverse the entire list at least once.

Please share if there some other efficient or elegant method to so. Will sure put that on this blog. If you are interested in contributing to website or want to share interview experiences, please contact us.

Delete node in doubly linked list

Delete node in a doubly linked list

In last post : Doubly linked list, we learned what are doubly linked list, what is it’s node structure, and how to insert a node at various places in doubly linked list. In this post we will learn how to remove or delete node from doubly linked list. For example,

delete node from doubly linked list

To delete a node there are two kinds of input which can be given. One, when data is given and second when actual node address is given. When data is given, it is difficult to delete a node if list contains duplicates. Where as when node address is given, uniquely that node is deleted.

Another advantage when node address is given is that delete operation is done in O(1) where as with data it is done in O(n).

In both the above cases, once the node to be deleted is found, process is same. It is 4 step process:

1. Save next node of node to be deleted, nextNode
2. Save previous node of node to be deleted, prevNode
3. If prevNode is not null, then prevNode->next = nextNode
4. If nextNode is not null, then nextNode->prev = prevNode

Extra thing which needs to be done is scanning the list to find node when data is given.

There is one case which needs to be handled, when the node should be delete is head. Usually we think that deletion at head, tail and middle should be handled separately, but that is not the case. Everything is taken care of by above algorithm. In head deletion case, only extra thing we need to do is change the head reference.

Delete node in doubly linked list implementation

With node pointer given

With data given

Please share your views and suggestions, we would love to hear what you have to say. Sharing is caring. If you are interested in contributing to website or have an interview experience to share, please contact us.

Insert in doubly linked list

Insert in doubly linked list 

In last few posts : Linked List Problems., we learned about singly linked list. Singly linked list has only one pointer per node which points to next node. There is only one way in which list can be traverse, that is forward. We cannot traverse it backward. In this post, we will discuss insert in doubly linked list.

Doubly linked list solves problem the problem to traversing both ways, it can be traversed backwards and forwards. Doubly linked list nodes contain two pointers each, one points to next node and other points to previous node of current node. To move forward, use next pointer and to move backward, use previous pointer.

insert doubly linked list

Insertion in Doubly linked list

There are four place a new node can be inserted into DLL.

 1. Head of list
2. Tail of list
3. Before a given node
4. After a given node

1. Insert in doubly linked list : At front

To insert a node at head, make sure that head pointer is change after insertion. Also in DLL, previous pointer of last head node points to new node, next of new node points to last head node and previous of new node points to NULL. Below these steps are clarified:

1. Create a new node
2. Make next of new node to point to old head
3. Make previous of old head to point to new node
4. Change headRef to point to new node
5. Make previous of new node as NULL

Below figure explains the insert operation at head

insert in doubly linked list at front

Code to insert at node at front of DLL

2. Insert in doubly linked list : At end

To insert at end, we obviously need to traverse to end of list. There is special case that needs to be handle, that is if this is first node of doubly linked list. Extra thing to do is point previous of first node to NULL.

1. Create new node with data
2. Check if this is first node, make previous to point to NULL, change headRef
3. Else traverse till last node of list.
4. Make next of last node point to new node.
5. Make previous of new node point to last node.
6. Make next of new node point to NULL

3. Insert in doubly linked list : After a given node

This is very similar case to insert at the end. Only thing not to be done is to check if this is first node.Rest all remains same.

1. Create new node with data
2. Save next of givenNode (nextNode)
3. Make next of givenNode point to new node.
4. Make previous of nextNode to point new node
5. Make previous of new node point to givenNode.
6. Make next of new node point to nextNode

4. Insert in doubly linked list : Before a given node

Again similar case to 3, only next and previous pointers to point to correct nodes.

1. Create new node with data
2. Save previous of givenNode (prevNode)
3. Make next of new Node point to givenNode
4. Make previous of givenNode point to new node.
4. Make next of prevNode point to new node.
6. Make previous of new node to point to prevNode

Below figure explains insert operation before a given node

insertion in doubly linked list before a node

Complexity of insertion is at start, before or after a given node is O(1) where for insertion at end is O(n).

Please share if there is something wrong or missing. If you are interested in contributing to website or share interview experience, please contact us.

Circular linked list and applications

Circular linked lists applications

In last few posts, we discussed about singly and doubly linked lists. This post is about circular linked list. Singly linked list is a list where each node points to its next node, there is no link from a node to previous, last node points to NULL node. Additional pointer needs to be kept in order to traverse linked list from start. Example of singly linked list given below:

circular linked lsit

What is circular linked list?

Circular linked list is a singly linked list with an additional thing. In circular linked list, next pointer of last node does not point to NULL. Next of last node of list again points to the head node of list. This in turn means there is no end node in circular linked list. Example of circular linked list is shown below:

circular linked list example

How to find what is head node of circular linked list? There are two ways :

1.Keeping an external pointer as in case of singly linked list, which points to head node.

2. Keeping a dummy node, header. This node is separated from regular nodes of list by keeping a SENTINEL value in it. Other way is to have a flag to indicate that it is a head node.

Insertion in circular linked list

Node definition of circular list is same as singly linked list. There are three cases when where we can insert a node in circular linked list.

1. Insert at start of list.

We have an extra pointer which points to head node of the list. When node is added at front of list, that pointer is to be changed. Also, in circular linked list, last node points to head node, hence that link also should be changed.

1. Create a new node.
2. If this if first node, point it's next to itself
   head->next = head
3. Else, scan list and go to last node while(current != *headRef)
4. Change next node of new node to point to earlier head.
   newNode->next = *headRef
5. Change head to point to new node.
   *headRef = newNode
6. Change next pointer of last node to point to new node
   lastNode->next = newNode

Since head node is changing, function call will be headRef and not head pointer only. Below is code for above algorithm to add a node at start of circular linked list

2. Insert at the middle of circular linked list.

This insertion is same as singly linked list, as there is no change in head or tail of circular list. Just scan to the required position, add new node.

next = prev->next;
prev->next = newNode;
newNode->next = next;

3. Insert at the end of circular linked list

This case is very similar to above case, only difference will be that next pointer of last node will be head node. No implementation change.

Delete node from circular linked list

To remove a node, care should be taken when removing head or last nodes. When last node is removed, previous to last node should now start pointing to head node. When head node is removed, last node should now be pointing to new head node. Below is code to remove node.

Complexity of insert and removal of nodes in circular linked list is O(n) as we always need to traverse linked list at least once.

Applications of circular linked lists

  • Implementation of waiting and context switch queues in operating system. When there are multiple processes running on operating system and there is mechanism to provide limited time slots for each process, waiting process can form a circular linked list. Task at head of list is given CPU time, once time allocated finishes, task is taken out and added to list again at the end and it continues.
  • Circular linked list is useful in implementation of queues using lists. Remember in post: Stack and Queue implementation using linked list, we had two pointers, one to point to head and other to point to end of list, because in queue, addition happens at end and removal  at head. With circular list, that can be done using only one pointer.

Please share your views and suggestions. We would love to hear what you have to say. Sharing is caring.  If you are interested in contributing to website or you have interview experience to share, please contact us.

Insert sort on linked list C implementation

Insert sort on linked list

In last post Insert in sorted order in linked list, how to insert a new node into sorted list so that resultant list is also sorted. We will be using the same concept and implement insert sort on linked list.

First of all, let’s understand what is insertion sort. Insertion sort is a sorting technique in which, each element is take out from input and insert into it’s appropriate place in output. When all elements of inputs are inserted at their right place, list is sorted.

Insert sort on linked list algorithm

Array based implementation requires movement of all elements on to right of correct place by one position. At any given elements, all elements on to left of that are sorted and this current element needs to be inserted into that sorted part of array. And it is done for all n elements, hence complexity of insertion sort is O(n2). Below example explains how insertion sort works:

Input: 3,2,1,6,4,9,7,5
Step 1 : Take out 3. There is no elements on left, move
Step 2 : Take out 2. Now since 2 < 3, it should be before 3. Insert it.
Array : 2,3,1,6,4,9,7,5
Step 3 : Take out 1, it is smaller than 2 and 3, and should be placed before them. Insert it.
Array : 1,2,3,6,4,9,7,5
Step 4 : Take out 6. It is greater than all elements on left. Skip it.
Array : 1,2,3,6,4,9,7,5
Step 5 : Take out 4, 4 < 6 and greater than 3, insert 4 between 3 and 6
Array : 1,2,3,4,6,9,7,5
Step 6 : Take out 9, It is greater than all elements on left, skip it.
Array : 1,2,3,4,6,9,7,5
Step 7 : Take out 7. It is less than 9 and greater than 6. Insert it in between 6 and 9
Array : 1,2,3,4,6,7,9,5
Step 8 : Take out 5, 5 is less than 6 and greater than 4. Insert it there.
Array : 1,2,3,4,5,6,7,9 (output)
1. Start i = 0 to n
2. Let's say x = array[i]
3. Start from j = i and j > =0
   3.a if x < array[j]  array[j+1] = a[j] and move left i.e j--
   3.b if x > array[j] array[j] =

C implementation of insert sort on arrays

Implementing insert sort on linked list is simple as we don’t have to move any node right. Just take out the node and insert it at appropriate place in already sorted list, this where will use : Insert in sorted order in linked list

Insert sort on linked list implementation 

In implementation, we initialize a new list which is NULL to start with, then insert nodes of original list into result list in sorted order. Note that we are not allocating any new memory, only nodes are moved from one place to another.

Output of insert sort

Original list : 2->7->6->12->10->1->NULL
Output : 1->2->6->7->10->12->NULL

Complexity of insert sort on linked list is also O(n2).

Please share your suggestions, or if something is wrong. We would love to hear what you have to say. Sharing is caring. If you want to contribute to website or have an interview experience to share, please contact us.

Insert node in sorted linked list

Insert node in sorted linked list

Today’s problem is to insert node in sorted linked list. Extension to thi statement will be to create linked list in sorted order. Every new node added to linked list should adhere to the fact the resultant linked list is in sorted order. For example,

List : 2->7->8->9->NULL Item to be inserted : 6
Resultant list : 2->6->7->8->9

This is very simple problem to solve. There are three cases below needs to be solved for, rest all is just traversing of linked list.

1. When there is no node in list and first node is added.
2. When new node to be added is less than head of list
3. New node to be added in middle or end of list.

Insert node in sorted linked list

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
//Add node to sorted list
void addNode(Node **headRef, int value){
	if(!(*headRef)) {
		*headRef = createNode(value);
		return;
	}
 
	Node *current = *headRef;
	//Special case when data is less than head itself
	if(value < current->data){
		Node *temp = createNode(value);
		temp->next = *headRef;
		*headRef = temp;
		return;
	}
	/*traverse till we find node greater 
         than value to be inserted.*/
	while(current && current->next 
              && current->next->data < value){
		current = current->next;
	}
 
	//Put new node between current and current next
	if(current){
		Node *temp = createNode(value);
		Node *next = current->next;
		current->next = temp;
		temp->next = next;
	}
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
    printf("NULL");
    printf("\n");
}
 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
 
        addNode(&L1,12);
        addNode(&L1,10);
        addNode(&L1,8);
        addNode(&L1,6);
        addNode(&L1,4);
        addNode(&L1,2);
 
 	printList(L1);
 
        return 0;
}

Complexity of above algorithm to insert node in sorted linked list is O(n) to insert each new node, as entire list might have to be traversed if new node to be added is greater than all nodes already added.

There is a bit tricky implementation of same solution. We have used last pointer reference when we learned how to insert node at the end of list. Maintain a reference of next of current node. Check new node to be inserted using reference. If node being pointed by reference has data greater than value to be inserted, create a new node and point its next to node pointed by reference. Now change the reference itself to point to new node, which in turn changes the next pointer of previous node. (Remember we are modifying reference and not a pointer). Reference starts with pointing to head node.

Node **current = headRef

Insert node in sorted linked list: Implementation

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
//Add node to sorted list
void addNodeRef(Node **headRef, int value){
 
	//Start with referencing to head.
	Node **current = headRef;
 
	//Till we find that data of next node is greater than value
	//here current is reference to next node.
	while(*current && (*current)->data < value){
		current = &((*current)->next);
	}
	//Create new node
	Node *newNode = createNode(value);
 
	//New node's next should point to next node. 
	newNode->next = *current;
 
	/*As current is reference to next node, 
        that has to be set to new node.*/
	*current = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}
 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
 
        addNodeRef(&L1,12);
        addNodeRef(&L1,10);
        addNodeRef(&L1,8);
        addNodeRef(&L1,6);
        addNodeRef(&L1,4);
        addNodeRef(&L1,2);
 
 	printList(L1);
 
        return 0;
}

Let us understand what is going on here in code. First currentNext reference is declared which points to head node of list. Situation is something like below:

insert node in sorted linked list

Now we check if pointer being pointed at by currentNext is not null, and if data in that node is less than new node to be inserted. If data is less, we make currentNextRef pointer to point to next of currentNextRef node.

Once value in node pointed by currentNext is higher, we exit the while loop. At this point, currentNextRef is pointing to next node of current node. We make next of new node point to currentNextRef node and change currentNextRef to point to new node.

insert node in sorted linked list example

Complexity will be same but there is no explicit handling of above mentioned cases, they are implicitly handled.

For further problems on linked list, please refer : Linked list problem

Please share if there is something is missing or wrong. If you are interested in contributing to website, please contact us.