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,
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.