Insertion in a Singly Linked List

By now, you understand how traversal works and why it is necessary in a singly linked list. The next important operation is insertion, which allows new nodes to be added to the list.

Insertion in a linked list is different from insertion in an array. Instead of shifting elements, insertion is performed by updating references between nodes. Understanding how these references change is important for implementing insertion correctly and analyzing its time complexity.

Linked list insertion

Insertion means adding a new node to a singly linked list. Unlike arrays, insertion does not require shifting elements, but it still requires careful pointer updates so the list remains connected.

Insertion is usually discussed in three common cases:

1. Insertion at the beginning

2. Insertion at the end

3. Insertion at a specific position

Before implementing these cases, it helps to remember one rule: insertion is done by changing next references. If the references are updated in the wrong order, part of the list can become unreachable.

Insertion at the beginning

Insertion at the beginning is the most direct case because only the head reference needs to change.

This insertion takes two pointer updates:

• The new node’s next points to the current head.

• The head is updated to point to the new node.

The following interactive visualizer shows the step-by-step insertion at the beginning of a linked list.

Java implementation

The method below implements insertion at the beginning of the list.

• Time complexity: Insertion at the beginning takes $O(1)$ ...