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):
    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

1) Delete a node from doubly linked list in c 2) Delete a node from doubly linked list in c++ 3) Delete a node from doubly linked list in java 4) Delete a node from doubly linked list in golang 5) Delete a node from doubly linked list in c# 6) Delete a node from doubly linked list in vb.net 7) Delete a node from doubly linked list in php 8) Delete a node from doubly linked list in node js 9) Delete a node from doubly linked list in typescript 10) Delete a node from doubly linked list in python 11) Delete a node from doubly linked list in ruby 12) Delete a node from doubly linked list in scala 13) Delete a node from doubly linked list in swift 14) Delete a node from doubly linked list in kotlin

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.