Linked Lists vs Arrays

An array (Python’s list) stores its elements in one contiguous block of memory, so the computer can jump straight to any index using simple arithmetic. A linked list instead stores each element in its own node, and every node holds a pointer to the next node, so the elements can live scattered anywhere in memory and are only connected by those pointers. That single difference in layout is the reason arrays and linked lists have almost opposite performance profiles: arrays are fast to read by index but expensive to grow or shrink in the middle, while linked lists are cheap to insert or delete once you already have a reference to the right spot, but slow to reach an arbitrary position. Recognizing this trade-off — and knowing which one an interview question is really testing — is the point of this lesson.

Overview: How Arrays and Linked Lists Work

Arrays (Python lists)

A Python list is backed by a contiguous block of memory holding pointers to the actual objects. Because every slot is the same fixed size and they sit back-to-back, the interpreter can compute the memory address of index i directly: base_address + i * slot_size. That arithmetic is why array[i] is O(1) no matter how large the array is. The cost shows up when you insert or delete somewhere other than the end: every element after that position has to physically shift over by one slot to keep the array contiguous, which is O(n) in the worst case. Appending to the end is usually cheap because Python’s list implementation over-allocates spare capacity, so most appends just write into unused space — this is called amortized O(1), because occasionally the array does have to grow and copy everything, but that cost is spread thin across many cheap appends.

Linked Lists

A linked list is built from nodes. Each node stores a value and a reference (next) to the following node; the list itself just keeps a reference to the first node, called the head. There is no requirement that nodes sit near each other in memory — the only thing connecting them is the chain of pointers. That has two big consequences. First, once you have a reference to a node, inserting or removing right next to it is O(1): you just rewire a couple of pointers, with no shifting required. Second, you cannot jump to “the 10th node” the way you jump to array[10] — you have to start at the head and follow next pointers one at a time, which makes indexed access O(n).

Singly vs Doubly Linked Lists

A singly linked list node only points forward (next). A doubly linked list node also points backward (prev), which lets you walk in either direction and delete a node in O(1) without having to search for its predecessor first. The extra pointer roughly doubles the per-node memory overhead. Python’s collections.deque is implemented as a doubly linked list of small fixed-size blocks, which is why it gives O(1) appends and pops from both ends, unlike a plain list, which is only fast at the right end.

Time and Space Complexity

Operation	Array (Python list)	Singly Linked List	Why
Access by index	O(1)	O(n)	Arrays compute an address directly from the index; a linked list must follow next pointers one at a time from the head.
Search by value	O(n)	O(n)	Both must inspect elements one by one unless the array is sorted and binary search applies.
Insert at front	O(n)	O(1)	Array insertion at index 0 shifts every existing element one slot to the right; a linked list only rewires the head pointer.
Insert at end	O(1) amortized	O(1) with a tail pointer, O(n) without one	Python’s list append usually has spare capacity; a linked list needs a direct reference to the last node or it must walk the whole chain first.
Insert/delete in the middle	O(n)	O(n) to reach the spot, O(1) to unlink once there	Arrays must shift elements to close or open a gap; linked lists must traverse to the position, but the pointer rewiring itself is O(1).
Extra memory per element	none beyond the value itself	one pointer (two for doubly linked)	Each node stores a reference to the next node (and previous, for doubly linked lists), overhead an array never needs.

Storing n elements takes O(n) space either way, but a linked list’s constant factor is larger because of the pointer(s) and the per-object overhead Python attaches to every node instance, whereas a list stores just the references themselves in one packed block.

Examples

Example 1: Inserting at the Front

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


class LinkedList:
    def __init__(self) -> None:
        self.head: "Node | None" = None

    def insert_at_front(self, value: int) -> None:
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def to_list(self) -> list[int]:
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result


def main() -> None:
    linked_list = LinkedList()
    for value in [3, 2, 1]:
        linked_list.insert_at_front(value)
    print("Linked list after inserting 3, 2, 1 at front:", linked_list.to_list())

    array = []
    for value in [3, 2, 1]:
        array.insert(0, value)
    print("Array after inserting 3, 2, 1 at front:", array)


main()

Output:

Linked list after inserting 3, 2, 1 at front: [1, 2, 3]
Array after inserting 3, 2, 1 at front: [1, 2, 3]

Both structures end up holding [1, 2, 3], but the work done to get there is very different. Each insert_at_front call on the linked list only creates one node and rewires two pointers — constant work regardless of how long the list already is. Each array.insert(0, value) call, by contrast, has to shift every element already in the array one position to the right before writing the new value at index 0, so its cost grows with the array’s current size.

Example 2: Random Access Cost

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def build_linked_list(values: list[int]) -> Node:
    head = Node(values[0])
    current = head
    for value in values[1:]:
        current.next = Node(value)
        current = current.next
    return head


def get_at_index_linked_list(head: Node, index: int) -> tuple[int, int]:
    steps = 0
    current = head
    for _ in range(index):
        current = current.next
        steps += 1
    return current.value, steps


def get_at_index_array(array: list[int], index: int) -> tuple[int, int]:
    return array[index], 1


def main() -> None:
    values = [10, 20, 30, 40, 50]
    head = build_linked_list(values)

    linked_value, linked_steps = get_at_index_linked_list(head, 3)
    array_value, array_steps = get_at_index_array(values, 3)

    print(f"Linked list: value at index 3 is {linked_value}, took {linked_steps} pointer hops")
    print(f"Array: value at index 3 is {array_value}, took {array_steps} step (direct index)")


main()

Output:

Linked list: value at index 3 is 40, took 3 pointer hops
Array: value at index 3 is 40, took 1 step (direct index)

To reach index 3 in the linked list, get_at_index_linked_list has to hop from the head through nodes holding 10, 20, and 30 before it lands on 40 — three hops for three intervening nodes. The array reaches the same value in a single step because indexing computes the address directly. This gap only widens as the structure grows: reaching index 999 in a 1,000-node linked list takes 999 hops, but still just one step in an array.

Example 3: Queue Behavior — deque vs list.pop(0)

from collections import deque


def process_as_queue_with_deque(items: list[int]) -> list[int]:
    queue = deque(items)
    processed = []
    while queue:
        processed.append(queue.popleft())
    return processed


def process_as_queue_with_list(items: list[int]) -> list[int]:
    queue = items.copy()
    processed = []
    while queue:
        processed.append(queue.pop(0))
    return processed


def main() -> None:
    items = [1, 2, 3, 4, 5]
    print("Using deque (doubly linked list):", process_as_queue_with_deque(items))
    print("Using list.pop(0):", process_as_queue_with_list(items))


main()

Output:

Using deque (doubly linked list): [1, 2, 3, 4, 5]
Using list.pop(0): [1, 2, 3, 4, 5]

Both versions produce the identical result, which is exactly why this mistake is easy to miss in review — the bug is in performance, not correctness. deque.popleft() is O(1) because deque is a doubly linked list of blocks with direct references to both ends. list.pop(0) is O(n) because removing the front element forces every remaining element to shift left by one slot. For a queue that will be popped from the front repeatedly, that difference turns an O(n) total workload into an O(n^2) one.

How It Works Step by Step

Let’s trace insert_at_front from Example 1 pointer by pointer, starting from an empty list (head = None):

• Insert 3: a new Node(3) is created. Its next is set to the current self.head, which is None. Then self.head is reassigned to point at this new node. List: 3 -> None.
• Insert 2: a new Node(2) is created. Its next is set to the current self.head, which is the node holding 3. Then self.head is reassigned to the node holding 2. List: 2 -> 3 -> None.
• Insert 1: a new Node(1) is created. Its next is set to the current head, the node holding 2. Then self.head becomes the node holding 1. List: 1 -> 2 -> 3 -> None.

Notice that no existing node ever moved in memory and no shifting happened — only pointers changed, which is exactly why this operation stays O(1) no matter how many nodes already exist. Compare that to array.insert(0, value) on [2, 3]: to insert 1, Python must move 3 from index 1 to index 2, move 2 from index 0 to index 1, and only then write 1 into index 0 — work proportional to the array’s length.

Common Mistakes

Mistake 1: Looping on current.next instead of current

It’s tempting to write the traversal loop condition around the pointer you’re about to follow, but that silently skips the last node.

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def print_all(head: "Node | None") -> None:
    current = head
    while current.next:
        print(current.value)
        current = current.next


def main() -> None:
    third = Node(30)
    second = Node(20)
    second.next = third
    first = Node(10)
    first.next = second
    print_all(first)


main()

Output:

10
20

The value 30 never gets printed. The loop condition while current.next asks “does the next node exist?” instead of “does the current node exist?”, so it stops one node too early — a classic off-by-one. Worse, if head itself is None, this version crashes with an AttributeError on current.next before the loop even starts. The fix is to check current directly:

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def print_all(head: "Node | None") -> None:
    current = head
    while current is not None:
        print(current.value)
        current = current.next


def main() -> None:
    third = Node(30)
    second = Node(20)
    second.next = third
    first = Node(10)
    first.next = second
    print_all(first)


main()

Output:

10
20
30

Now every node prints, and an empty list (head = None) simply prints nothing instead of crashing.

Mistake 2: Assuming array insertion at the front is as cheap as a linked list’s

This one doesn’t produce a wrong answer — it produces a slow one, which is arguably more dangerous because tests still pass.

def build_reversed(values: list[int]) -> list[int]:
    result: list[int] = []
    for value in values:
        result.insert(0, value)
    return result


def main() -> None:
    numbers = [1, 2, 3, 4, 5]
    print(build_reversed(numbers))


main()

Output:

[5, 4, 3, 2, 1]

The result is correct, but each of the n calls to result.insert(0, value) shifts every element already in result, making the whole loop O(n^2) — a mistake that comes from mentally treating a Python list like a linked list, where inserting at the front really would be O(1). Building the same result by appending (which is O(1) amortized) and reversing once at the end is O(n) overall:

def build_reversed(values: list[int]) -> list[int]:
    result: list[int] = []
    for value in values:
        result.append(value)
    result.reverse()
    return result


def main() -> None:
    numbers = [1, 2, 3, 4, 5]
    print(build_reversed(numbers))


main()

Output:

[5, 4, 3, 2, 1]

Same output, but now the total work is proportional to n instead of n^2 — the difference is invisible on a five-element list and painful on a million-element one.

Best Practices

• Reach for an array (list) by default — most problems need indexed access, iteration, or slicing, and Python’s list is highly optimized for exactly that.
• Reach for a linked list (or collections.deque) when you need frequent insertions/deletions at the ends or in the middle once you already hold a node reference, and indexed access isn’t required.
• Use collections.deque instead of hand-rolling a doubly linked list whenever you just need O(1) push/pop from both ends — it’s battle-tested and avoids reinventing pointer bookkeeping.
• Never use list.pop(0) or list.insert(0, x) inside a loop that runs many times; each call is O(n), turning the loop into O(n^2).
• When implementing a linked list yourself, always check current is not None (not current.next) as the traversal condition, and keep a tail reference if you need fast appends at the end.
• Remember that a linked list trades memory for flexibility — each node’s pointer overhead adds up, so for large collections of small values (e.g., integers), a plain array is usually far more memory-efficient.

Practice Exercises

• Reverse a linked list in place. Given the head of a singly linked list, write a function that reverses the direction of every next pointer and returns the new head, using O(n) time and O(1) extra space. Hint: track three references — previous, current, and the node you’re about to move to next — and rewire one pointer per step.
• Find the middle element. Given an array and a singly linked list holding the same n integers, find the middle element of the array in O(1) (using its length) and the middle of the linked list in a single pass using the fast/slow pointer technique (O(n) time, O(1) space) — no counting the length first.
• Interview-style: pick the structure. You need a data structure that supports O(1) insertion and removal at both ends, plus O(1) access by index. Can a plain array alone do this? Can a plain singly linked list alone do this? Which built-in Python type gets closest to all three requirements, and what does it sacrifice to do so?

Summary

• Arrays store elements contiguously, giving O(1) indexed access but O(n) insertion/deletion away from the end because elements must shift.
• Linked lists store elements as separate nodes connected by pointers, giving O(1) insertion/deletion once you’re at the right node, but O(n) indexed access because you must traverse pointer by pointer.
• Both use O(n) total space for n elements, but linked lists carry extra per-node pointer overhead.
• collections.deque (a doubly linked list under the hood) gives O(1) push/pop at both ends, unlike a plain list, which is only fast at the right end.
• Common bugs: looping on current.next instead of current (skips the last node or crashes on an empty list), and treating list.insert(0, x)/list.pop(0) as cheap when they are actually O(n).
• Default to arrays for general-purpose storage and indexed access; reach for linked lists or deque when insertions/deletions at known positions dominate and indexing isn’t needed.