Posted on by Kalkicode

# Delete a node in a Doubly Linked List

The problem at hand is about deleting a node with a given value from a Doubly Linked List. A Doubly Linked List is a linear data structure where each element (node) contains a value and two pointers, one pointing to the previous node and the other pointing to the next node. This bidirectional linkage allows efficient traversal in both directions.

## Problem Statement

The task is to design a program that deletes a node with a specified value from a Doubly Linked List. If the value is found in the list, the corresponding node should be removed, and the pointers of the neighboring nodes should be updated accordingly.

## Example

Consider the following scenario:

Original Doubly Linked List: 6 → 9 → 1 → 4 → 3 → 6 → 2

Delete node with value 4.

Expected Result: 6 → 9 → 1 → 3 → 6 → 2

## Idea to Solve

To solve this problem, we need to traverse the Doubly Linked List while searching for the node with the given value. Once the node is found, we need to adjust the pointers of the neighboring nodes to bypass the node to be deleted.

## Pseudocode

``````deleteNode(DoublyLinkedList *list, int value):
return
else:
list.tail = NULL
free(temp)
else if list.tail.data == value:
temp = list.tail
list.tail = list.tail.prev
if list.tail is not NULL:
list.tail.next = NULL
else:
free(temp)
else:
while temp is not NULL and temp.data != value:
temp = temp.next
if temp is NULL:
else:
temp.prev.next = temp.next
if temp.next is not NULL:
temp.next.prev = temp.prev
free(temp)``````

## Algorithm Explanation

1. If the linked list is empty, print "Empty linked list" and return.
2. If the value to be deleted is found in the head node:
• If the list is not empty, update the prev pointer of the new head.
• If the list becomes empty, update the tail pointer as well.
• Free the memory of the deleted node.
3. If the value to be deleted is found in the tail node:
• Update the tail pointer to skip the current tail node.
• If the list is not empty, update the next pointer of the new tail.
• If the list becomes empty, update the head pointer as well.
• Free the memory of the deleted node.
4. If the value to be deleted is found in an intermediate node:
• Traverse the list until the node with the target value is found.
• Update the next pointer of the previous node to skip the node to be deleted.
• If the node to be deleted is not the last node, update the prev pointer of the next node.
• Free the memory of the deleted node.

## Time Complexity

• For insertion, each insertion operation takes O(1) time as it simply involves updating the tail pointer and connecting the new node.
• For deletion, the worst-case time complexity is O(n), where n is the number of nodes in the linked list. This is because in the worst case, we might have to traverse the entire linked list to find the node with the given value.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post