Write a C program to create a doubly linked list and delete a node from beginning, end or at any position of the linked list. How to delete a node from beginning of a doubly linked list. How to delete a node from end of a doubly linked list. How to delete a node from any position of a doubly linked list in C. Algorithm to delete a node from doubly linked list.
Required knowledge
Basic C programming, Functions, Dynamic memory allocation, Doubly linked list
Algorithm to delete node from beginning of a doubly linked list
Algorithm to delete node from beginning
%% Input: head {Pointer to first node of the linked list}
Begin:
If [head == NULL] then
write ['Can't delete from an empty list']
End if
Else then
toDelete head;
head head.next;
head.prev NULL;
unalloc [toDelete]
write ['Successfully deleted first node from the list']
End if
End
Algorithm to delete node from end of a doubly linked list
Algorithm to delete node from end
%% Input: last {Pointer to last node of the linked list}
Begin:
If [last == NULL] then
write ['Can't delete from an empty list']
End if
Else then
toDelete last;
last last.prev;
last.next NULL;
unalloc [toDelete]
write ['Successfully deleted last node from the list']
End if
End
Algorithm to delete node from any position of a doubly linked list
Algorithm to delete node from any position
%% Input : head {Pointer to the first node of the list}
last {Pointer to the last node of the list}
N {Position to be deleted from list}
Begin:
current head;
For i 1 to N and current != NULL do
current current.next;
End for
If [N == 1] then
deleteFromBeginning[]
End if
Else if [current == last] then
deleteFromEnd[]
End if
Else if [current != NULL] then
current.prev.next current.next
If [current.next != NULL] then
current.next.prev current.prev;
End if
unalloc [current]
write ['Node deleted successfully from ', N, ' position']
End if
Else then
write ['Invalid position']
End if
End
Steps to delete node from any position of a doubly linked list
Let us suppose that we want to delete node from 2nd position.
- Traverse to Nth node of the linked list, lets say a pointer current points to Nth node in our case 2 node.
- Link the node behind current node with the node ahead of current node, which means now the N-1th node will point to N+1th node of the list. Which can be implemented as current->prev->next = current->next.
- If N+1th node is not NULL then link the N+1th node with N-1th node i.e. now the previous address field of N+1th node will point to N-1th node. Which can be implemented as current->next->prev = current->prev.
- Finally delete the current node from memory and you are done.
Program to delete a node from doubly linked list
/** * C program to delete a node from Doubly linked list */ #include #include /* * Basic structure of Node */ struct node { int data; struct node * prev; struct node * next; }*head, *last; /* * Functions used in this program */ void createList[int n]; void displayList[]; void deleteFromBeginning[]; void deleteFromEnd[]; void deleteFromN[int position]; int main[] { int n, data, choice=1; head = NULL; last = NULL; /* * Run forever until user chooses 0 */ while[choice != 0] { printf["============================================\n"]; printf["DOUBLY LINKED LIST PROGRAM\n"]; printf["============================================\n"]; printf["1. Create List\n"]; printf["2. Delete node - from beginning\n"]; printf["3. Delete node - from end\n"]; printf["4. Delete node - from N\n"]; printf["5. Display list\n"]; printf["0. Exit\n"]; printf["--------------------------------------------\n"]; printf["Enter your choice : "]; scanf["%d", &choice]; switch[choice] { case 1: printf["Enter the total number of nodes in list: "]; scanf["%d", &n]; createList[n]; break; case 2: deleteFromBeginning[]; break; case 3: deleteFromEnd[]; break; case 4: printf["Enter the node position which you want to delete: "]; scanf["%d", &n]; deleteFromN[n]; break; case 5: displayList[]; break; case 0: break; default: printf["Error! Invalid choice. Please choose between 0-5"]; } printf["\n\n\n\n\n"]; } return 0; } /** * Creates a doubly linked list of n nodes. * @n Number of nodes to be created */ void createList[int n] { int i, data; struct node *newNode; if[n >= 1] { /* * Creates and links the head node */ head = [struct node *]malloc[sizeof[struct node]]; printf["Enter data of 1 node: "]; scanf["%d", &data]; head->data = data; head->prev = NULL; head->next = NULL; last = head; /* * Create and link rest of the n-1 nodes */ for[i=2; idata = data; newNode->prev = last; // Link new node with the previous node newNode->next = NULL; last->next = newNode; // Link previous node with the new node last = newNode; // Make new node as last node } printf["\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n"]; } } /** * Display the content of the list from beginning to end */ void displayList[] { struct node * temp; int n = 1; if[head == NULL] { printf["List is empty.\n"]; } else { temp = head; printf["DATA IN THE LIST:\n"]; while[temp != NULL] { printf["DATA of %d node = %d\n", n, temp->data]; n++; /* Move the current pointer to next node */ temp = temp->next; } } } /** * Delete or remove the first node of the doubly linked list */ void deleteFromBeginning[] { struct node * toDelete; if[head == NULL] { printf["Unable to delete. List is empty.\n"]; } else { toDelete = head; head = head->next; // Move head pointer to 2 node if [head != NULL] head->prev = NULL; // Remove the link to previous node free[toDelete]; // Delete the first node from memory printf["SUCCESSFULLY DELETED NODE FROM BEGINNING OF THE LIST.\n"]; } } /** * Delete or remove the last node of the doubly linked list */ void deleteFromEnd[] { struct node * toDelete; if[last == NULL] { printf["Unable to delete. List is empty.\n"]; } else { toDelete = last; last = last->prev; // Move last pointer to 2nd last node if [last != NULL] last->next = NULL; // Remove link to of 2nd last node with last node free[toDelete]; // Delete the last node printf["SUCCESSFULLY DELETED NODE FROM END OF THE LIST.\n"]; } } /** * Delete node from any position in the doubly linked list */ void deleteFromN[int position] { struct node *current; int i; current = head; for[i=1; inext; } if[position == 1] { deleteFromBeginning[]; } else if[current == last] { deleteFromEnd[]; } else if[current != NULL] { current->prev->next = current->next; current->next->prev = current->prev; free[current]; // Delete the n node printf["SUCCESSFULLY DELETED NODE FROM %d POSITION.\n", position]; } else { printf["Invalid position!\n"]; } }Output
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 1
Enter the total number of nodes in list: 5
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40
Enter data of 5 node: 50DOUBLY LINKED LIST CREATED SUCCESSFULLY
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 10
DATA of 2 node = 20
DATA of 3 node = 30
DATA of 4 node = 40
DATA of 5 node = 50
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 2
SUCCESSFULLY DELETED NODE FROM BEGINNING OF THE LIST.
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 20
DATA of 2 node = 30
DATA of 3 node = 40
DATA of 4 node = 50
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice :
3
SUCCESSFULLY DELETED NODE FROM END OF THE LIST.
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 20
DATA of 2 node = 30
DATA of 3 node = 40
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 4
Enter the node position which you want to delete: 2
SUCCESSFULLY DELETED NODE FROM 2 POSITION.
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 20
DATA of 2 node = 40
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 0
Happy coding