Linked Lists: Pointers, Nodes, and Traversal

May 7, 20268 min read

data-structureslinked-listpatterns

If arrays are the first data structure you learn, the linked list data structure is almost always the second. And it teaches you something arrays never do: that data does not have to live in one contiguous block. Nodes can be scattered anywhere in memory, connected only by pointers.

That mental shift from "everything in a row" to "things connected by references" is the foundation for trees, graphs, and most of the more advanced structures you will encounter later. Linked lists are where that journey starts.

What is a linked list?

A linked list is a sequence of nodes where each node stores two things: a value and a pointer (or reference) to the next node. The first node is called the head. The last node points to null, signaling the end of the list.

Unlike arrays, linked list nodes are not stored in consecutive memory locations. Each node is its own object, and the next pointer is the only thing tying them together. There is no index. If you want to reach the fifth element, you have to start at the head and follow four pointers.

Here is what a basic node looks like in Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

That is the entire structure. A value and a pointer. Everything else in linked list problems is just manipulating these two fields.

Singly vs doubly linked list

There are two main flavors of linked list, and the difference comes down to how many pointers each node carries.

Singly linked lists have one pointer per node. Doubly linked lists add a backward pointer, enabling traversal in both directions.

Singly linked list

Each node has one pointer: next. You can only move forward. If you are at node 7 and you want to go back to node 3, tough luck. You have to start over from the head.

This is the version you will see in most interview problems. It is simpler, uses less memory per node, and the pointer manipulation is already tricky enough.

Doubly linked list

Each node has two pointers: next and prev. You can move both forward and backward. This costs extra memory per node, but it lets you do things that are awkward or impossible with a singly linked list.

class DoublyListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

The classic use case for a doubly linked list is the LRU Cache, where you need to both access and remove nodes from the middle of the list in O(1) time. The prev pointer makes removal trivial because you do not need to find the previous node first.

When an interview problem says "linked list" without further qualification, assume singly linked. If the problem requires backward traversal or O(1) deletion from the middle, think doubly linked.

Operations and time complexity

Understanding the complexity of each operation is what helps you decide whether a linked list is the right tool for the job.

Original list: 3 -> 7 -> 9 -> null

We want to insert value 5 after node 7.

Insert: create node 5, point it to 9, then point 7 to 5

Two pointer updates. O(1) once you have a reference to the target node.

Result: 3 -> 7 -> 5 -> 9 -> null

The new node is wired in. No shifting required, unlike an array.

Delete: remove node 5 from 3 -> 7 -> 5 -> 9 -> null

Point 7's next directly to 9, bypassing 5. O(1) once you have the previous node.

Result: 3 -> 7 -> 9 -> null

Node 5 is gone. The list is shorter, no elements were shifted.

Operation	Linked List	Array
Access by index	O(n)	O(1)
Search for value	O(n)	O(n)
Insert at head	O(1)	O(n)
Insert at tail (with tail pointer)	O(1)	O(1) amortized
Insert at arbitrary position (given node)	O(1)	O(n)
Delete (given node reference)	O(1) for doubly, O(n) for singly	O(n)
Memory overhead	Extra pointer(s) per node	None (contiguous)

The key takeaway: linked lists are fast at inserting and deleting when you already have a reference to the right node. They are slow at accessing elements by position. Arrays are the opposite.

Traversal

Every linked list operation starts with traversal. You walk the list one node at a time:

def traverse(head):
    curr = head
    while curr:
        print(curr.val)
        curr = curr.next

This is O(n) and it is unavoidable. There is no shortcut to the middle of a linked list.

Insertion

To insert a new node after a given node, you only need to update two pointers:

def insert_after(node, val):
    new_node = ListNode(val)
    new_node.next = node.next
    node.next = new_node

The order matters. If you set node.next = new_node first, you lose the reference to the rest of the list. Always point the new node forward before breaking the existing link.

Deletion

To delete a node, you point the previous node's next around it:

def delete_after(node):
    if node.next:
        node.next = node.next.next

In a singly linked list, you need a reference to the node before the one you want to delete. This is why many linked list problems use a dummy head node (also called a sentinel). It avoids special-casing deletion of the actual head.

dummy = ListNode(0)
dummy.next = head
# Now even the head can be deleted uniformly

The dummy head trick is one of the most useful patterns in linked list problems. It eliminates edge cases where the head itself needs to be removed, which simplifies your code significantly.

Practice linked list operations with SRS

When to use a linked list vs an array

This is the question that matters in practice. Arrays win most of the time because of cache locality and O(1) random access. But linked lists have real advantages in specific situations:

Use a linked list when:

You need frequent insertions or deletions at the beginning or middle of the sequence
You do not need random access by index
You are implementing a queue, deque, or LRU cache where insertion order matters
The size of your collection changes frequently and you want to avoid resizing

Use an array when:

You need to access elements by index
You are iterating through elements sequentially (cache performance matters)
Memory overhead per element matters
The size is relatively fixed or you can tolerate amortized resizing

In coding interviews, the choice is usually made for you by the problem. If the input is a linked list, you work with linked list operations. The real skill is knowing how to manipulate the pointers without breaking the chain.

Common linked list techniques

Most linked list problems use one or more of these core techniques:

1. Two pointers (fast and slow)

Use a slow pointer that moves one step at a time and a fast pointer that moves two steps. When the fast pointer reaches the end, the slow pointer is at the middle. This is the basis for cycle detection (Floyd's algorithm) and finding midpoints.

2. Pointer reversal

Walk through the list and flip each next pointer to point backward. This is the core of Reverse Linked List and shows up as a subroutine in many harder problems.

3. Dummy head

Create a fake node before the real head. This eliminates the need for special-case logic when the head might change.

4. Two-pointer gap

Send one pointer ahead by N steps, then move both pointers together. When the leading pointer hits the end, the trailing pointer is exactly N steps from the end. This powers Remove Nth Node From End.

Essential linked list problems

These six problems cover the most important linked list techniques. If you can solve all of them from scratch, you have a solid foundation for any linked list question that comes up in an interview.

Reverse Linked List (LeetCode 206) - The foundational pointer manipulation problem. If you cannot do this in your sleep, practice it until you can.
Linked List Cycle (LeetCode 141) - Detect whether a cycle exists using Floyd's tortoise and hare algorithm. Teaches the fast/slow pointer technique.
Palindrome Linked List (LeetCode 234) - Combines finding the midpoint (fast/slow) with reversal. A great test of whether you can chain techniques together.
Remove Nth Node From End of List (LeetCode 19) - The two-pointer gap technique in action. Also a good exercise in using dummy head nodes.
LRU Cache (LeetCode 146) - The most famous design problem. Combines a hash map with a doubly linked list for O(1) get and put operations.
Merge Sorted Array (LeetCode 88) - While this one uses arrays, the merging logic is identical to merging two sorted linked lists. Understanding the pointer dance here transfers directly to linked list merge problems.

Drill these problems with spaced repetition

Common mistakes

These are the bugs that come up most often in linked list problems:

1. Losing the reference to the next node. When you reassign curr.next, whatever was there before is gone. If you did not save it first, you have broken the chain and cannot continue traversing. Always save before you overwrite.

2. Forgetting to handle the empty list. If head is None, your code should not crash. Check for it explicitly at the top of your function.

3. Off-by-one with the dummy head. When you use a dummy node, remember to return dummy.next, not dummy. The dummy is not part of the real list.

4. Not updating the head after modification. If you delete or reverse the first node, the head changes. If you return the old head, your answer is wrong.

5. Infinite loops from bad pointer updates. If you accidentally create a cycle (say, by not setting the last node's next to null after a reversal), your traversal will never terminate.

If your linked list solution is running forever in testing, you almost certainly have an accidental cycle. Add a print statement inside your loop to see if you are visiting the same node repeatedly. Then check your pointer assignments for the node that should be pointing to null but is not.

Building real fluency

Reading about the linked list data structure is one thing. Being able to reverse a list, detect a cycle, and merge two sorted lists under interview pressure is something else entirely. The pointer manipulations are simple individually, but getting the order of operations right when you are nervous takes practice.

The building block approach works well here. The core operations (traverse, insert, delete, reverse a pointer) are small and self-contained. Once each one is automatic, you can combine them to solve harder problems without getting tangled up in the details.

Spaced repetition locks in the muscle memory. You type the reversal loop today, again in three days, again next week. After a few cycles, the save-reverse-advance pattern is second nature. You stop thinking about which variable to update first and just write it.

Reverse Linked List - The pointer swap technique, explained step by step with visual walkthroughs
Linked List Cycle - Floyd's tortoise and hare algorithm for O(1) space cycle detection
LRU Cache - The classic design problem combining a hash map with a doubly linked list
Stack Patterns - Stacks are essentially singly linked lists with restricted access, and the two often appear in the same problem families

CodeBricks breaks linked list problems into their reusable building blocks: the reversal loop, the fast/slow pointer, the dummy head pattern, and the two-pointer gap. You type each piece from scratch, and the spaced repetition scheduling adapts to how well you remember each one.

Start drilling linked list patterns today

New to data structures? Start with our visual What is an Algorithm? guide to build your foundation.