Spread the post

Delete linked list node in given key position

This post we are learning how to delete given linked list node by on given position. supposed following data [1,2,3,4,5,6,7,8] are inserted on linked list.

root_ptr87654321

Not given insertion of linked list.

Try it yourself

The following process to delete given key position node.

Case (1) If given key position are one. that means deleting first node of linked list.

process:

1) temp=root; One temp pointer store the first linked list element.

root_ptr87654321 temp

2) root=root->next; root node move next node.

root_ptr87654321 temp

3) temp->next=NULL;

root_ptr87654321 temp

Before remove linked list node assign that node next pointer value is (NULL).

4) free(temp); free(remove) first node of linked list.

root_ptr8765432

Time complexity in this case O(1).

Case (2) if given key node are not first node of linked list. then

1) First we need to find that given (key-1) node position. this process will take O(n) time.

Suppose delete position is [3].

root_ptr8765432

2) Suppose find (key-1 node position) are pointed on temp pointer.

root_ptr87654helper 3 temp2

helper=temp->next; Assign that next node address of other helper pointer.

3) temp->next=helper->next; helper pointer next node address are assign to temp->next.

root_ptr87654helper 3 temp2

4) free(helper); free memory block of linked list.

root_ptr8765 3 2

Algorithm:

Below in C implementation of this problem. Iterative approach.

Accepted Output

Given list is :

45--->232--->63--->21--->52--->51--->23--->66--->21--->NULL

Delete node [2] result is

45--->63--->21--->52--->51--->23--->66--->21--->NULL

Delete node [5] result is

45--->63--->21--->52--->23--->66--->21--->NULL

Code execution process:

Stack Areamainroot(pointer)delete_positionhelper(pointer)position (int) =4root(pointer)temp(pointer) Heap Areastruct Nodedata (int)= 2next (pointer) struct Nodedata (int)= 3next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 5next (pointer) struct Nodedata (int)= 6next (pointer) struct Nodedata (int)= 7next (pointer) struct Nodedata (int)= 8next (pointer)= NULL

C program to delete node in given position.

Output
linked list data is: 
1  2  3  4  5  6  7  8  

 Remove position [1] linked list data is: 
2  3  4  5  6  7  8  

 Remove position [7] linked list data is: 
2  3  4  5  6  7  

 Remove position [14]---->> Invalid position to delete node <<--- 

 linked list data is: 
2  3  4  5  6  7  

 Remove position [4] linked list data is: 
2  3  4  6  7  

 Free linked list Node element 

Spread the post

Recommended Posts: