☕ DSA Java Articles

Topics › Linked List › Learn Doubly LinkedList

Insert node before head in Doubly Linked List

Easy TUF ID 361 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a doubly linked list and an integer val. Create a new node holding val, place it in front of the current first node, and return the head of the resulting list. Both links must be correct afterwards: the new node’s next is the old head, and the old head’s prev is the new node. The list may be empty, in which case the new node is the whole list.

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 = 2 <-> 3 <-> 4, val = 1
answer = 1 <-> 2 <-> 3 <-> 4        // 1.next is 2, 2.prev is 1, 1.prev is null

Example 2

list = (empty), val = 5
answer = 5                           // prev and next are both null

Example 3

list = 9, val = 9
answer = 9 <-> 9                     // two distinct nodes with equal values

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, inserting at the head is one assignment: the new node points at the old head. A doubly linked list has a mirror invariant, a.next == b if and only if b.prev == a, so every forward link we create must be matched by a backward link. Here that means one extra assignment: the old head must point back at the new node. The new node’s own prev is null because it is now first, which the constructor already gives us.

Algorithm.

  1. Create node = new Node(val); its prev and next are null.
  2. Set node.next = head.
  3. If head is not null, set head.prev = node. On an empty list there is no old head to update.
  4. Return node as the new head.
static Node insertBeforeHead(Node head, int val) {
    Node node = new Node(val);
    node.next = head;
    if (head != null) head.prev = node;      // the old head now has a predecessor; skip when the list was empty
    return node;
}

Complexity. Time O(1): an allocation and at most two assignments. Space O(1) beyond the new node.

Dry run on 2 <-> 3 <-> 4 with val = 1:

step node.prev node.next old head’s prev result
create null null null -
forward link null [2] null 1 -> 2 <-> 3 <-> 4, broken backward
backward link null [2] [1] 1 <-> 2 <-> 3 <-> 4
return - - - head is [1]

After step 2 the list is reachable forward but not well formed: walking backward from the tail would stop at 2 without ever reaching 1. Step 3 restores the invariant. The test file verifies all three facts at once for a concrete pair of nodes: fresh.next == old, old.prev == fresh, and fresh.prev == null.

The caller must store the result, head = insertBeforeHead(head, 1);, since Java cannot reassign the caller’s variable from inside the method. Repeated insertion before the head reverses the insertion order: inserting 1, 2, 3, 4 gives 4 <-> 3 <-> 2 <-> 1.

Approach 2: Insert before any node you hold

Intuition. The head case is a special case of a more general O(1) operation that only a doubly linked list offers: insert before a node given just a reference to it. The prev link tells us the predecessor without a scan. The new node sits between before = target.prev and target, so four links must be set: the new node’s two, target.prev, and before.next. When before is null, target was the head and the new node becomes the new head.

Algorithm.

  1. Let before = target.prev.
  2. Create node = new Node(val, before, target); its links are already correct.
  3. Set target.prev = node.
  4. If before != null, set before.next = node; otherwise node is the new head.
  5. Return the (possibly new) head.
static Node insertBeforeNode(Node head, Node target, int val) {
    Node before = target.prev;
    Node node = new Node(val, before, target);          // prev = before, next = target
    target.prev = node;
    if (before != null) before.next = node;             // splice in between
    else head = node;                                   // target was the head, so node is the new head
    return head;
}

Complexity. Time O(1), space O(1). With target == head, this method does exactly what Approach 1 does, and the tests run it against the same expected output on every non-empty input.

Compare this with a singly linked list, where “insert before this node” costs O(n): you would have to walk from the head to find the predecessor. That one extra reference per node is what buys the constant-time edit.

Generalisation: insert before the k-th node

Intuition. Insertion before the head is k = 1 of inserting before the k-th node (1-based). For larger k, we walk to the k-th node and hand it to Approach 2. There is no need to stop one node early, as a singly linked list would require, because prev is available at the target.

Algorithm.

  1. If k < 1, the position does not exist; return the list unchanged.
  2. If k == 1, return insertBeforeHead(head, val).
  3. Walk target from the head for k - 1 steps. If it becomes null, there are fewer than k nodes; return the head unchanged.
  4. Return insertBeforeNode(head, target, val).
static Node insertBeforePosition(Node head, int k, int val) {
    if (k < 1) return head;                                               // no such position
    if (k == 1) return insertBeforeHead(head, val);
    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 insertBeforeNode(head, target, val);
}

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

Two boundary behaviours deserve attention. k = 1 always means “become the new head”, so it works even on an empty list and produces a one-node list. For k ≥ 2, the k-th node must exist: on a list of n nodes, k = n + 1 walks off the end and the list is returned unchanged, because there is no node to insert before. If you need “append”, that is a different operation, shown next. The tests cover k = 1 on an empty list, k = n + 1 and k = n + 2 on non-empty lists, and k = 0.

Insertion at the tail, for contrast

Intuition. Inserting at the tail requires reaching the tail, and with only a head reference that is a full walk. Once there, the same two-link pattern applies: the tail’s next points at the new node and the new node’s prev points at the tail.

Algorithm.

  1. Create the node. If the list is empty, it is the new head.
  2. Walk tail until tail.next == null.
  3. Set tail.next = node and node.prev = tail; return the unchanged head.
static Node insertAtTail(Node head, int val) {
    Node node = new Node(val);
    if (head == null) return node;
    Node tail = head;
    while (tail.next != null) tail = tail.next;
    tail.next = node;
    node.prev = tail;
    return head;
}

Complexity. Time O(n), space O(1). Keeping a separate tail reference makes it O(1), which is what deque and LRU-cache implementations do.

Edge cases and pitfalls