Queue (linked list)

Cost and properties

enqueue / dequeue	O(1) worst case
order	FIFO
pointers	first and last
used by	BFS, buffers, schedulers

Reference: Sedgewick & Wayne, §1.3.

Queue (linked list) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class Queue:
    class _Node:
        __slots__ = ('item', 'next')
        def __init__(self, item):
            self.item, self.next = item, None

    def __init__(self):
        self.first = None                 # dequeue from here
        self.last = None                  # enqueue here
        self.n = 0

    def enqueue(self, item):
        node = Queue._Node(item)
        if self.last is None:             # empty queue: one node is both ends
            self.first = node
        else:
            self.last.next = node
        self.last = node
        self.n += 1

    def dequeue(self):
        if self.first is None:
            raise IndexError('queue underflow')
        item = self.first.item
        self.first = self.first.next
        if self.first is None:            # queue just became empty
            self.last = None              # or last dangles at a dead node
        self.n -= 1
        return item

Why it works

Two ends, two pointers

A singly linked list can only walk forwards, so dequeuing from first is easy and enqueuing at the end would cost a full traversal — unless you keep last. Maintaining that second pointer is the whole trick, and both operations become O(1) worst case.

The bug everyone writes

Dequeuing the final item leaves last pointing at a node that is no longer in the queue. The next enqueue then attaches to a dead node and the item vanishes. The three-line guard if self.first is None: self.last = None is not defensive coding; it restores the invariant “both pointers are None, or both point into the same list”. Run the drain to empty and refill preset and watch it happen.

Same input, different order

Feed the identical operations to the stack: LIFO returns to be not that or be, FIFO returns to be or not to be. The data structure, not the data, decides the answer — which is why choosing it is a design decision.

Where it shows up next

Breadth-first search is a queue: swap the queue for a stack and you get (almost) depth-first search. Part II makes that substitution explicit.

What to try in the animation

A word enqueues it; - dequeues. Same input as the stack — compare the output order.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• tobe.txt (course) — to be or not to - be - - that - - - is
• drain to empty and refill — a b - - c d -

Open Queue (linked list) in the player →

The rest of Stacks and queues

• Stack (linked list) Push and pop at the front of a singly linked list.
• Stack (resizing array) Keep items in an array and double it when it fills.