Arrays and Linked Lists

Why organize data

Suppose a program keeps a million items and looks each one up once. If every lookup checks every item, that’s a million times a million, 10^12 checks; at a billion simple operations a second, about 16 minutes and 40 seconds ¹. Organized well, the same lookups can take a fraction of a second. That’s what data structures are for: arranging data in memory so the operations a program does most stay fast as the data grows ¹.

This module builds the main ones in Python and measures them. Next module, Algorithms, does the same for the procedures that use them.

Interfaces and implementations

Two questions get kept apart ¹:

• the interface: what a structure does, the operations it offers and what they mean;
• the implementation: how it does them, with what layout in memory.

One interface can have many implementations. Three classic interfaces ¹:

• A stack (last in, first out): add and remove at the same end, like a pile of plates. Your browser’s Back button, an editor’s undo history, and the stack in a process’s address space (last module) all work this way.
• A queue (first in, first out): add at the back, remove from the front, like a checkout line. The scheduler’s FIFO policy was a queue.
• A deque (“deck”, double-ended queue): add and remove at both ends.

Underneath, nearly all of them are built from one of two layouts: an array or a linked list.

Arrays

An array stores its items side by side in one block of memory. If each slot is 8 bytes, item i is at the block’s start address plus 8 * i, so reaching any position takes one calculation, the same time whatever the index ¹. Arrays are also friendly to the memory hierarchy: walking through one in order is the fast, cache-friendly pattern from module 3.

Their weakness is change in the middle ¹:

• Inserting or removing near the front means shifting every item after it one slot over.
• Growing past the end of the block means allocating a bigger block and copying everything across. Allocating twice the size each time keeps this rare enough that, averaged over many additions, it costs only a constant amount per addition ¹.

Python’s list

Python’s list is an array: a contiguous array of references to the actual objects, with its length stored alongside ². Each reference is a 64-bit address, 8 bytes. When the array has to grow, Python allocates some extra room so the next few appends don’t need to copy anything ². You can watch it happen with sys.getsizeof, which reports the size of the list object itself, not the items it refers to ³. Save this as growth.py:

# growth.py: watch a Python list's array grow as items are appended.
import sys

items = []
last = sys.getsizeof(items)
print(f"empty list: {last} bytes")
for i in range(40):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:                    # the array was just reallocated
        print(f"after {len(items):>2} items: {size} bytes, room for {(size - 56) // 8}")
        last = size

me@linuxbox:~$ python3 growth.py
empty list: 56 bytes
after  1 items: 88 bytes, room for 4
after  5 items: 120 bytes, room for 8
after  9 items: 184 bytes, room for 16
after 17 items: 248 bytes, room for 24
after 25 items: 312 bytes, room for 32
after 33 items: 376 bytes, room for 40

An empty list is 56 bytes of bookkeeping; each slot adds 8. The first append reserved room for 4, and in 40 appends the array was replaced only 6 times. The other 34 appends just filled a spare slot. (These sizes are from 64-bit CPython 3.12; other versions may differ slightly.)

Naming the costs

Programmers describe how an operation’s time grows with the number of items, n, using big-O notation, which next module explains properly. For now, two cases ⁴:

• O(1), constant time: the same however big the list. Python’s items[k], items[k] = x, append, and len(items).
• O(n), linear time: proportional to the number of items. x in items checks item after item; items.insert(0, x) and items.pop(0) shift the whole list.

Python’s documentation lists the cost of every operation on its built-in types; insert(k, x) is O(n − k), because only the items after position k move ⁴.

Measuring

This program adds n items three ways: at the end of a list, at the front of a list, and at the front of a collections.deque. Save it as ends.py:

# ends.py: add n items at the end of a list, at its front, and at a deque's front.
import time
from collections import deque

def at_end(n):
    a = []
    for i in range(n):
        a.append(i)

def at_front(n):
    a = []
    for i in range(n):
        a.insert(0, i)                  # every item already there shifts one place

def deque_front(n):
    d = deque()
    for i in range(n):
        d.appendleft(i)

for n in (100_000, 200_000):
    for name, fn in [("list.append", at_end), ("list.insert(0, x)", at_front), ("deque.appendleft", deque_front)]:
        start = time.perf_counter()
        fn(n)
        print(f"n={n:<8,} {name:<18} {time.perf_counter() - start:7.3f} s")

On a desktop PC:

me@linuxbox:~$ python3 ends.py
n=100,000  list.append          0.003 s
n=100,000  list.insert(0, x)    0.998 s
n=100,000  deque.appendleft     0.003 s
n=200,000  list.append          0.006 s
n=200,000  list.insert(0, x)    3.928 s
n=200,000  deque.appendleft     0.005 s

Doubling n doubled the time for append: twice as many operations, each O(1). But it quadrupled the time for inserting at the front: twice as many inserts, and each one shifts, on average, twice as many items. A deque is built for exactly this: appends and pops at either end in about constant time, where a list pays O(n) for insert(0, v) and pop(0) ⁵. Use a deque whenever you need a queue.

Linked lists

A linked list gives up the single block. Each item lives in its own node, which holds the value and a reference to the next node; the list itself only remembers the first node, the head ¹. Save this as linked.py:

# linked.py: a singly linked list, built from nodes that point to the next one.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next                # the next node, or None at the end

class LinkedList:
    def __init__(self):
        self.head = None                # the first node

    def push_front(self, value):        # constant time: no shifting
        self.head = Node(value, self.head)

    def insert_after(self, node, value):  # constant time, once you have the node
        node.next = Node(value, node.next)

    def find(self, value):              # walks from the head: time grows with length
        node, steps = self.head, 1
        while node is not None and node.value != value:
            node, steps = node.next, steps + 1
        return node, steps

    def __str__(self):
        parts, node = [], self.head
        while node is not None:
            parts.append(str(node.value))
            node = node.next
        return " -> ".join(parts) + " -> None"

todo = LinkedList()
for task in ["sand", "glue", "cut"]:
    todo.push_front(task)
print(todo)
node, steps = todo.find("glue")
todo.insert_after(node, "clamp")
print(todo)
print("found 'sand' after", todo.find("sand")[1], "steps")

me@linuxbox:~$ python3 linked.py
cut -> glue -> sand -> None
cut -> glue -> clamp -> sand -> None
found 'sand' after 4 steps

push_front added each task in front of the last, so they come out in reverse order. Inserting clamp after glue changed two references and moved nothing, but finding sand meant visiting every node before it. That’s the trade ¹:

• Fast: adding or removing at the head, or next to any node you already have, in constant time.
• Slow: reaching position i, which means walking i nodes from the head.

A doubly linked list gives each node a reference to the previous node as well, so both ends, and removal of any known node, are constant time ¹. The nodes can be anywhere in memory, though, so walking a linked list loses the spatial locality that makes arrays fast.

You’ve used a linked structure already: each git commit stores a reference to its parent, so git log walks backward from HEAD one commit at a time, just like find here.

Which one?

In Python: use a list for almost everything, a deque for queues and anything that adds or removes at the front, and a hand-built linked list almost never. The ideas matter anyway: every structure in this module is built from these two layouts, references between nodes and blocks of slots.

Your turn

So

Data structures arrange data so common operations stay fast as it grows. An interface (stack, queue, deque) says what a structure does; an implementation says how. Arrays keep items side by side, so any index is O(1), but inserting near the front is O(n), and growing means copying, kept rare by reserving spare room; Python’s list is such an array. Linked lists chain separate nodes: inserting next to a known node is O(1), but reaching position i means walking. Doubling the data doubles O(n) work per operation, and repeating an O(n) operation n times quadruples it.