A Python stack from a linked list and list growth cost

Why this matters

A stack has one rule: the last item put in is the first item taken out. The rule says nothing about how the items are stored. This lesson builds the same stack two ways. The first way links small objects together in a chain, the structure from the linked list lesson. The second way uses a list, Python's built-in row of slots that grows when it fills up.

The two versions have different costs. A stack that holds a million items uses memory differently in each case. The growing list has a cost that looks uneven at first. Most pushes are fast, and a few are slow. Measuring that unevenness, and seeing why it averages out, is the main point of this lesson.

The stack operations used here are push to add an item on top, pop to remove the top item and return it, peek to read the top item without removing it, and is_empty to check for no items.

Start from the rule

Before any code, fix the four operations in your head:

push(x) puts x on the top.
pop() removes the top item and returns it.
peek() returns the top item and leaves it in place.
is_empty() returns True when there are no items.

A good stack does each of these in a fixed amount of work. The work does not depend on how many items the stack holds. Computer scientists call this constant time, and write it as O(1). The letter O stands for "order of", and the notation describes how the cost grows as the number of items grows. An O(1) operation costs about the same with ten items as with ten million.

Keep this goal in mind for both versions. Each push and pop should do a small, fixed amount of work.

Part 1: A stack on a linked chain

A linked chain is a set of nodes. A node is a small object that holds a value and a reference to the next node. A reference is a name that points at an object. The last node points at None, which is Python's word for "no object". Here the first node in the chain is the top of the stack.

Look at what happens when you push two values and pop one:

push a:  head -> [a | next: None]
push b:  head -> [b | next: ] -> [a | next: None]
pop:     returns b, head -> [a | next: None]

A push creates a new node that points at the old head, then moves the head to the new node. A pop takes the value from the head, then moves the head to the next node. Neither step touches the other nodes, so both steps do the same small amount of work no matter how long the chain is.

Here is the stack as a Python class:

class Node[T]:
    __slots__ = ("value", "next")
 
    def __init__(self, value: T, next_node: "Node[T] | None") -> None:
        self.value = value
        self.next = next_node
 
 
class LinkedStack[T]:
    def __init__(self) -> None:
        self._head: Node[T] | None = None
        self._size = 0
 
    def push(self, value: T) -> None:
        self._head = Node(value, self._head)
        self._size += 1
 
    def pop(self) -> T:
        if self._head is None:
            raise IndexError("pop from an empty stack")
        value = self._head.value
        self._head = self._head.next
        self._size -= 1
        return value
 
    def peek(self) -> T:
        if self._head is None:
            raise IndexError("peek at an empty stack")
        return self._head.value
 
    def is_empty(self) -> bool:
        return self._head is None
 
    def __len__(self) -> int:
        return self._size

Several details here are specific to Python.

The [T] after the class name is a type parameter. It is a placeholder for the kind of value the caller stores. The syntax class LinkedStack[T]: needs Python 3.12 or later. A caller can write LinkedStack[str] for a stack of strings. Python does not check these hints while the program runs. They help readers and tools that check types, but a wrong value still goes in without an error.

The line __slots__ = ("value", "next") tells Python that a node has only these two attributes. Without it, each node carries an extra dictionary, which costs memory. With it, each node is smaller.

The method __len__ lets the caller write len(stack). Python calls a method with two underscores on each side when the matching built-in action is used, so len(stack) calls stack.__len__().

The order of the lines in push matters. The expression Node(value, self._head) creates a node that points at the current head. Only then does self._head = ... move the head to that new node. If the code moved the head first, the old head would be lost.

The pop method saves the value first, then moves the head forward, then returns the saved value. If it read self._head.value after moving the head, it would read the wrong node.

Each of these methods touches a fixed number of attributes. No loop runs. That is why push and pop are O(1).

A short test shows the rule in action:

linked: LinkedStack[str] = LinkedStack()
for item in ["a", "b", "c"]:
    linked.push(item)
print(f"linked peek={linked.peek()} size={len(linked)}")
print(f"linked pop={linked.pop()} pop={linked.pop()} pop={linked.pop()}")
print(f"linked empty={linked.is_empty()}")

The output is:

linked peek=c size=3
linked pop=c pop=b pop=a
linked empty=True

The last item pushed, c, is the first item popped. Python evaluates the parts of an f-string from left to right, so the three pops come out in the order c, b, a.

What the linked version costs in memory

Each node is a separate object in memory. Every value needs its own node, and the node takes space on top of the value it holds. On the test machine (CPython 3.14.4), sys.getsizeof reported 48 bytes for one node with __slots__. That number depends on the Python build, and it does not count the value stored in the node. Pushing a million small numbers means creating a million node objects. Python frees a node when nothing refers to it any more, so popped nodes are cleaned up without any extra code.

The linked version has no capacity limit, and it never copies its data. Its cost is spread evenly across the operations. The list version below trades that evenness for less memory per item.

Part 2: A stack on a growing list

Python's list is a dynamic array. It is a row of slots that grows by itself. A slot is a place that holds one reference. The number of items is len(lst). The number of slots the list has reserved is its capacity. Python does not show the capacity directly. Part 2 of this lesson builds the growth rule by hand, so you can see it. Later in the lesson you can measure the real list.

The class below keeps its own row of slots, _items. The slots that are in use are counted by _size. The counter copies counts how many items were moved during growth. That counter is only there so the lesson can measure the cost. The same file also runs the growth rule as a counting simulation, so the large counts can be checked quickly.

Python · editable

class ArrayStack[T]:
    def __init__(self) -> None:
        self._items: list[T | None] = [None, None]
        self._size = 0
        self.copies = 0

def push(self, value: T) -> None:
        if self._size == len(self._items):
            self._grow()
        self._items[self._size] = value
        self._size += 1

def _grow(self) -> None:
        bigger: list[T | None] = [None] * (len(self._items) * 2)
        for i in range(self._size):
            bigger[i] = self._items[i]
            self.copies += 1
        self._items = bigger

def pop(self) -> T:
        if self._size == 0:
            raise IndexError("pop from an empty stack")
        self._size -= 1
        value = self._items[self._size]
        self._items[self._size] = None
        return value

@property
    def capacity(self) -> int:
        return len(self._items)

def __len__(self) -> int:
        return self._size

def copies_for(n: int, start: int, grow_to) -> int:
    capacity = start
    size = 0
    copies = 0
    for _ in range(n):
        if size == capacity:
            copies += size
            capacity = grow_to(capacity)
        size += 1
    return copies

def capacity_after(n: int) -> int:
    capacity = 2
    while capacity < n:
        capacity *= 2
    return capacity

def main() -> None:
    print("n  capacity  copies  copies/n")
    stack: ArrayStack[int] = ArrayStack()
    for n in range(1, 10):
        stack.push(n)
        print(f"{n}  {stack.capacity}  {stack.copies}  {stack.copies / n:.2f}")

small: ArrayStack[int] = ArrayStack()
    small.push(1)
    small.pop()
    print(f"after pop size={len(small)} capacity={small.capacity}")

for n in (1000, 1_000_000, 10_000_000):
        copies = copies_for(n, 2, lambda cap: cap * 2)
        print(f"n={n} capacity={capacity_after(n)} copies={copies} copies/n={copies / n:.3f}")

print(f"n=10000 plus-one copies={copies_for(10_000, 2, lambda cap: cap + 1)}")
    print(f"n=10000 doubling copies={copies_for(10_000, 2, lambda cap: cap * 2)}")
    print(f"n=16 doubling copies={copies_for(16, 2, lambda cap: cap * 2)}")
    print(f"n=9 start-1 copies={copies_for(9, 1, lambda cap: cap * 2)}")
    print(f"n=9 start-2 copies={copies_for(9, 2, lambda cap: cap * 2)}")

if __name__ == "__main__":
    main()

The output is:

n  capacity  copies  copies/n
1  2  0  0.00
2  2  0  0.00
3  4  2  0.67
4  4  2  0.50
5  8  6  1.20
6  8  6  1.00
7  8  6  0.86
8  8  6  0.75
9  16  14  1.56
after pop size=0 capacity=2
n=1000 capacity=1024 copies=1022 copies/n=1.022
n=1000000 capacity=1048576 copies=1048574 copies/n=1.049
n=10000000 capacity=16777216 copies=16777214 copies/n=1.678
n=10000 plus-one copies=49994999
n=10000 doubling copies=16382
n=16 doubling copies=14
n=9 start-1 copies=15
n=9 start-2 copies=14

Read the first rows. The stack starts with capacity 2. After one push, the capacity is still 2, and no copy happened. After two pushes, the array is full but nothing needs to grow yet. The third push finds the array full, so _grow makes a new array of length 4 and copies the two existing items. The copies column goes to 2 at that point.

The next growth happens at push 5, when the array of length 4 is full. The new array has length 8, and copies 4 items. The running total becomes 2 + 4 = 6. Then push 9 finds the array of length 8 full. It makes length 16 and copies 8 items, for a total of 6 + 8 = 14.

Look at the pattern. The capacity doubles each time, from 2 to 4 to 8 to 16. Copies happen only at the moments when the array is full, and the number copied is the size of the old array: 2, then 4, then 8.

The names starting with an underscore, such as _items and _size, are a convention. They tell a reader that the attribute is for the class's own use, and that callers should not change it directly. Python does not block the access.

Slots are numbered from 0 at the bottom. The index _size is the next free slot, and the top item sits one slot below it. Push writes to self._items[self._size], then adds one to _size. Pop subtracts one from _size first, then reads that slot. This order is the reverse of push, and it keeps _size pointing at the next free slot at all times.

The line [None] * (len(self._items) * 2) creates a new row of empty slots. Python uses None to mean "no value here". Because the value None can be a real item too, the stack relies on _size, not on the contents of the slots, to know how many items are in use.

The line self._items[self._size] = None in pop matters for this class. The row of slots still holds a reference to the popped value. Without this line, the value stays in memory even though the stack no longer uses it. Setting the slot to None drops that reference, and Python can free the object. A plain list does not need this step, because its own pop() method removes the slot and returns the value.

Why doubling and not adding one slot

The alternative is to grow by one slot each time the array is full. That works, but it is slow. Each growth copies every item, so if the array grows by one slot at a time, almost every push copies all the items so far. Pushing a million items would copy about 500 billion items in total. That is the sum 1 + 2 + 3 and so on up to a million. This is arithmetic, not a measured number, but it shows the problem: the total work grows with the square of the number of items.

Doubling avoids that. Copies happen only at sizes 2, 4, 8, 16, and so on. There are few growth steps, and each one copies every item the stack holds at that moment.

Part 3: What the real Python list does

Python's own list does not double. You can measure its capacity with sys.getsizeof, which reports how many bytes an object uses. An empty list uses a fixed number of bytes, and each reserved slot adds 8 bytes on a 64-bit build. Subtracting the empty size and dividing by 8 gives the capacity:

import sys
 
empty = sys.getsizeof([])
lst = []
last = None
for i in range(1, 60):
    lst.append(i)
    capacity = (sys.getsizeof(lst) - empty) // 8
    if capacity != last:
        print(len(lst), capacity)
        last = capacity

On the test machine the output was:

Each line shows the length at the moment the capacity changed, and the new capacity. The steps are not all doubling. The capacity grows by about one eighth of the size plus a few slots, rounded down to a multiple of 4. This rule fits every line above, but it was found by reading these numbers, not by reading the Python source. Other builds may use different steps, so do not rely on the exact numbers. The main point holds: each growth step copies a fixed fraction of the list, so the average stays a constant per push. That constant is larger than for doubling, because the list grows in smaller steps.

The list also shrinks. Starting from a list of 1000 items and popping them one at a time, the capacity dropped when about half the slots were in use. On the test machine, the capacity was 564 when 499 items were left, and 64 when 53 items were left. That is another reason to use the built-in list in real code. You get the growth and the shrink without writing them yourself.

A reader who knows Java will recognise this as the same idea as ArrayList.

Part 4: Amortised cost

The copies come in bursts. A single push can be expensive. When the array holds a million items and is full, the next push copies a million items in one step. Most pushes are cheap, because they write one slot and nothing else. The question is how the cost looks when you average over many pushes.

Amortised cost is the average cost per operation over a long sequence, counting the expensive steps as part of that sequence. It is not the cost of a typical single step. The word "amortised" comes from paying off a debt in parts. The occasional large cost is spread over the many cheap operations before it.

The run above shows this with three sizes. Each row gives the total number of copies after n pushes, and that total divided by n. For n = 1,000,000 the copies per push are about 1.05. Each push writes one item, and on average it causes about 0.05 extra copies. That is a small constant, not a number that grows with n.

The last row needs a note. For n = 10,000,000 the ratio is 1.678, which is larger than the 1.049 at a million. The reason is where n falls relative to the powers of two. The array has capacity 16,777,216, which is 2 to the 24th power. Ten million pushes fill the array to about 60 percent of that size. The copies so far came from the earlier growth steps, which together sum to 16,777,214. The ratio is still under 2, because the total copies after any number of pushes is always less than twice the number of pushes.

Here is why that holds. The copies happen at sizes that are powers of two: 2, 4, 8, and so on, up to the largest power of two below n. Their sum is less than twice that largest power, and that power is less than n. So the copies total less than 2n. A push adds one write to that, so the work for n pushes is less than 3n. Each push costs at most about three simple steps on average, and that does not depend on n.

What the worst single push costs

The average hides the expensive pushes. The push that triggers growth can copy about n items, where n is the current size. For a stack of one million items, that single push is a million steps. A program that needs every push to finish quickly, such as a real-time audio program, must allow for that. For most programs the average is what matters, and the average stays low.

This is why the statement is about amortised cost, not about the cost of each push. The statement is: over any sequence of pushes, the total work is less than three times the number of pushes. The statement is not: each push takes three steps.

Common mistakes

Growing by one slot

A common first try is to grow by one slot when full. It works, and the output is correct, but it copies items on almost every push. The counting run above shows the gap. For n = 10,000 pushes, growing by one slot copies 49,994,999 items. Doubling copies 16,382 items. The test is the count, not whether the output is correct.

Popping an empty stack

Both versions in this lesson raise an error when popped with no items. The message in the class is pop from an empty stack. A plain list raises IndexError with the message pop from empty list. Here is the output of an uncaught pop on the linked stack. The folder part of the path is shortened here, and it will differ on your machine. The line numbers come from a file with the class and a short test, so they will differ in your copy:

Traceback (most recent call last):
  File ".../linked_stack.py", line 39, in <module>
    empty.pop()
    ~~~~~~~~~^^
  File ".../linked_stack.py", line 20, in pop
    raise IndexError("pop from an empty stack")
IndexError: pop from an empty stack

Read the last line first. It names the error type, IndexError, and the message. The lines above it show where the error was raised. The bottom frame, line 20, in pop, is inside the class. The top frame, line 65, in <module>, is the line in the program that called pop. The ~~~ and ^^ lines are markers that point at the part of the line that failed. Python 3.11 and later print them.

A loop that pops until the stack is empty should check is_empty() or len(stack) on each pass. A loop that runs a fixed number of times, based on a count taken earlier, will pop too many times when the stack is smaller than expected.

Peeking with `items[-1]` on an empty list

A Python list accepts a negative index. items[-1] means the last item. On an empty list there is no last item, and Python raises an error:

IndexError: list index out of range

When the stack is a plain list, check if items: before reading items[-1].

Confusing size with capacity

size is the number of items. capacity is the number of reserved slots. On the ArrayStack class, push 1 and pop, and the output is:

after pop size=0 capacity=2

The stack is empty, but it still has room for two items. Code that checks the capacity to decide whether the stack is empty will be wrong. Always check the size. For a plain list, len(items) is the size, and the capacity is not available without sys.getsizeof.

Forgetting to clear the popped slot

In ArrayStack, if pop does not set the slot to None, the row of slots keeps the popped object alive. The output is still correct, but memory is not freed. A program that pushes large objects and pops them can use much more memory than it needs. The line self._items[self._size] = None prevents this.

Walking a long chain with recursion

A method that calls itself once for each node is easy to write, but Python limits how deep those calls can go. Here is a recursive length function on a chain of 5000 nodes:

def length_recursive(node):
    if node is None:
        return 0
    return 1 + length_recursive(node.next)

The output from the test machine was:

recursion limit: 1000
recursive big: RecursionError maximum recursion depth exceeded

The default limit is 1000 calls deep in CPython. The limit can be read with sys.getrecursionlimit(). The loop version, which moves through the chain with a while loop, has no such limit. For a stack, the methods in this lesson are not recursive, so this limit does not affect them.

Practice

Try each exercise on paper first, then check your answer with the code in this lesson.

Exercise 1: trace the linked stack

Using the LinkedStack class, write the chain after each step: push 1, push 2, pop, push 3. Then say which value the next pop returns.

Show the answer

After push 1, the head points to the node holding 1, whose next is None. After push 2, the head points to the node holding 2, whose next points to the node holding 1. The pop returns 2 and moves the head to the node holding 1. After push 3, the head points to the node holding 3, whose next points to the node holding 1. The next pop returns 3. The chain is 3 -> 1, and the top of the stack is 3.

Exercise 2: count the copies by hand

Starting with capacity 2, how many copies does the ArrayStack make in total after 16 pushes? Work out the answer, then check it with a program.

Show the answer

Growth happens when the array is full at the start of a push. The array of length 2 is full at push 3, which copies 2 items. The array of length 4 is full at push 5, copying 4. The array of length 8 is full at push 9, copying 8. The array of length 16 would be full at push 17, which does not happen for 16 pushes. The total is 2 + 4 + 8 = 14. The counting run prints 14 for n = 16.

Exercise 3: start from capacity 1

Change the starting capacity from 2 to 1. How many copies happen after 9 pushes? Give the reason for the result.

Show the answer

The array of length 1 is full at push 2, copying 1 item. The array of length 2 is full at push 3, copying 2 items. The array of length 4 is full at push 5, copying 4 items. The array of length 8 is full at push 9, copying 8 items. The total is 1 + 2 + 4 + 8 = 15. The counting run prints 15 for n = 9 with start 1, compared with 14 when starting from capacity 2. The starting size changes the total only a little, because the copies still follow powers of two.

Exercise 4: make the linked stack reject None

Add a check so that push(None) raises a ValueError with the message None is not allowed. Explain why this check is a choice, not a requirement of the linked structure.

Show the answer

One way is a subclass that checks the value before it calls the parent's push:

class CheckedStack[T](LinkedStack[T]):
    def push(self, value: T) -> None:
        if value is None:
            raise ValueError("None is not allowed")
        super().push(value)

Calling CheckedStack().push(None) raises ValueError: None is not allowed. A node can hold None without any problem, so the check is a rule the stack chooses to enforce. A caller who gets None back from pop may think the stack was empty, and forbidding None avoids that confusion. The rule is a choice the stack makes, and the node structure does not need it.

Exercise 5: explain the trade-off

A program pushes one million numbers, then pops them all, then pushes one million again. Explain how the linked version and the array version differ in memory and in the work done by each push. Keep the answer to a few sentences.

Show the answer

The linked version creates one node object per push, so it creates a million objects, and each one takes memory on top of its value. The array version keeps a row of slots. After the first fill it reuses the row, because ArrayStack never shrinks. Its growth copies items, but the total copies stay below twice the number of pushes. The linked version does no copying at all, but each item costs the memory of a node. The array version is usually lighter per item, while the linked version never has a copy spike.

Summary

A stack has the same rule, last in first out, whether it is built on nodes or on a list.
A linked stack pushes and pops at the head in constant time, at the cost of one node object per item.
A dynamic array doubles its capacity when full and copies the items across, so growth happens only at powers of two.
The total copies after n pushes is less than 2n, so the amortised cost per push stays a small constant.
A single push can be expensive, so amortised cost describes the average over many operations, not each one.

A Python stack from a linked list and list growth cost

Why this matters

Start from the rule

Part 1: A stack on a linked chain

What the linked version costs in memory

Part 2: A stack on a growing list

Why doubling and not adding one slot

Part 3: What the real Python list does

Part 4: Amortised cost

What the worst single push costs

Common mistakes

Growing by one slot

Popping an empty stack

Peeking with items[-1] on an empty list

Confusing size with capacity

Forgetting to clear the popped slot

Walking a long chain with recursion

Practice

Exercise 1: trace the linked stack

Exercise 2: count the copies by hand

Exercise 3: start from capacity 1

Exercise 4: make the linked stack reject None

Exercise 5: explain the trade-off

Summary

Stuck? Ask the tutor

Peeking with `items[-1]` on an empty list