Course contentsShow
← Java
Lesson 1024 of 2,87024. List ImplementationsFree lesson

Inserting Elements in the Middle

How linkBefore() traverses to position, updates four pointers to insert a node between two existing nodes.

Inserting Elements in the Middle

You'll learn how LinkedList's linkBefore() method navigates to a target position and surgically reconnects four pointers to insert a new node between two existing ones.

The Challenge of Middle Insertion

Adding to the beginning or end of a LinkedList is straightforward—you just update the head or tail. But what happens when you need to insert a node between two existing nodes? This requires finding the right position, then carefully rewiring connections so nothing gets lost.

How linkBefore() Works

The linkBefore() method performs middle insertion in two phases:

Phase 1: Traversal
First, LinkedList must find the node after which you want to insert. Since there's no array indexing, it walks through the chain node-by-node from either the head or tail (whichever is closer) until it reaches the target position.

Phase 2: Four-Pointer Update
Once at the right spot, the method creates a new node and updates exactly four pointers to splice it in:

  1. New node's prev → points to the node that was before the target
  2. New node's next → points to the target node (the one originally at this position)
  3. Previous node's next → now points to the new node instead of the target
  4. Target node's prev → now points back to the new node

Think of it like inserting a link into a chain: you must disconnect one connection, slide the new link in, then reconnect both sides.

Why Four Pointers?

Because LinkedList is doubly-linked, every insertion affects relationships in both directions. Miss even one pointer update, and you break the chain's integrity—nodes become orphaned or the list becomes unnavigable.

Key Takeaway:
Middle insertion in LinkedList uses linkBefore() to traverse to the target position, then atomically updates four pointers (two in the new node, one in each neighbor) to maintain doubly-linked integrity.