A Stack on Links

Get access to whole semester resourcesSemester Pass

Chapter Thirty-Three

Syllabus topic Module 1, "Stacks: Stack ADT for Stack"

Pages 99 to 101 of 411

In one line

A linked stack pushes by prepending and pops by removing the head, so both are the O(1) operations of chapter 17 and there is no capacity at all.

The design

The top of the stack is the head of a singly linked list. That choice is the whole design, and it is made because chapter 17 measured prepending at two assignments whatever the length.

push(item): head = Node(item, head)

pop() : item = head.data; head = head.next; return item

peek() : return head.data

is_empty(): head is null

Nothing is searched, nothing is shifted, nothing has a maximum.

Why not the tail? Because appending needs a walk or a tail pointer, and deleting the last node is O(n) even with one, by chapter 18. The head is the only end of a singly linked list where both operations are free, and a stack needs both at the same end. That is the reasoning an examiner is looking for.

Built and run

class Node:
    __slots__ = ("data", "next")

    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


class LinkedStack:
    """The top of the stack is the head of the list."""

    def __init__(self):
        self.head = None
        self.n = 0

    def is_empty(self):
        return self.head is None

    def size(self):
        return self.n

    def push(self, item):
        self.head = Node(item, self.head)     # prepend: two assignments
        self.n += 1

    def pop(self):
        if self.head is None:
            raise IndexError("pop from an empty stack: underflow")
        node = self.head
        self.head = node.next
        node.next = None
        self.n -= 1
        return node.data

    def peek(self):
        if self.head is None:
            raise IndexError("peek at an empty stack: underflow")
        return self.head.data

    def snapshot(self):
        """Bottom to top, so it prints like the array version."""
        out, walk = [], self.head
        while walk is not None:
            out.append(walk.data)
            walk = walk.next
        return list(reversed(out))


s = LinkedStack()
for item in ("A", "B", "C"):
    s.push(item)
    print("push %s -> %-16s size = %d" % (item, str(s.snapshot()), s.size()))

print()
print("peek ->", s.peek(), "| size is still", s.size())
print("pop  ->", s.pop(), "| now", s.snapshot())

print()
deep = LinkedStack()
for i in range(100000):
    deep.push(i)
print("pushed 100,000 items with no capacity declared: size =", deep.size())
print("top of it:", deep.peek())
print("there is no overflow to report, only the machine's memory")

print()
try:
    LinkedStack().pop()
except IndexError as e:
    print("underflow still applies:", e)

push A -> ['A']            size = 1
push B -> ['A', 'B']       size = 2
push C -> ['A', 'B', 'C']  size = 3

peek -> C | size is still 3
pop  -> C | now ['A', 'B']

pushed 100,000 items with no capacity declared: size = 100000
top of it: 99999
there is no overflow to report, only the machine's memory

underflow still applies: pop from an empty stack: underflow

A Stack on Links

The ADT proved: one caller, both stacks

Chapter 7 claimed that a caller written against the ADT works with any implementation. Here it is, on the two stacks this paper builds.

class ArrayStack:
    def __init__(self, capacity):
        self.cells = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def push(self, item):
        self.top += 1
        self.cells[self.top] = item

    def pop(self):
        item = self.cells[self.top]
        self.top -= 1
        return item


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


class LinkedStack:
    def __init__(self, capacity=None):
        self.head = None

    def is_empty(self):
        return self.head is None

    def push(self, item):
        self.head = Node(item, self.head)

    def pop(self):
        node = self.head
        self.head = node.next
        return node.data


def reverse_with(stack_class, text):
    """A caller written against the ADT. It never asks how the stack is built."""
    stack = stack_class(len(text))
    for character in text:
        stack.push(character)
    out = []
    while not stack.is_empty():
        out.append(stack.pop())
    return "".join(out)


for cls in (ArrayStack, LinkedStack):
    print("%-12s reversed 'Data Structures' to %r"
          % (cls.__name__, reverse_with(cls, "Data Structures")))

ArrayStack   reversed 'Data Structures' to 'serutcurtS ataD'
LinkedStack  reversed 'Data Structures' to 'serutcurtS ataD'

One function, two structures sharing no storage code, identical results. That is the ADT doing its job, and it is also the reversal property of chapter 30 put to work.

Array against links, for a stack

	Array stack	Linked stack
push	O(1)	O(1)
pop	O(1)	O(1)
peek	O(1)	O(1)
Capacity	fixed, must be chosen	none
Overflow	possible	only when memory runs out
Memory per item	one cell	one cell plus an address
Unused memory	reserved capacity sits empty	none
Cache behaviour	good, items are contiguous	poorer, nodes are scattered

Neither is better in general. Use the array when the maximum depth is known, which it often is, and the contiguous memory then makes it genuinely faster. Use links when it is not, and accept the address per item.

Quick revision

A linked stack makes the top of the stack the head of the list.
push prepends, pop removes the head, peek reads the head. All O(1) by chapter 17.
The head is chosen because it is the only end of a singly linked list where adding and removing are

both free.

There is no capacity, so overflow does not arise; underflow still does.
The same caller runs unchanged against the array stack and the linked stack, which is what the ADT

promises.

Choose the array when the maximum depth is known, for the contiguous memory; choose links when it is

not.

Test yourself

1. Which end of the linked list is the top of the stack, and why that one? The head. It is the only end of a singly linked list where both adding and removing are O(1); the tail needs a walk to delete even with a tail pointer.

A Stack on Links

2. Write push and pop for a linked stack. push: head = Node(item, head). pop: check empty, item = head.data, head = head.next, return item.

3. Which of the two error conditions does a linked stack still have? Underflow. Overflow does not arise because there is no fixed capacity.

4. What did the one-caller demonstration show, and what did it not show? That a function written against the ADT works unchanged on both implementations. It did not show that they cost the same: memory per item and cache behaviour differ.

5. Give two reasons to prefer the array stack when the maximum depth is known. No address of memory per item, and contiguous storage, which the cache handles better than scattered nodes.

6. A program pushes an unknown number of items, possibly very many. Which implementation, and why? The linked stack, because it has no capacity to choose in advance and therefore cannot overflow on valid input.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue