Linked Lists

The Node Is the Whole Idea

An array stores its elements shoulder to shoulder in memory. A linked list doesn't. Each element lives wherever, and carries a pointer to the next one. That single design choice is the entire trade.

In Python you rarely reach for a linked list in production, because list already gives you a dynamic array with fast appends. But interviewers love linked lists precisely because they force you to think in pointers, and pointer manipulation is where sloppy code breaks. Learn to move pointers cleanly here and half of the "hard" list problems become mechanical.

Start with the atom:

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

A singly linked list is just a reference to the first node, the head. Follow .next until you hit None. That's it. No indexing, no len in O(1) unless you track it yourself.

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, val):
        self.head = Node(val, self.head)   # O(1)

    def __iter__(self):
        node = self.head
        while node:
            yield node.val
            node = node.next

push_front is O(1) and that's the list's whole selling point: cheap insertion and deletion at a known position, without shifting anything.

Doubly Linked, and Why It Earns Its Keep

A doubly linked list adds a prev pointer. Now you can walk backwards and, more importantly, delete a node in O(1) when you already hold a reference to it, because you can reach both neighbors.

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

def remove(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

This is exactly why an LRU cache pairs a hash map with a doubly linked list: the map finds the node in O(1), and the doubly linked list unlinks it in O(1). Neither structure alone does both. Python's own collections.OrderedDict is built on this idea, and if you want to skip the interview theater in real code, deque gives you O(1) at both ends.

The cost of the extra pointer is more bookkeeping. Every insert and delete touches two links per side, and forgetting one leaves a corrupt list that reads fine forwards and explodes backwards. Update both directions or neither.

The Three Pointer Patterns Interviewers Actually Ask

Nearly every linked list interview question is one of three moves in disguise.

Reversal. Walk the list, flipping each .next to point at the node you just left. Keep three references: previous, current, and the next node you're about to lose.

def reverse(head):
    prev = None
    while head:
        nxt = head.next   # save before you overwrite
        head.next = prev  # flip
        prev = head       # advance
        head = nxt
    return prev           # new head

The only bug worth worrying about is losing head.next before you save it. Save first, flip second. Say it out loud while you code it.

Cycle detection. A list with a loop never reaches None, so a naive walk hangs forever. Floyd's algorithm runs two pointers at different speeds: slow moves one node, fast moves two. If there's a cycle, fast laps slow and they collide. If not, fast falls off the end.

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

This is O(n) time and O(1) space. The tempting alternative, dumping every visited node into a set, also works but costs O(n) memory. Interviewers ask cycle detection specifically to see if you reach for the two-pointer trick instead of the set.

Merging two sorted lists. Splice nodes together in order using a dummy head so you never special-case the empty start.

def merge(a, b):
    dummy = tail = Node(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b   # attach whatever remains
    return dummy.next

The dummy node is the trick that makes this clean. Without it you write an annoying branch to pick the first node; with it, every node attaches the same way and you return dummy.next at the end. Reuse this pattern anywhere you build a list front to back.

When a List Actually Beats an Array

Be honest about this, because the answer is "rarely, in Python."

A linked list wins when you insert or delete in the middle and you already hold a pointer to that spot. That's O(1) versus an array's O(n) shift. It also wins when you splice whole sublists together, or when you can't tolerate the amortized reallocation an array does when it grows.

An array wins almost everywhere else. Random access is O(1) for an array and O(n) for a list, because you have to walk. Arrays are cache-friendly since their elements sit together in memory, so even an O(n) array scan often beats an O(n) list walk in wall-clock time. And every node in a linked list carries pointer overhead the array simply doesn't pay.

The practical read: use Python's list or deque for real work, and use hand-rolled nodes when a problem's constraints, an O(1) middle-delete, an LRU cache, an interview, demand them. If you want to drill these patterns until they're reflex, the DSA in Python course runs the same three moves against timed variations, and Advanced Python Programming covers the iterator and memory details underneath.

Master reversal, Floyd's cycle detection, and dummy-head merging. Those three cover the overwhelming majority of what you'll be asked, and each one is really just careful pointer choreography you can now do without flinching.