Deletion in a Doubly Linked List in C
Just like insertion, we have three scenarios while deleting a node in a doubly linked list:
- Deletion from the beginning of the list.
- Deletion from the end of the list.
- Deletion at specific position of the list.
a. Deletion at the Beginning of the Doubly Linked List
To delete a node at the beginning of the doubly linked list, follow the below approach:
Approach:
- Check if the List is Empty: If true, there’s nothing to delete.
- Check if the List Contains Only One Node:
- Set head to NULL.
- Free the memory of the node.
- If the List Contains More Than One Node:
- Update head to head->next.
- Set the prev of the new head to NULL.
- Free the memory of the old head.
Time Complexity: O(1), as deletion is done at front so we are not traversing through the list.
b. Deletion at the End of the Doubly Linked List
To delete a node at the end of the doubly linked list, follow the below approach:
Approach:
- Check if the List is Empty: If true, there’s nothing to delete.
- If the List is Not Empty:
- Traverse to the last node using a loop.
- Check if the last node is the only node (head->next == NULL):
- Update head to NULL.
- If more than one node:
- Set the next of the second last node (last->prev) to NULL.
- Free the memory of the last node.
Time Complexity: O(n), as deletion is done at the end, so we need to traverse through the list. If a tail pointer is maintained, this operation can be optimized to O(1) by directly accessing the last node.
c. Deletion at a Specific Position in Doubly Linked List
For deleting a node at a specific position in a doubly linked list, follow the below approach:
Approach:
- Check Position Validity:
- If position is 0 (or 1 depending on indexing), use deletion at the beginning.
- If position is the size of the list, use deletion at the end.
- Otherwise, proceed with the middle deletion.
- Traverse to the Specified Position:
- Use a loop to reach the node (delNode) at the desired position.
- If delNode is the first node, adjust head.
- If not, adjust delNode->prev->next and delNode->next->prev if delNode->next is not NULL.
- Free the Memory:
- Release the node to be deleted.
Time Complexity: O(n), as deletion is done in between, as we may need to traverse up to n elements to find the correct position.
Doubly Linked List in C
A doubly linked list is a type of linked list in which each node contains 3 parts, a data part and two addresses, one points to the previous node and one for the next node. It differs from the singly linked list as it has an extra pointer called previous that points to the previous node, allowing the traversal in both forward and backward directions.
In this article, we will learn about the doubly linked list implementation in C. We will also look at the working of the doubly linked list and the basic operations that can be performed using the doubly linked list in C.