Handling Edge Cases in Linked List Insertion

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.

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…

Why Middle Insertion Is Harder

A common first guess about a linked list is that a new item always goes in one of two places: at the front or at the back. That guess works for some data structures. 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.

Adding at either end needs only one or two reference updates, because the end of the list is known without searching. A middle insertion is different. The method first has to find the right position, and then it has to rearrange the nodes on both sides of that position. The table below contrasts the two situations.

Situation	What must be known	Links that change	Extra work
Insert at the head	The current head reference	head moves to the new node; newNode.next points to the old head	No search
Insert at the tail	Where the last node is	The last node's next points to the new node	Reach the end of the list
Insert in the middle (sorted)	Which two nodes the new item sits between	The link from previous to runner is replaced by previous to newNode and newNode to runner	Search the list, then splice

Middle insertion adds a search and a three-node rearrangement on top of the work needed at either end.

Choosing Which Case Applies

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 flowchart shows this decision order. Notice that only the third branch enters the search loop.

When the list is empty or the new value belongs before the first node, which branch runs and why does it skip the search loop?

What do you think happens?

The list is empty, so head is null. Which branch of the decision order runs, and does the search loop run at all?

The search loop runs first, then the new node is placed
The new node becomes the head, and the search loop is skipped
The new item is compared with head.item, then the search loop runs

Reveal answer

Answer:

The new node becomes the head, and the search loop is skipped.

When head is null, the new node is the only node in the list, so it becomes the head. The check comes before any comparison, so head.item is never read.

Empty Lists and the Head Insertion

An empty list has no head node. Its head reference is null, and any attempt to compare against head.item would fail. For this reason the empty-list check is made first, before any comparison. When head is null, the new node is the only node in the list, so it becomes the head.

The simplest non-empty case is an item that belongs before the first node. The source gives two steps for 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. The order of these two steps matters. If head were changed first, the only reference to the old head would be lost before newNode.next could be set.

Worked example

Inserting 1 at the head of a list that starts with 4

The list currently holds 4, then 7, then 12, with head referring to the node holding 4. Insert 1 so that the list stays in increasing order.

1
Check for an empty list
head is not null, so the list has at least one node and the comparison can safely run.
2
Compare with the first item
1 is not greater than 4, so the new item belongs in front of the current head. The search loop is skipped.
3
Point newNode at the old head
Set newNode.next to the node holding 4. The rest of the list is still reachable through this link.
4
Move head to newNode
Set head to newNode. The list now reads 1, then 4, then 7, then 12.

Result

The list is 1, 4, 7, 12, and the old head is still reachable from the new first node.

Searching Safely with previous and runner

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 the 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 its 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.

As runner advances node by node, at what point does the loop stop, and what happens when the value is larger than every node?

The condition runner not 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 the new item, because that is the place where the new node belongs before. If the new value is larger than every item, the loop ends when runner becomes null, with previous pointing at the last node.

Edge case

Consider inserting 20 into the same list, 2, 5, 9. The search moves previous to 5, then to 9, and then runner becomes null. Both comparisons stop before any null node is examined, and previous holds 9, the last node. Splicing then points newNode at runner, which is null, so the new node becomes the last node.

Splicing the New Node into Place

Once previous and runner are in place, the splice uses the same idea as the head insertion. The insertion 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. The before-and-after diagram shows which next pointers change.

Which next pointers change, and in what order, so newNode sits between previous and runner without breaking the rest of the list?

newNode.next = runner
previous.next = newNode

newNode.next = runner
previous.next = newNode

Notes on the code

Line 1 links the new node to the node on its right before anything else changes.
Line 2 replaces the link from previous, so previous now points to newNode instead of runner.

Mistakes Beginners Make with Edge Cases

Most crashes in linked list insertion come from skipping one of the checks or taking the reference updates in the wrong order. The following mistakes are the ones the source identifies as the most common.

Common mistake
Comparing against head.item without checking for an empty list first
What it looks like
head is null, and the code reads head.item to decide where the new item goes.
Why it fails
An empty list has no head node, so there is no item to read and the comparison fails.
Do this instead
Test whether head is null before any comparison. If it is, make the new node the head.
Common mistake
Moving head before setting newNode.next
What it looks like
head is set to newNode, and then newNode.next is set to head.
Why it fails
After head has moved, the reference to the old head is gone, so newNode.next would point back to the new node itself.
Do this instead
Set newNode.next to the old head first, then move head to newNode.
Common mistake
Dropping the null check in the search loop
What it looks like
The loop runs while the item at runner is less than insertItem, with no test for runner being null.
Why it fails
When the new value is larger than every item, runner reaches the end and then becomes null, so the comparison has no node to examine.
Do this instead
Keep the loop condition runner not null in the test, so the search stops safely at the end.
Common mistake
Overwriting previous.next before newNode.next is set
Why it fails
The only reference to runner is lost, and the nodes after it become unreachable.
Do this instead
Set newNode.next to runner first, then set previous.next to newNode.
Common mistake
Assuming the new item always goes at the front or the back of the list

Practice Tracing an Insertion

MEDIUM

A sorted list holds 3, 8, 11, with head referring to the node holding 3. Insert 6. Trace the empty-list check, the head comparison, the search with previous and runner, and the splice. Name the two nodes that previous and runner end on, and list which next pointers change.

Hints

Start by checking whether head is null. It is not, so the comparison with the first item comes next.
Is 6 greater than 3? Yes, so the search loop runs. Start previous at 3 and runner at 8.
Keep advancing while runner is not null and runner's item is less than 6. Only one step is needed here.

Your attempt (not saved)

Key Takeaways

Middle insertion in a sorted linked list is harder than adding at the ends, because the correct position must be found by searching and then the nodes on both sides must be rearranged.
The empty-list check comes first, and the insert-at-head case sets newNode.next to the old head before moving head to newNode, so no part of the list is lost.
The search keeps previous and runner moving together, and the runner not null test stops the loop safely when the new value is larger than every item.
The splice sets newNode.next to runner before setting previous.next to newNode, which keeps the rest of the list reachable.