☕ DSA Java Articles

Topics › Linked List › Learn Doubly LinkedList

Delete head of Doubly Linked List

Easy TUF ID 348 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a doubly linked list. Remove the first node and return the head of the remaining list. The new head must have prev == null. If the list is empty, return null; if it has a single node, removing it leaves the empty list, so return null as well.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer. The operation must not visit the rest of the list.

Example 1

list = 1 <-> 2 <-> 3 <-> 4 <-> 5
answer = 2 <-> 3 <-> 4 <-> 5        // 2 is the new head and 2.prev is null

Example 2

list = 42
answer = (empty)                    // the only node is removed

Example 3

list = (empty)
answer = (empty)                    // nothing to delete

The node type carries a value and two references.

static class Node {
    int val;
    Node prev, next;
    Node(int val) { this.val = val; }
    Node(int val, Node prev, Node next) { this.val = val; this.prev = prev; this.next = next; }
}

Intuition. In a singly linked list, deleting the head is just “return the second node”. A doubly linked list adds one obligation: the second node currently points back at the first through prev, and after the deletion it is the head, so that link must become null. Leaving it in place would make the deleted node reachable by walking backward, and the list would no longer be well formed. Everything else is untouched, so the operation stays O(1).

Algorithm.

  1. If the list is empty or has one node, the result is the empty list; return null.
  2. Let newHead = head.next.
  3. Set newHead.prev = null.
  4. Set head.next = null to detach the removed node.
  5. Return newHead.
static Node deleteHead(Node head) {
    if (head == null || head.next == null) return null;    // empty or single node: the list becomes empty
    Node newHead = head.next;
    newHead.prev = null;                                    // the new head has nothing before it
    head.next = null;                                       // detach the old head completely
    return newHead;
}

Complexity. Time O(1), space O(1).

Dry run on 1 <-> 2 <-> 3:

step head newHead newHead.prev list from newHead
guard [1] - - -
read next [1] [2] [1] 2 <-> 3, but backward walk reaches 1
clear prev [1] [2] null null <- 2 <-> 3 -> null
detach [1], links null [2] null unchanged

The single-node case is folded into the guard. With head.next == null, the only node is removed and null is the correct answer; without the guard, newHead.prev would dereference null. The test file asserts after rest = deleteHead(first) that first.next == null, first.prev == null, and rest.prev == null.

As usual the caller must store the result: head = deleteHead(head);.

Approach 2: Delete any node you hold

Intuition. Deleting the head is a special case of the operation that makes doubly linked lists worth their extra link: delete a node given only a reference to it, in O(1). The predecessor is target.prev, the successor is target.next, and the two must be made to bypass target in both directions. If there is no predecessor, target was the head and the successor becomes the new head.

Algorithm.

  1. Let before = target.prev and after = target.next.
  2. If before != null, set before.next = after; otherwise the new head is after.
  3. If after != null, set after.prev = before.
  4. Clear both links of target.
  5. Return the (possibly new) head.
static Node deleteNode(Node head, Node target) {
    Node before = target.prev, after = target.next;
    if (before != null) before.next = after;    // bypass target going forward
    else head = after;                          // target was the head
    if (after != null) after.prev = before;     // bypass target going backward
    target.prev = null;
    target.next = null;
    return head;
}

Complexity. Time O(1), space O(1).

With target == head, before is null, so the head becomes after, and after.prev is set to before, which is null: exactly the two effects of Approach 1. The tests run deleteNode(head, head) against deleteHead(head) on every non-empty input and require identical results. In a singly linked list this operation would cost O(n), because the predecessor can only be found by scanning from the head.

Generalisation: delete the k-th node

Intuition. With deleteNode available, deleting by position reduces to finding the node. Unlike a singly linked list, there is no need to stop on node k - 1, because the target’s own prev link gives us the predecessor.

Algorithm.

  1. If the list is empty or k < 1, return it unchanged.
  2. Walk target from the head for k - 1 steps; if it becomes null, there is no k-th node, return the head unchanged.
  3. Return deleteNode(head, target).
static Node deleteAtPosition(Node head, int k) {
    if (head == null || k < 1) return head;
    Node target = head;
    for (int i = 1; i < k && target != null; i++) target = target.next;  // walk to the k-th node
    if (target == null) return head;                                      // fewer than k nodes
    return deleteNode(head, target);
}

Complexity. Time O(k), space O(1). The tests check k = 1 against deleteHead, k = n against deleteTail, and confirm that k = 0 and k = n + 1 leave the list untouched.

Deleting the tail, for contrast

Intuition. Reaching the tail from the head is still a full walk, so the operation is O(n). What the prev link buys is that once we are on the tail, the second-last node is tail.prev; a singly linked list would have had to stop one node early with a more delicate loop condition.

Algorithm.

  1. If the list is empty or has one node, return null.
  2. Walk tail until tail.next == null.
  3. Set tail.prev.next = null so the second-last node becomes the tail, clear tail.prev, and return the head.
static Node deleteTail(Node head) {
    if (head == null || head.next == null) return null;
    Node tail = head;
    while (tail.next != null) tail = tail.next;
    tail.prev.next = null;                                   // the second-last node becomes the tail
    tail.prev = null;
    return head;
}

Complexity. Time O(n), space O(1). With a maintained tail reference it would be O(1), which is why deques and LRU caches keep one.

Edge cases and pitfalls