Linked List Data Structure: Nodes, Pointers, and Interview Patterns

Insert an element at position 0 of a 10 million element array. Watch everything shift right. Go ahead. I'll wait.

That's O(n) work just to put one value at the front. The whole array shuffles down one slot like a packed subway car where someone needs to get off at the first stop.

The linked list data structure solves a different problem. Elements can live anywhere in memory, no contiguous block required. Each element holds a pointer to the next one. No shuffling. No evictions. Just a chain of nodes with trust in their pointers.

That trade-off (fast insertions and deletions at the cost of slow random access) is why linked lists show up in real systems and in almost every coding interview.

The Node: The Only Building Block You Need

A linked list is made of nodes. Each node holds two things: a value and a pointer to the next node.

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

That's it. Seriously. The "list" is just a chain of these nodes strung together. The first node is called the head. The last node's next pointer is None, marking the end.

The whole structure lives in the pointers, not in any container. There is no array. No wrapper object hiding complexity. Just nodes pointing at other nodes, all the way down.

A list containing 1 → 2 → 3:

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

In memory, those three nodes can be scattered anywhere on the heap. The pointers stitch them into a logical sequence.

Linked list node diagram: three nodes connected by arrows, last pointing to None

Each box is a node. Left side is the value, right side is the pointer. The last node points to None.

Traversal Is the Price You Pay

To read elements, start at head and follow pointers until you hit None:

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

Every traversal is O(n), and there is no shortcut. Unlike arrays, there's no index arithmetic to jump ahead. To reach position k, you must visit every node from 0 to k-1. You wanted element 9,999? That's 9,999 hops. Hope you packed snacks.

There's also a performance gap that Big-O notation politely glosses over. Arrays are cache-friendly: elements are contiguous, so hardware prefetchers load them into L1 cache before you ask. Linked list nodes are scattered in memory. Each current = current.next is a potential cache miss, a round trip to RAM instead of L1. In practice, array traversal is 5 to 10 times faster than linked list traversal even when asymptotic complexity is identical. "5 to 10 times" is the benchmark paper's way of saying it's not even close. See Array vs Linked List Performance for the full breakdown.

Linked List Time Complexity: Where the Data Structure Wins

The case for linked lists is insertion and deletion. This is what the data structure was born to do.

Operation	Linked List	Array
Access by index	O(n)	O(1)
Search	O(n)	O(n)
Insert at head	O(1)	O(n)
Insert at tail	O(1) with tail pointer	O(1) amortized
Delete at head	O(1)	O(n)
Delete given a pointer to the node	O(1)	O(n)
Space per element	Value + pointer overhead	Value only

If you already hold a pointer to a node, you can remove it in O(1) by rewiring the previous node's next. An array must shift everything. A linked list just updates two pointers. The array is moving furniture. The linked list is changing one name in an address book.

This is why the LRU cache is a linked list problem. When evicting the least recently used entry, you need O(1) deletion anywhere in the list. A doubly linked list combined with a hash map delivers exactly that. See LRU Cache Implementation for how those two structures fuse together.

Space overhead is real though. Each node carries a pointer alongside the value. On a 64-bit system that's 8 bytes per next pointer, before alignment padding. For millions of small integers, you're paying more for the packaging than the product.

Singly vs. Doubly Linked: When You Need to Go Both Ways

The list above is singly linked. Each node knows its successor but not its predecessor. It's a one-way street.

A doubly linked list adds a prev pointer:

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

Now each node knows where it came from and where it's going. This sounds like a philosophy seminar, but it has a very practical payoff.

The benefit: you can delete a node in O(1) without knowing its predecessor. In a singly linked list, you need the previous node to rewire prev.next. In a doubly linked list, node.prev gives you that for free.

Use a singly linked list when you only traverse forward. Use a doubly linked list when you need O(1) deletion of arbitrary nodes. The LRU cache needs the second case. So does the LFU cache. They come up constantly in interviews.

The cost is double the pointer overhead and slightly more complex bookkeeping. More pointers to keep consistent, more chances to leave one dangling. See Singly vs Doubly Linked List for the full comparison.

Three Linked List Interview Patterns That Cover Most Problems

Linked list interview problems are almost all variations on three patterns. Learn these three and you've covered probably 80% of what you'll see.

Reversal

Classic. You iterate once, rewiring each next pointer to point backwards. Sounds simple. First time you implement it, you will accidentally delete your entire list at least once.

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Save current.next before you overwrite it, or you've severed the rest of the list. Ask anyone who's spent 45 minutes in an interview staring at a None pointer wondering where their list went. Save the pointer first. Always. Every time.

The logic looks intimidating once, then becomes muscle memory. Practice it until you can write it cold in the same time it takes to type def reverse_list.

Fast and Slow Pointers

Two pointers move at different speeds. Slow advances one node per step. Fast advances two. The slow pointer is doing a leisurely stroll. The fast pointer is on a bicycle.

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

If a cycle exists, the fast pointer laps the slow pointer and they meet. If there's no cycle, fast falls off the end.

The same pattern finds the middle of a list (when fast finishes, slow is at the midpoint), detects cycle entry points, and solves the "k steps from the end" problems. It's the most versatile tool in the linked list toolkit and the one interviewers love because it looks like magic until you understand it. See Floyd's Cycle Detection Algorithm for the proof behind why they're guaranteed to meet.

Dummy Head Nodes

A dummy (sentinel) node sits before head and eliminates edge cases when inserting at position zero or operating on an empty list. Not because your code is dumb. Because the alternative is a thicket of if head is None guards scattered through every function.

def remove_nth_from_end(head, n):
    dummy = Node(0)
    dummy.next = head
    left = dummy
    right = head

    for _ in range(n):
        right = right.next

    while right:
        left = left.next
        right = right.next

    left.next = left.next.next
    return dummy.next

The dummy node costs one allocation. In return, your logic handles every position uniformly. No special-casing for empty lists or head deletions. No if node is head branch that you'll inevitably forget to test. Almost every medium-to-hard linked list problem gets simpler with a dummy head. When in doubt, add one.

Five Problems to Know Cold

These cover every pattern. You should be able to write all five from scratch without looking anything up.

Reverse a Linked List (LeetCode 206): the reversal template, non-negotiable
Linked List Cycle (LeetCode 141): fast/slow pointers in their simplest form
Remove Nth Node From End (LeetCode 19): two-pointer gap technique with a dummy head
Merge Two Sorted Lists (LeetCode 21): fundamental merging, appears inside harder problems
LRU Cache (LeetCode 146): doubly linked list plus hash map, hard but extremely high-value at senior levels

Once you can write all five from scratch, you've internalized the shapes. The rest of the problem set is variations on themes you already know. For a broader list with difficulty rankings, see Linked List Interview Questions.

Most candidates can code the solution but completely fall apart when the interviewer says "walk me through this on the input 1 → 2 → 3." Dry-running pointer manipulation out loud on two or three nodes is its own skill. You are tracking multiple variables in your head while narrating what each one is doing. That narration does not come free. If it feels awkward, SpaceComplexity runs voice-based mock interviews that score communication and explanation quality alongside code correctness. The gap between writing it and explaining it is where most candidates lose points.