Insertion at doubly linked list

Given the head of a doubly linked list, a 0-based position p, and an integer x, insert a new node holding the value x immediately after the p-th node, then return the head of the updated list.

A doubly linked list node carries a value plus two links — prev (to the node before it) and next (to the node after it). Inserting in the middle means re-wiring those links so the newcomer is stitched in from both sides.

The position p is guaranteed to be valid, i.e. 0 <= p < size of the list.

Hints

· Stuck? Reveal one nudge at a time.

You are only adding one node — how much of the existing list actually needs to change?

Land on the node at index p first. The new node goes between it and whatever currently follows it.

It is a four-pointer handshake: new.next, new.prev, the successor's prev, and curr.next — set them in an order that does not lose the old successor.

Common doubts

It is 0-based. Position p refers to the node reached after p steps from the head, and the new node is inserted immediately after it.

Then curr.next is null and the new node becomes the tail — its next stays null and it simply hangs off the end.

In a doubly linked list every link is two-way. If you only fix the forward links, the list reads correctly going forward but is broken going backward, which shows up the moment something walks prev.

Interview follow-ups

· What an interviewer asks next.

Insert after the (p-1)-th node, or handle p = 0 as a special head-insert by pointing the new node's next at head and updating head's prev.

Drop every prev assignment — you only maintain next. Insertion is the same walk-then-splice, just half the pointers.

Fun facts

The whole trick is constant work — insertion into a linked list is O(1) once you are standing at the right spot; all the cost is in getting there.
This same four-pointer handshake powers the doubly linked list at the heart of an LRU cache, where nodes are spliced in and out of a usage list on every access.

Asked at

AmazonMicrosoftAdobeGoogle

Frequently Sometimes Occasionally

Example 1

Input: list = 2 <-> 4 <-> 5, p = 2, x = 6
Output: 2 <-> 4 <-> 5 <-> 6
The node at index 2 is `5`. Insert `6` right after it, so `6` becomes the new tail.

Example 2

Input: list = 1 <-> 2 <-> 3 <-> 4, p = 0, x = 44
Output: 1 <-> 44 <-> 2 <-> 3 <-> 4
The node at index 0 is `1`. Insert `44` right after it, between `1` and `2`.

Constraints

- 1 <= list size <= 10^4 - 0 <= p < list size - 0 <= x <= 10^4 - 0 <= node value <= 10^4

Inserting into a doubly linked list looks fiddly, but it is really just re-tying a few knots. Master the pointer dance once and it transfers to every DLL insert, delete, and reverse you will ever write.

Prerequisites

Before you start

· Concepts used directly in the solution.

Doubly linked list. Each node stores a value plus two links: prev to the node before and next to the node after.

Pointer reassignment. Changing a node's next/prev re-routes the chain — the order you reassign them in matters.

Linear traversal. Walking k steps with curr = curr.next to land on a node by index.

Understand the problem

Walk from the head until you reach the node at index p — call it curr. The new node must sit between curr and curr.next. That means the new node's prev points back at curr, its next points at curr's old successor, and both neighbors point back at the newcomer.

Worked example — list = 1 <-> 2 <-> 3 <-> 4, p = 0, x = 44

index:   0     1     2     3
         1  <-> 2  <-> 3  <-> 4

curr = node at index 0  ->  value 1
insert 44 between curr (1) and curr.next (2):

         1  <-> 44 <-> 2  <-> 3  <-> 4
         ^curr  ^new
answer:  1 44 2 3 4

Clarifying questions

A candidate who confirms the position rules before touching pointers signals they have been burned by off-by-one bugs before — that is seniority.

Questions to ask first

· Signals seniority before you write a line of code.

Indexing

“Is p 0-based, and do we insert after that node rather than before it?”

Off-by-one here flips every answer — after index p is very different from at index p.

Input validity

“Is p always a valid position inside the list?”

If p can point past the end, we need a decision for that case; the guarantee 0 <= p < size removes it.

Edge cases

“What if p is the last index — do we insert a new tail?”

Yes; curr.next is null there, so the newcomer becomes the tail and its next is null.

The ideal opening — say it like this

Before I start, let me confirm a couple of things about the position.

First — p is 0-based and I insert immediately after the p-th node, correct?

And p is always in range, so I never have to handle an out-of-bounds position?

Key observations

1Aha

Only a constant number of pointers ever change

No matter how long the list is, insertion touches just three nodes: curr (the p-th node), curr.next (its old successor, if any), and the new node. Four links get rewired; everything else is untouched.

before:   curr  <->  succ
after:    curr  <->  new  <->  succ

2Aha

Finding the spot is the only linear part

Landing on the p-th node costs O(p) steps of walking. The actual splice afterwards is O(1). So there is nothing to "optimize" in the relinking — the whole cost is the walk.

3Aha

Capture the old neighbor before you overwrite

Once you set curr.next = new, the pointer to the old successor is gone. So read curr.next into the new node first, then fix curr.next. Getting this order wrong silently drops the rest of the list.

Brute force vs optimal

	Brute force (rebuild)	Optimal (splice)
Time	O(n)	O(p)
Space	O(n)	O(1)
Reuses existing nodes

Both are correct; the optimal one just refuses to throw away the list it was handed. See the full code for each in the Approaches selector below.

Summary

Key takeaway

Doubly linked list insertion is a fixed four-pointer handshake: point the newcomer at its two neighbors, then point both neighbors back. Read the old successor before you overwrite it, and the rest is bookkeeping.

curr = walk head forward p steps
new.next = curr.next
new.prev = curr
if curr.next exists: curr.next.prev = new
curr.next = new
return head