Doubly Linked List – Delete Operation

Linked Lists

Contents

IntroExamplePseudocodeExamplesTimeSpace

Delete Operation in Doubly Linked List

After deleting the node at index/position = 2 (value 30).

Deleting from a doubly linked list involves removing a specific node and adjusting both the next pointer of the previous node and the prev pointer of the next node.

This operation can occur at the beginning, in the middle, or at the end of the list. Doubly linked lists allow efficient deletion from any position as each node has pointers in both directions.

Visual Example

Suppose we have a doubly linked list:

We want to delete the node at index 2 (value 30). After deletion, the list becomes: 10 ⇄ 20 ⇄ 40 ⇄ null

Step-by-Step Deletion at Index 2 (Doubly Linked List)

  1. Start with list 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ null.
  2. Traverse to the node at index 2 (value 30).
  3. Update the previous node's next pointer:
    30.prev.next = 30.next (i.e., 20 → 40).
  4. Update the next node's prev pointer:
    30.next.prev = 30.prev (i.e., 40 ← 20).
  5. The node with value 30 is now disconnected and will be garbage collected.

Complete Pseudocode: Delete Node in Doubly Linked List

This pseudocode shows how to delete a node at a specific index in a doubly linked list, handling both forward and backward links.

head.prev to null.",
    "If the index is greater than 0, initialize a pointer curr to head.",
    "Loop index times to move curr to the target node.",
    "Check if curr is not null, which ensures a node exists at that index.",
    "If curr.prev exists, set curr.prev.next to curr.next.",
    "If curr.next exists, set curr.next.prev to curr.prev.",
    "This detaches the curr node from the list in both directions.",
    "Return head of the updated list."
  ]'>function deleteAt(head, index):
    if index == 0:
        head = head.next
        if head is not null:
            head.prev = null
        return head

    curr = head
    for i in range(index):
        curr = curr.next

    if curr is not null:
        if curr.prev is not null:
            curr.prev.next = curr.next
        if curr.next is not null:
            curr.next.prev = curr.prev

    return head

Let’s walk through each part of the code to understand how it works in a doubly linked list context.

function deleteAt(head, index):

Explanation: This function deletes the node at the specified index from a doubly linked list.

    if index == 0:
        head = head.next
        if head is not null:
            head.prev = null
        return head

Explanation: If the node to delete is the head, we move the head pointer forward and detach the new head from the old one by setting head.prev to null.

    curr = head
    for i in range(index):
        curr = curr.next

Explanation: We move the curr pointer to the node at the target index.

    if curr is not null:
        if curr.prev is not null:
            curr.prev.next = curr.next
        if curr.next is not null:
            curr.next.prev = curr.prev

Explanation: If the node exists, we unlink it in both directions: its previous node skips forward, and its next node skips back, effectively removing curr from the list.

    return head

Explanation: The function returns the updated head of the doubly linked list.

Initial List Delete Operation Resulting List
10 ⇄ 20 ⇄ 30 ⇄ 40 Delete from Beginning 20 ⇄ 30 ⇄ 40
10 ⇄ 20 ⇄ 30 ⇄ 40 Delete from End 10 ⇄ 20 ⇄ 30
10 ⇄ 20 ⇄ 30 ⇄ 40 Delete node with value 20 10 ⇄ 30 ⇄ 40
10 Delete from Beginning [Empty List]
[Empty List] Delete from End [Empty List]

Time Complexity of Doubly Linked List Delete Operation

Deletion Case Time Complexity Explanation
Delete at Beginning O(1) We update the head pointer to the next node and set its prev to null. No traversal is required.
Delete at Middle O(n) We traverse to the node to delete, then update its prev.next and next.prev pointers. Finding the node takes linear time.
Delete at End O(n) We traverse to the last node, then update the tail or prev.next pointer and set the last node's prev to null.
Delete by Value O(n) We scan the list to find the first node with the target value. Once found, we update both adjacent pointers to unlink the node.

Space Complexity of Doubly Linked List Delete Operation

Deletion Case Space Complexity Explanation
Delete at Beginning O(1) No extra memory is needed. Only the head pointer and the second node’s prev are updated.
Delete at Middle O(1) Only local pointer adjustments are made. The prev and next pointers of adjacent nodes are reassigned.
Delete at End O(1) Even if traversal is required, no extra memory is used. The prev node's next is set to null.
Delete by Value O(1) Once the node is located, deletion involves constant-space pointer changes.

Key Takeaways

  • Efficient Bidirectional Deletion: Doubly linked lists allow deletion in constant time O(1) once the target node is located, thanks to both prev and next pointers.
  • Pointer Updates: When deleting a node, always update both the previous node’s next and the next node’s prev to maintain list integrity.
  • Deletion at Head: Update the head pointer and ensure the new head's prev is set to null.
  • Deletion at Tail: Set the previous node’s next to null and update the tail pointer if maintained.
  • No Extra Space: All deletions are done in-place with no additional memory requirements, giving a space complexity of O(1).
  • Safe Deletion: Always check for null references before accessing or updating prev and next pointers to avoid runtime errors.

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...