Spread the post

Insertion of linked list

There are following position are possible to insert newly created node of linked list.

1) Beginning of linked list (head position)

2) End position

3) In between linked list node

Before read this article please, viewing an animations of insertion process.

Insertion animation

Linked list Inserted node is:

496, 437, 496, 501, 479, 450, 465, 451, 569, 586

Case 1 : Insertion at start position.

Following process to insert linked list element on start position.

Insert first element 498 in linked list. In this case linked list are empty so create a memory block using malloc function and assign data value is 498 and assign next pointer value is to Root Pointer. And assign this newly memory block to root pointer.

Step 1: Create memory block on heap area.

/* create new memory block using malloc function.*/
struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));

Step 2: Assign data and pointer value.

/*Assign data and next pointer value to newly created node.*/
new_node->data=value;
new_node->next=root;

Step 3: Assign root pointer .

/*Assign root pointer to newly linked list node. */
root=new_node.

Conclusion : Continuous follow this three step to insert linked list node at start position

Visualization : Try it YourselfView Steps

Insert linked list at beginning Insertion of linked list at beginning position root_ptr 496437496501479450465451569586

Another example suppose there are following data are.
144, 325, 343, 44, 23, 36, 66, 612

insert on linked list. then visualize linked list
Make This Linked List.

Example insert node at first position Example- Insert node at staring of linked list root_ptr 14432534344233666612

Code imagination : View to below

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 144next (pointer)= NULLstruct Nodedata (int)= 325next (pointer) struct Nodedata (int)= 343next (pointer) struct Nodedata (int)= 44next (pointer) struct Nodedata (int)= 23next (pointer) struct Nodedata (int)= 36next (pointer) struct Nodedata (int)= 66next (pointer) struct Nodedata (int)= 612next (pointer)

Below in C implementation of insert newly created node at starting position.

Visualization process view


Output
      Case 1: Empty Linked list 
      Output Empty linked List

      case 2: When linked list are not empty 
      Output Linked list data is : 612  66  36  23  44  343  325  144  
      case 3: Free Of linked list Node 

      Free linked list Node element 
    

Another case insert data at end of linked list.

Iterative approach in below code. To find last node of linked list its time taken by O(n). So time complexity of this program will be O(n) . Note that if already find last node then complexity will be a constant (using queue data structure).

Suppose following data are 144, 325, 343, 44, 23, 36, 66, 612 insert on linked list.

Following process to insert linked list element on end position.

Insert first element 144 in linked list. In this case linked list are empty so create a memory block using malloc function and assign data value is 144 and assign next pointer value is to Root Pointer. And assign this newly memory block to root pointer.

Step 1: Create memory block on heap area.

/* create new memory block using malloc function.*/
struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));

Step 2: Assign data and pointer value.

/*Assign data and next pointer value to newly created node.*/
new_node->data=value;
new_node->next=NULL;

Step 3: Find last linked list node and attach newly created node.

/*linked list first node address assign on temp pointer*/
temp=root;
/*This will loop find last node of exist linked list*/
while(temp->next){
/*move temp pointer on next memory block*/
temp=temp->next; }
/*assign this newly created node on end of list*/
temp->next=new_node;
root=new_node.

Conclusion : Continuous follow this steps to insert linked list node at End position

Global Variableroot(pointer) Stack Areamaininsert_datanew_node(pointer)temp(pointer)value (int) =62 Heap Areastruct Nodedata (int)= 44next (pointer) struct Nodedata (int)= 35next (pointer) struct Nodedata (int)= 34next (pointer) struct Nodedata (int)= 75next (pointer) struct Nodedata (int)= 23next (pointer) struct Nodedata (int)= 36next (pointer) struct Nodedata (int)= 66next (pointer)= NULLstruct Nodedata (int)= 62next (pointer)= NULL

Visualize Code

Output
  Case 1: Empty Linked list 
      Output Empty linked List

      case 2: When linked list are not empty 
      Output Linked list data is : 44  35  34  75  23  36  66  62  

      Free linked list Node element 
    

Insertion using queue data structure

When we are use queue data structure to implement linked list then there Time Complexity will be change. Insertion time complexity : O(1). And Deletion time complexity : O(n) to Finding delete node position. More information visit Queue implementation of linked list .

Insertion of between linked list node

The following post are related to insertion between linked list nodes.
Singly linked list insert data in ascending order
Singly linked list insert data in descending order
Single linked list insert node at middle position

Spread the post

Recommended Posts: