Linked ListsLesson 2

Singly Linked List Operations

Insert at head, tail, and middle. Delete a node. Search for a value. Reverse the list. All operations step by step.

What Is It?

Knowing what a linked list is is not enough — you need to be able to do things with it. That means inserting new nodes, removing old ones, searching for values, and even reversing the whole chain.

Every operation comes down to one idea: find the right node, then update its next pointer.

Here is what we will cover, along with how fast each one is:

Insert at head — O(1) — instant, no matter how long the list
Insert at tail — O(n) — must walk to the end first
Insert at position — O(n) — must walk to the right spot
Delete head — O(1) — instant
Delete by value — O(n) — must search first
Search — O(n) — must check each node
Reverse — O(n) — must visit every node once

Analogy

Think of a singly linked list as a conga line at a party. Each person has their hands on the shoulders of the person in front of them (the next pointer). The person at the front is the head.

Insert at head: A new person steps to the very front and puts their hands on the old leader's shoulders. Instant — O(1).
Insert at tail: A new person must walk to the very back of the line. The longer the line, the longer the walk — O(n).
Delete head: The front person leaves. The person behind them becomes the new leader. Instant — O(1).
Delete by value: You must walk the line to find the person, then the person behind them reaches forward to the person ahead. O(n) to find them.
Reverse: Everyone turns around and puts their hands on the person who was behind them. This requires careful coordination.

Insert at Head — O(1)

NEW

A new person walks up to the FRONT of the conga line
They place their hands on the old leader's shoulders
They are now the new head — no one else had to move

Instant — the line can be 1,000 people long and it still takes one step.

New dancer grabs the old leader's shoulders

Insert at Tail — O(n)

NEW

A new person wants to join at the BACK
They must walk past every single dancer to find the end
Only then can the last dancer reach back and let them join

The longer the line, the longer the walk — that is why it is O(n).

New dancer must walk the entire line to join at the back

Delete Head — O(1)

The person at the front decides to leave the conga line
The person behind them automatically becomes the new leader
No one else in the line needs to move or even notice

Instant — the rest of the line keeps moving as if nothing happened.

The front dancer simply steps out

Delete by Value — O(n)

Someone in the MIDDLE needs to leave (B left here)
You walk from the front checking each dancer until you find them
The person behind them reaches forward to grab the next person's shoulders

Finding the right person is the slow part — once found, the gap closes instantly.

Walk the line to find the person, then close the gap

Search — O(n)

You start at the front and ask each dancer: "Are you the one?"
You cannot skip ahead — you must check them in order
You stop when you find them or reach the end of the line

Just like the scavenger hunt — one clue at a time, no shortcuts.

Walk from the front, checking each dancer one by one

Reverse — O(n)

The DJ shouts: "REVERSE!" — everyone must turn 180 degrees
Each person lets go of the person ahead and grabs the one behind
The old tail becomes the new head — the whole line flips

Every dancer must participate — that is why it visits all n nodes.

Everyone turns around and grabs the person who was behind them

How It Works

INSERT at Head — O(1)

This is the fastest insertion. You create a new node, point it at the current head, and update head.

pseudocode

function insertAtHead(list, value):
    newNode = new Node(value)
    newNode.next = list.head
    list.head = newNode
    list.size = list.size + 1

Before: Head -> [20] -> [30] -> null

pseudocode

Step 1: Create newNode [10]
Step 2: newNode.next = head    =>  [10] -> [20] -> [30] -> null
Step 3: head = newNode

After: Head -> [10] -> [20] -> [30] -> null

Only 3 operations regardless of list size. That is why it is O(1).

INSERT at Tail — O(n)

You must walk to the last node, then attach the new node after it.

pseudocode

function insertAtTail(list, value):
    newNode = new Node(value)
    if list.head is null:
        list.head = newNode
    else:
        current = list.head
        while current.next is not null:
            current = current.next
        current.next = newNode
    list.size = list.size + 1

Before: Head -> [10] -> [20] -> [30] -> null

pseudocode

Walk: current = [10], then [20], then [30] (stop — current.next is null)
Attach: [30].next = newNode [40]

After: Head -> [10] -> [20] -> [30] -> [40] -> null

INSERT at Position — O(n)

To insert at position k (starting from 0), walk to the node at position k-1, then rewire.

pseudocode

function insertAtPosition(list, value, position):
    if position equals 0:
        insertAtHead(list, value)
        return
    newNode = new Node(value)
    current = list.head
    for i from 0 to position - 2:
        if current is null:
            error("Position out of bounds")
        current = current.next
    newNode.next = current.next
    current.next = newNode
    list.size = list.size + 1

Insert 25 at position 2:

Before: Head -> [10] -> [20] -> [30] -> [40] -> null

pseudocode

Walk to position 1: current = [20]
Step 1: newNode.next = current.next    =>  [25] -> [30]
Step 2: current.next = newNode         =>  [20] -> [25]

After: Head -> [10] -> [20] -> [25] -> [30] -> [40] -> null

Important: Step 1 must happen before Step 2. If you do Step 2 first, you lose the reference to [30] and everything after it — it is gone forever.

DELETE Head — O(1)

pseudocode

function deleteHead(list):
    if list.head is null:
        error("List is empty")
    value = list.head.data
    list.head = list.head.next
    list.size = list.size - 1
    return value

Before: Head -> [10] -> [20] -> [30] -> null

pseudocode

Step 1: Save value = 10
Step 2: head = head.next  (head now points to [20])

After: Head -> [20] -> [30] -> null

DELETE by Value — O(n)

To delete a node, you need the node before it so you can make it skip over the target.

pseudocode

function deleteByValue(list, target):
    if list.head is null:
        return false
    // Special case: target is at head
    if list.head.data equals target:
        list.head = list.head.next
        list.size = list.size - 1
        return true
    // General case: find the node BEFORE the target
    current = list.head
    while current.next is not null:
        if current.next.data equals target:
            current.next = current.next.next
            list.size = list.size - 1
            return true
        current = current.next
    return false   // not found

Delete value 20 from: Head -> [10] -> [20] -> [30] -> null

pseudocode

current = [10]
current.next.data = 20  =>  match!
current.next = current.next.next
[10].next = [30]

After: Head -> [10] -> [30] -> null

SEARCH — O(n)

pseudocode

function search(head, target):
    current = head
    index = 0
    while current is not null:
        if current.data equals target:
            return index
        current = current.next
        index = index + 1
    return -1   // not found

REVERSE — O(n) with Three Pointers

This is one of the most important linked list techniques. We use three pointers: prev, current, and next.

The idea: visit each node and flip its next pointer to point backward instead of forward.

pseudocode

function reverse(list):
    prev = null
    current = list.head
    while current is not null:
        next = current.next      // save next node before we lose it
        current.next = prev      // flip the pointer backward
        prev = current           // move prev forward
        current = next           // move current forward
    list.head = prev

Step-by-step on [10] -> [20] -> [30] -> null:

pseudocode

Start: prev=null, current=[10]
Step 1:
  next = [20]           // save [20] before we lose it
  [10].next = null      // flip: [10] now points backward (to nothing)
  prev = [10]
  current = [20]
Step 2:
  next = [30]           // save [30]
  [20].next = [10]      // flip: [20] now points back to [10]
  prev = [20]
  current = [30]
Step 3:
  next = null           // save null
  [30].next = [20]      // flip: [30] now points back to [20]
  prev = [30]
  current = null
Loop ends. head = prev = [30]

Result: Head -> [30] -> [20] -> [10] -> null

Examples

Example: Build a List and Reverse It

Build and Reverse a Linked List— Step-by-step list state after each operation

1 / 4

insertAtHead(30)

[0]

Example: Delete the Middle Element

Given [1] -> [2] -> [3] -> [4] -> [5], delete value 3:

pseudocode

current starts at [1]
current.next.data = 2, not 3. Move on.
current = [2]
current.next.data = 3, match!
current.next = current.next.next
[2].next = [4]

Result: [1] -> [2] -> [4] -> [5]

Common Mistakes

1. Forgetting the special case for head. When deleting or inserting at position 0, the head pointer itself must change. The general loop logic does not cover this — you need an explicit check at the top.

2. Rewiring pointers in the wrong order. During insertion, always set newNode.next BEFORE updating current.next. Doing it backwards severs the rest of the list.

3. Not saving `current.next` before reversing. In the reverse algorithm, once you flip current.next = prev, you can no longer reach the next node. You must save it in next first.

4. Off-by-one in position traversal. To insert at position k, stop at position k-1. Going one step too many puts the new node in the wrong place.

5. Not handling an empty list or single-node list. Operations like deleteHead and reverse need special handling when head is null or the list has only one node.

Best Practices

Return the value on delete. When deleting a node, return the data it contained. This is useful for stack and queue implementations built on linked lists.

Test edge cases first: empty list, single element, operation at the very beginning and very end. These are where most bugs hide.

Draw the pointers. Before coding any linked list operation, draw the before and after states with arrows. Identify exactly which pointers change and in what order.

Memorize the three-pointer reversal. It shows up constantly in interviews and is the foundation for more advanced problems like palindrome checking and reversing sublists.

Singly Linked Lists Doubly Linked Lists