Insert a node at the head of a doubly linked list

You're warming up for a technical screen and the interviewer asks you to insert a node at the head of a doubly linked list. It sounds straightforward, and it is, but the small details around pointer management are exactly what separate a clean solution from one riddled with null pointer bugs. This problem is a staple for early-round interviews because it tests whether you truly understand how doubly linked structures maintain their bidirectional references.

TL;DR

Create a new node, point its next to the current head, update the old head's previous to the new node, and return the new node. If the list is empty, just return the new node. Both time and space complexity are O(1) since no traversal or auxiliary storage is required.

Why This Problem Matters

Doubly linked list insertion at the head is one of the foundational operations you need to internalize before tackling harder problems like implementing an LRU cache or reversing a doubly linked list. The operation itself is simple, but getting the pointer updates in the right order is a skill that transfers directly to more complex linked list manipulations.

Doubly Linked Lists: A Quick Refresher

A doubly linked list extends the singly linked list by adding a previous pointer to each node. This means you can traverse the list in both directions, and you can delete any node in O(1) time if you have a direct reference to it.

Each node in a doubly linked list has three fields:

• data: The value stored in the node
• next: A reference to the next node (or null for the tail)
• previous: A reference to the previous node (or null for the head)

The head node's previous is always null, and the tail node's next is always null. This bidirectional linking is what makes doubly linked lists more versatile than their singly linked counterparts, at the cost of an extra pointer per node.

Understanding the Problem

Given the head DoubleLinkListNode of a doubly linked list and an integer n, insert a new node containing n at the front of the list and return the new head.

Consider the doubly linked list [1, 2]:

After calling insertAtHead(head, -1), the list becomes [-1, 1, 2]:

Edge Cases to Consider

1. Empty list (null head): Return the new node as the sole element
2. Single-node list: Insert before the existing node, updating its previous
3. Large list: The operation is always O(1) regardless of size

Solution Approach

The algorithm has three parts:

1. Create a new node with the given value
2. If the list is empty, return the new node immediately
3. Otherwise, wire up the pointers: new node's next to old head, old head's previous to new node

The order of pointer updates matters. You must set newNode.next = head before updating head.previous = newNode. If you did it the other way around, you wouldn't lose any data in this case, but building the habit of updating the new node first before modifying existing nodes helps avoid bugs in more complex linked list operations.

Step-by-Step Walkthrough

Starting with the list [1, 2, 3], let's insert 0 at the head.

Step 1: Create the new node

We allocate a new DoubleLinkListNode with data = 0. Its previous and next are both null at this point.

Step 2: Point new node's next to the old head

Set newNode.next = head. The new node now links forward to node 1.

Step 3: Point old head's previous to the new node

Set head.previous = newNode. Node 1 now links backward to node 0. The doubly linked structure is complete.

Return newNode as the new head of the list.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public DoubleLinkListNode insertAtHead(DoubleLinkListNode head, int n) {
    // Create a new node with the given value
    DoubleLinkListNode newNode = new DoubleLinkListNode(n);

    // If the list is empty, the new node is the entire list
    if (head == null) {
      return newNode;
    }

    // Wire up the forward link
    newNode.next = head;
    // Wire up the backward link
    head.previous = newNode;

    // The new node is now the head
    return newNode;
  }
}

The solution handles both the empty list case and the general case cleanly. The null check for head is essential. Without it, head.previous = newNode would throw a null pointer exception on an empty list.

Handling the Empty List

When head is null, there is no existing node to link back to. The new node simply becomes a standalone element with both pointers set to null.

Inserting Before a Single Node

For a list containing only [5]:

After insertAtHead(head, 10):

The new node's next points to 5, and 5's previous points back to 10. Both the forward and backward links are correctly established.

Complexity Analysis

Time Complexity: O(1)

Every operation in this method runs in constant time:

• Node creation: O(1)
• Null check: O(1)
• Two pointer assignments: O(1)

No loops, no recursion, no traversal. The list could have 5 nodes or 5 million, and the operation takes the same amount of time.

Space Complexity: O(1)

We allocate exactly one new node regardless of the input size. No auxiliary data structures are used.

Common Pitfalls

1. Forgetting the null check: Attempting to set head.previous when head is null causes a null pointer exception. Always handle the empty list case first.

2. Not updating the previous pointer: If you only set newNode.next = head but skip head.previous = newNode, forward traversal works fine but backward traversal breaks silently. This is a particularly tricky bug because many test cases only check forward traversal.

3. Returning the wrong node: The new node is the new head. Returning the old head parameter means the caller loses access to the inserted element.

Interview Tips

When solving this in an interview:

1. Clarify the node structure: Ask whether the node has previous and next fields, and confirm their naming convention. Some implementations use prev instead of previous.

2. Draw it out: Sketch a small list (2-3 nodes) and show how each pointer changes. This demonstrates clear thinking and makes it easy to verify correctness.

3. Mention the edge cases explicitly: State that you're handling the empty list case before the interviewer asks about it.

4. Discuss tradeoffs: If the interviewer asks why doubly linked lists exist, mention O(1) deletion with a direct reference and bidirectional traversal, at the cost of extra memory per node.

5. Anticipate follow-ups: Be ready to discuss insertion at the tail, deletion by value, or how doubly linked lists power LRU cache implementations.

Key Takeaways

• Inserting at the head of a doubly linked list requires exactly two pointer updates: newNode.next = head and head.previous = newNode. Both must happen for the bidirectional structure to remain intact.
• Always check for a null head before accessing its fields. The empty list is the most common source of null pointer exceptions in linked list problems.
• This O(1) operation is the building block for more complex data structures like LRU caches, which combine a doubly linked list with a hash map for O(1) access, insertion, and deletion.
• The order of pointer updates (new node first, then existing nodes) is a good habit that prevents data loss in more complex linked list operations.

Related Problems and Practice

Once you're comfortable with head insertion, these related problems build on the same pointer manipulation skills:

• Insert a node at the tail of a doubly linked list
• Delete a node from a doubly linked list
• Reverse a doubly linked list
• Implement an LRU cache

This problem and hundreds of others are available on Firecode, where spaced repetition helps you build lasting muscle memory for these fundamental operations. Whether you're just starting with linked lists or brushing up before an interview, consistent practice with pointer manipulation problems pays dividends across your entire preparation.

Solutions in Other Languages

JavaScript

const DoubleLinkListNode = require("./DoubleLinkListNode");

class Solution {
  insertAtHead(head, n) {
    const newNode = new DoubleLinkListNode(n);

    if (head === null) {
      return newNode;
    }

    newNode.next = head;
    head.previous = newNode;

    return newNode;
  }
}

Python

class Solution:
    def insert_at_head(self, head: DoubleLinkListNode, n: int) -> DoubleLinkListNode:
        new_node = DoubleLinkListNode(n, None, head)

        if head:
            head.previous = new_node

        return new_node

The Python solution takes a slightly different approach by passing head directly as the next parameter in the constructor, eliminating a separate assignment step.

TypeScript

class Solution {
  insertAtHead(head: DoubleLinkListNode | null, n: number): DoubleLinkListNode | null {
    const newNode = new DoubleLinkListNode(n);

    if (head === null) {
      return newNode;
    }

    newNode.next = head;
    head.prev = newNode;

    return newNode;
  }
}

C++

#include "DoubleLinkListNode.h"

class Solution {
public:
  DoubleLinkListNode *insertAtHead(DoubleLinkListNode *head, int n) {
    auto *newNode = new DoubleLinkListNode(n);

    if (head == nullptr) {
      return newNode;
    }

    newNode->next = head;
    head->previous = newNode;

    return newNode;
  }
};

Go

package solution

import . "firecode.io/custom_types"

func (s *Solution) InsertAtHead(head *DoubleLinkListNode, n int) *DoubleLinkListNode {
  newNode := &DoubleLinkListNode{Data: n}

  if head == nil {
    return newNode
  }

  newNode.Next = head
  head.Previous = newNode

  return newNode
}

Scala

class Solution {
  def insertAtHead(head: DoubleLinkListNode, n: Int): DoubleLinkListNode = {
    val newNode = DoubleLinkListNode(n)

    if (head == null) return newNode

    newNode.next = head
    head.previous = newNode

    newNode
  }
}

Kotlin

class Solution {
  fun insertAtHead(head: DoubleLinkListNode?, n: Int): DoubleLinkListNode? {
    val newNode = DoubleLinkListNode(n)

    if (head == null) {
      return newNode
    }

    newNode.next = head
    head.prev = newNode

    return newNode
  }
}

Ruby

class Solution
  def insert_at_head(head, n)
    new_node = DoubleLinkListNode.new(n)

    if head.nil?
      return new_node
    end

    new_node.next = head
    head.prev = new_node

    new_node
  end
end

Swift

class Solution {
    func insertAtHead(_ head: DoubleLinkListNode?, _ n: Int) -> DoubleLinkListNode? {
        let newNode = DoubleLinkListNode(n)

        if head == nil {
            return newNode
        }

        newNode.next = head
        head!.previous = newNode

        return newNode
    }
}

C#

public class Solution {
    public DoubleLinkListNode? insertAtHead(DoubleLinkListNode? head, int n) {
        var newNode = new DoubleLinkListNode(n);

        if (head == null) {
            return newNode;
        }

        newNode.next = head;
        head.previous = newNode;

        return newNode;
    }
}

PHP

class Solution {
    public function insertAtHead(?DoubleLinkListNode $head, int $n): DoubleLinkListNode {
        $newNode = new DoubleLinkListNode($n);

        if ($head === null) {
            return $newNode;
        }

        $newNode->next = $head;
        $head->previous = $newNode;

        return $newNode;
    }
}