Data Structures: Arrays, Linked Lists, Stacks, and Queues

We explained that RAM holds your program’s data but did not explain that how you organize data within that memory is one of the most consequential decisions a program makes — the same collection of values, arranged differently, can make one operation instant and another one dramatically slow. This post covers the four foundational data structures every other structure in this series builds on: arrays, linked lists, and the two access-pattern-restricted structures built from them, stacks and queues.

Arrays: Contiguous Memory, Instant Index Access

An array stores its elements in contiguous memory — one value immediately after another, with no gaps. This single property is what makes index-based access essentially instant: to find array[5], the computer does not search anything — it calculates the exact memory address directly (the array’s starting address, plus 5 times the size of one element) and jumps straight there.

numbers = [10, 20, 30, 40, 50]
print(numbers[3])  # 40 — computed directly, not found by searching

The cost of this layout: inserting or removing an element anywhere except the very end requires shifting every subsequent element to maintain the contiguous layout.

numbers = [10, 20, 30, 40, 50]
numbers.insert(1, 99)
# Everything from index 1 onward must physically shift over by one position
# to make room: [10, 99, 20, 30, 40, 50]

Linked Lists: Scattered Memory, Flexible Insertion

A linked list takes the opposite approach: each element (called a node) is a separate object, stored wherever memory happens to be available, containing both its value and a reference (a “pointer”) to the next node in the sequence.

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


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

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def print_all(self):
        current = self.head
        while current is not None:
            print(current.value, end=" -> ")
            current = current.next
        print("None")


ll = LinkedList()
ll.prepend(30)
ll.prepend(20)
ll.prepend(10)
ll.print_all()  # 10 -> 20 -> 30 -> None

The advantage this layout provides: inserting a new node at a known position requires only updating a couple of references — no shifting anything else in memory, regardless of how large the list is.

The cost: reaching a specific position requires walking through the list node by node, starting from the head, since there is no way to jump directly to “the fifth node” the way array indexing does.

def get_at_index(self, index):
    current = self.head
    for _ in range(index):
        current = current.next  # must walk through, one node at a time
    return current.value

The Real, Hardware-Level Reason Arrays Are Often Faster in Practice

Post #1’s memory hierarchy directly explains something the raw Big O comparison alone does not: arrays frequently outperform linked lists in practice even for operations where their theoretical complexity is similar, because contiguous memory is cache-friendly. When the CPU reads array[0], the cache (Post #1) automatically loads a chunk of nearby memory too — meaning array[1], array[2], and so on are frequently already sitting in fast cache by the time you need them. A linked list’s nodes, scattered throughout memory, provide no such benefit — each node access is potentially a fresh trip all the way out to slower RAM, since the next node’s location has no relationship to the current one’s physical memory address.

This is a genuine, measurable, real-world performance difference that pure algorithmic complexity analysis (covered fully in Post #7) does not capture on its own — a direct, concrete payoff for understanding Post #1’s hardware coverage before this post’s data structure coverage.

Stacks: Last In, First Out

A stack restricts access to just one end — you can only add (push) or remove (pop) from the “top.”

stack = []
stack.append(10)  # push
stack.append(20)  # push
stack.append(30)  # push

print(stack.pop())  # 30 — the LAST item added is the FIRST one removed
print(stack.pop())  # 20
print(stack)         # [10]

LIFO — Last In, First Out — is the defining behavior. This is not an arbitrary restriction; it directly models a genuinely common real-world pattern.

Real-world use cases: The call stack referenced conceptually in Post #1 — when a function calls another function, the calling function’s state is “pushed” onto a stack, and “popped” back off once the called function returns, which is exactly why deeply nested recursive calls (covered fully in Post #10) can exhaust available memory. Undo functionality in almost any application. Expression evaluation and parsing (checking that parentheses are correctly matched, for instance).

Queues: First In, First Out

A queue also restricts access, but differently — items are added at one end (enqueue) and removed from the other (dequeue).

from collections import deque

queue = deque()
queue.append(10)   # enqueue
queue.append(20)   # enqueue
queue.append(30)   # enqueue

print(queue.popleft())  # 10 — the FIRST item added is the FIRST one removed
print(queue.popleft())  # 20
print(queue)              # deque([30])

FIFO — First In, First Out — models an entirely different, equally common real-world pattern: a genuine waiting line, where whoever arrived first is served first.

Real-world use cases: Task scheduling — processing requests or jobs in the order they arrived. Breadth-first search, previewed here and covered fully once Post #6 introduces graphs. Any producer-consumer pattern where work is generated by one part of a system and processed by another, in arrival order.

Why Python uses collections.deque instead of a plain list for queues: Removing from the front of a plain Python list (list.pop(0)) requires shifting every remaining element, exactly the array insertion cost covered earlier in this post — deque is specifically implemented to make both-end operations efficient, avoiding this cost entirely.

Real-World Use Cases

Choosing arrays for most general-purpose data: When you need fast, frequent access by position and insertions/removals are relatively rare or happen mostly at the end, arrays (Python’s list) are almost always the right default — exactly why this blog’s Python series used lists as the default collection throughout.

Choosing linked lists for frequent insertion/removal at arbitrary positions: Genuinely less common in everyday application code than textbook coverage might suggest, but valuable specifically when a program frequently inserts or removes from the middle of a large collection and cannot tolerate array’s shifting cost.

Stacks for anything requiring “undo the most recent action”: Browser back-button history, application undo/redo, and the call stack itself all follow this exact LIFO pattern.

Queues for anything requiring fair, arrival-order processing: Print job queues, request handling in web servers, and task scheduling systems all rely on FIFO ordering for the same underlying fairness guarantee.

Common Mistakes and Gotchas

⚠️ Mistake 1: Using a plain list for a queue’s dequeue operations

queue = []
queue.append(1)
queue.pop(0)  # works, but is O(n) — every remaining element shifts!

Use collections.deque for genuine queue behavior in Python — a plain list’s pop(0) technically works but carries the same shifting cost covered earlier in this post’s array section.

⚠️ Mistake 2: Assuming linked lists are always better for insertion because of their theoretical advantage Covered directly above — the cache-locality advantage arrays enjoy frequently makes them faster in practice even for insertion-heavy workloads at real-world data sizes, despite linked lists’ better theoretical insertion complexity.

⚠️ Mistake 3: Forgetting that linked list traversal is inherently sequential Unlike an array, there is no way to “jump” to the middle of a linked list — reaching any specific position requires walking from the head, one node at a time, a genuine limitation worth remembering when choosing this structure.

⚠️ Mistake 4: Confusing stack and queue behavior under pressure A genuinely common mistake when implementing an algorithm from memory — using a stack (LIFO) where a queue (FIFO) was needed, or vice versa, silently produces the wrong processing order without necessarily crashing, a specifically insidious kind of bug worth double-checking deliberately.

Quick Reference

# Array (Python list)
arr = [1, 2, 3]
arr.append(4)       # O(1) amortized
arr.insert(0, 0)      # O(n) — shifts everything

# Stack (Python list, use append/pop)
stack = []
stack.append(1)      # push
stack.pop()            # pop — LIFO

# Queue (collections.deque)
from collections import deque
q = deque()
q.append(1)           # enqueue
q.popleft()             # dequeue — FIFO

Exercises

Exercise 1 — Direct application Implement a Stack class from scratch (not using Python’s list directly) with push, pop, and peek (view the top without removing it) methods, using a plain Python list internally to store the data.

Exercise 2 — Slight variation Implement a function is_balanced(expression: str) -> bool that uses a stack to check whether a string’s parentheses, brackets, and braces are correctly matched and nested — a genuine, classic stack use case.

Exercise 3 — Real-world combination Extend the LinkedList class from this post with a delete(value) method that removes the first node containing a given value, correctly updating the surrounding nodes’ references.

Exercise 4 — Open-ended challenge Write a small benchmark comparing inserting 10,000 elements at the beginning of a Python list versus at the beginning of a collections.deque, timing both, and explain the result using this post’s coverage of arrays’ shifting cost.

FAQ

Q: Is Python’s list actually an array or a linked list underneath? A: A Python list is implemented as a dynamic array — contiguous memory that automatically grows as needed — which is exactly why it exhibits array-like performance characteristics (fast indexed access, costly middle insertion) covered throughout this post.

Q: When would I actually choose to implement my own linked list instead of using a list? A: Rarely in typical application code — Python’s built-in list and deque cover the overwhelming majority of real use cases well. Understanding linked lists deeply remains valuable for the concepts they set up directly for later posts, particularly trees (Post #5) and graphs (Post #6), both of which are built from the same node-and-reference idea.

Q: Why does a stack “make sense” for the call stack specifically? A: Because function calls genuinely nest — the most recently called function must finish before control returns to whichever function called it — exactly the LIFO pattern a stack is built to model, which is precisely why it’s called a “call stack” and not a “call queue.”

Q: Are there structures that combine array and linked-list advantages? A: Yes — more advanced structures like dynamic arrays with amortized growth (which is how Python’s list actually works internally) and various hybrid structures exist specifically to balance these tradeoffs, generally beyond this introductory post’s scope but worth knowing exist.

Summary and Next Steps

You now understand the fundamental tradeoff between arrays (fast access, costly middle insertion, cache-friendly) and linked lists (flexible insertion, slow access, cache-unfriendly) — including the genuine hardware-level reason, connecting directly back to Post #1, that arrays frequently win in practice despite comparable theoretical complexity. Stacks and queues, both built from these same underlying ideas with restricted access patterns, directly model two of the most common real-world processing orders: LIFO and FIFO.

Your next step: Complete Exercise 2 — the balanced-parentheses checker — since it is one of the clearest, most immediately satisfying demonstrations of exactly why a stack’s LIFO behavior is the natural, correct tool for a genuine, common problem.

Last updated: August 2026.