Inserting Nodes into a Linked List

Traversal moves through a linked list by following next pointers from the head until null is reached.

Programming

Interactive lab

Try it: Linked List

How a singly linked list stores values in separate nodes joined by next pointers, and how inserting or deleting only rewires pointers.

How it works

HEAD points at the first node; each node holds a value and a pointer to the next node; the last node points to NULL.
To insert, create a node, store its value, point it at its successor, then point its predecessor (or HEAD) at it.
To delete, walk to the node and make its predecessor skip over it.
Searching means following next pointers from HEAD until the value or NULL is reached.

Default run (9 steps): HEAD → 10 → 20 → 30 → NULL. 3 of 10 nodes. Choose an operation. Example: append 40. … Done: HEAD → 10 → 20 → 30 → 40 → NULL.

Educational simulation

Loading the simulation…

Walking a List Without Losing Its Front

Suppose you need to print every item in a linked list. A natural first attempt is to use the head variable itself as the moving pointer: keep stepping head forward to the next node, print the item along the way, and stop when head becomes null. The loop looks clean, and it seems to do exactly what you want. This article explains why that approach is a misconception, and what to do instead. The same traversal pattern then becomes the foundation for inserting a new node into a sorted list, which is the main task of this lesson.

What do you think happens?

Imagine a list whose head variable has been used as the walking pointer, so that head moves forward one node at a time until it reaches the end. Once the loop finishes, what can you still reach?

Reveal answer

Answer:

Nothing in the list can be reached through head any more. Advancing head during a walk leaves the program with no way to reach the list afterward.

The head variable is the program's only doorway into the list. Every operation that needs the list, including traversal, starts from that doorway. If the doorway itself is moved, the way back to the front of the list disappears.

Why head Must Stay Fixed

The head variable is the only access point to the list. The core correction is that head must keep pointing to the first node for the whole time the list is in use. Because of this, the walking has to be done with a different variable. A second variable, called runner in this material, receives a copy of head at the start, so both variables refer to the first node. From that moment on, only runner moves, while head stays where it is.

When a copy of head is made, does it point to the same node as head, and what happens to the list if only the copy moves?

Read the diagram as a picture of two references and one chain. Both head and runner point at node A at the start. Moving runner along the next links walks the chain without touching head. If head were moved instead, the program would lose its only reference to node A, and the remaining nodes would be unreachable from the program's point of view.

The Three Moving Parts of a Traversal

The standard traversal has three moving parts. First, a runner variable receives a copy of head, so both variables refer to the first node at the start. Second, the loop repeatedly processes the item in the node that runner currently refers to. Third, at the end of each pass, runner is advanced by following its next pointer, so it refers to the following node. The loop stops when runner becomes null, which is the marker for the end of the list.

java

Node runner = head;
while (runner != null) {
    System.out.println(runner.item);
    runner = runner.next;
}

Node runner = head;
while (runner != null) {
    System.out.println(runner.item);
    runner = runner.next;
}

Output

A
B
C

Walk through it

1
Line 1 makes runner a copy of head. Both now refer to the first node.
2
Line 2 tests runner for null. While it is not null, the body runs.
3
Line 3 processes the current node's item, here printing it.
4
Line 4 moves runner to the following node. When the last node is passed, runner becomes null and the loop ends.

Notes on the code

runner starts as a copy of head, so it refers to the first node
the loop condition tests runner for null before every pass
the body processes the item in the node that runner refers to
runner is advanced by following next, and head is never assigned

The output shown assumes a list whose three nodes hold the strings A, B, and C in that order. The loop visits the nodes in list order, so the strings print in the same order they appear in the list. Notice which variable is allowed to change, which is runner, and which must not, which is head.

Tracing an Empty List Through the Same Loop

An empty list is represented by a null head pointer. The traversal loop needs no special branch for this case. runner starts as null, the loop condition is false on its first check, and the body never executes. Nothing is dereferenced, so no error occurs. The null test in the loop condition is what makes the same code safe whether the list has zero nodes or many.

Worked example

Running the traversal on an empty list

head is null because the list has no nodes. Trace the traversal loop from the previous section.

1
Copy head
runner = head assigns null to runner, since head is null.
2
First condition check
runner != null is false, so the loop condition fails immediately.
3
Body
The body never runs, so nothing is printed and runner.item is never read.
4
Outcome
The loop ends with no error. The empty list was handled without a special branch.

Result

The same traversal loop completes safely with no output for an empty list.

Why Sorted Insertion Is Harder

A common first guess about adding to a linked list is that the new item always goes at one of two places: the front of the list or the back. That guess works for some data structures, but it fails as soon as the list has to stay in a particular order. In the StringList class described in this material, the items inside the nodes are kept in increasing order. So a new item cannot simply be attached wherever is convenient. It has to go where it fits the ordering, and that place is often somewhere in the middle of the list.

Definition

Insertion into a sorted linked list must place the new node where its value belongs, which is often in the middle of the list rather than at either end.

When a new item goes into the middle of the list, it must be placed between two existing nodes. To manage this, the method uses three references. One variable, previous, refers to the node that will sit on the left of the new node. Another, runner, refers to the node that will sit on the right. A third, newNode, refers to the node being added. Together they describe a local rearrangement of three nodes.

Handling the Empty and Insert-at-Head Cases

Before any links are changed, the insertion method has to decide which of three situations applies. If the list is empty, the new node becomes the head. If the new item is not greater than the first item in the list, it must go in front of the current head. Otherwise, the new item belongs somewhere after the first node, and the list must be searched to find its position. The diagram below shows this decision order.

What is the decision order that checks for an empty list or a new smallest value before the search loop runs, and which branch skips the loop entirely?

The simplest case happens when the new item belongs before the first node. Two steps handle it. First, the new node is pointed at the old head, so it does not lose the rest of the list. Second, the head reference is moved to the new node, making it the first node of the list. The order of these two lines is important. If head were changed first, the reference to the old head would be lost before newNode.next could be set.

Searching for the Insertion Point

When the new item belongs after the first node, the list has to be searched. The search uses two references that move together. previous starts at head, and runner starts at head.next, which is the second node. Each step of the loop moves previous forward to runner, then moves runner forward along the next pointer. The loop keeps going while runner is not null and the item at runner is still less than the new item. When it stops, previous and runner are the two nodes on either side of the insertion point.

Code walkthrough

void insert(String insertItem) {
    Node newNode = new Node(insertItem);
    if (head == null) {
        head = newNode;
        return;
    }
    if (insertItem.compareTo(head.item) <= 0) {
        newNode.next = head;
        head = newNode;
        return;
    }
    Node previous = head;
    Node runner = head.next;
    while (runner != null && runner.item.compareTo(insertItem) < 0) {
        previous = runner;
        runner = runner.next;
    }
    newNode.next = runner;
    previous.next = newNode;
}

1
Create the node that holds the new item.
2
If the list is empty, make newNode the head and stop.
3
If the new item is not greater than the first item, point newNode at the old head, make it the head, and stop.
4
Otherwise start previous at head and runner at head.next.
5
Advance both while runner is not null and runner's item is still less than the new item.
6
Link newNode to runner first, then link previous to newNode.

the empty-list check runs before any comparison
the insert-at-head branch returns before the search loop
the runner != null test stops the search at the end of the list
the splice sets newNode.next before previous.next

The condition runner != null is essential. Without it, the loop would eventually move runner past the last node, where next is null, and the next comparison would have no node to examine. The loop also stops as soon as it reaches an item that is not less than insertItem, because that is the place where the new node belongs before.

Splicing newNode Between previous and runner

The insertion itself has two parts. First, the existing link from previous to runner has to be broken. Then two new links are added: one from previous to newNode, and one from newNode to runner. Breaking a link without adding the replacement links would leave part of the list unreachable, so the order of these steps matters. Every insertion into a linked list works by updating the next pointers of the nodes that sit next to the new one.

After newNode is linked in, which next pointers change, and in what order must they be updated so the list stays connected and no node is lost?

The left panel shows the list before the splice, with a direct link from A to C. The right panel shows the result. The link from A to C has been replaced by a link from A to B and a link from B to C. Setting newNode.next to runner before changing previous.next keeps runner reachable, which is the same ordering concern seen at the head. Once previous.next points at newNode, the old link is gone and every node is still reachable from head.

Worked example

Inserting B into the list A then C

A sorted list holds A and C. Insert B so that the list stays in increasing order.

1
Decide the case
B is not less than or equal to the head item A, so it does not go at the head. The list is not empty either, so the search runs.
2
Set the references
previous starts at A and runner starts at C, since runner starts at head.next.
3
Search
runner refers to C, and C is not less than B, so the loop stops with previous at A and runner at C.
4
Link newNode to runner
newNode.next is set to C, so the rest of the list is preserved.
5
Link previous to newNode
previous.next is set to B, which replaces the old link from A to C.

Result

The list reads A, B, C, still sorted, and every node is reachable from head.

Mistakes Beginners Make When Inserting

Common mistake
Walking the list with head itself
What it looks like
```
while (head != null) { print(head.item); head = head.next; }
```
Why it fails
Once head is advanced, the program has no way to reach the front of the list again.
Do this instead
Copy head into a runner variable and move only runner.
Common mistake
Changing head before saving the old head
What it looks like
```
head = newNode; newNode.next = head;
```
Why it fails
The reference to the old head is lost before newNode.next is set, so the rest of the list is unreachable.
Do this instead
Set newNode.next = head first, then set head = newNode.
Common mistake
Breaking the old link before adding the new ones
Why it fails
Removing the link from previous to runner without adding the replacement links leaves part of the list disconnected.
Do this instead
Point newNode at runner, then point previous at newNode.
Common mistake
Dropping the null check in the search loop
What it looks like
```
while (runner.item < insertItem)
```
Why it fails
When runner moves past the last node, it becomes null and runner.item cannot be read.
Do this instead
Test runner != null in the loop condition before examining runner.item.
Common mistake
Comparing against head.item on an empty list
Why it fails
An empty list has no head node, so head.item cannot be read.
Do this instead
Check whether head is null before any comparison.

Practice: Tracing a Sorted Insert

MEDIUM

A sorted list holds the strings Apple, Mango, and Pear, in that order, with head referring to Apple. Trace the insertion of the string Banana. Name which branch runs, what previous and runner refer to when the loop stops, and the order in which the two links are changed.

Hints

Compare Banana with the head item first. Is Banana not greater than Apple?
Start previous at head and runner at head.next. Advance both while runner is not null and runner's item is less than Banana.
Link newNode to runner before linking previous to newNode.

Your attempt (not saved)

EASY

Predict the result of inserting Aardvark into the same list. Which branch runs, and does the search loop execute at all?