Posted on by Kalkicode
Code Doubly linked list

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.

Given 
Doubly Linked List Delete node value 4

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):
    if list.head is NULL:
        print "Empty linked list"
        return
    if list.head.data == value:
        temp = list.head
        list.head = list.head.next
        if list.head is not NULL:
            list.head.prev = NULL
        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:
            list.head = NULL
        free(temp)
    else:
        temp = list.head
        while temp is not NULL and temp.data != value:
            temp = temp.next
        if temp is NULL:
            print "Deleted node not found"
        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:
    • Update the head pointer to skip the current 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.

Code Solution

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.

New Comment