A Queue on Links

Get access to whole semester resourcesSemester Pass

Chapter Forty-Three

Syllabus topic Module 1, "Queues: linked representations"

Pages 131 to 133 of 411

In one line

A linked queue removes from the head and adds at the tail, so both operations are O(1) with no shifting, no drift and no maximum.

Why these two ends

Chapter 18 established the costs of a singly linked list:

At the head	At the tail
add: O(1)	add: O(1) with a tail pointer
remove: O(1)	remove: O(n), even with a tail pointer

A queue needs add at one end and remove at the other. The only assignment of ends that gives O(1) for both is: remove from the head, add at the tail.

The other way round is a trap. Adding at the head is cheap, but removing from the tail needs the node before the last, and a singly linked list can only find it by walking. That is the reasoning, and it is what an examiner wants when asking why the front is the head.

Built and run

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

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


class LinkedQueue:
    """front is the head; rear is the tail."""

    def __init__(self):
        self.front_node = None
        self.rear_node = None
        self.n = 0

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

    def size(self):
        return self.n

    def enqueue(self, item):
        node = Node(item)
        if self.rear_node is None:                  # the empty case
            self.front_node = self.rear_node = node
        else:
            self.rear_node.next = node
            self.rear_node = node
        self.n += 1

    def dequeue(self):
        if self.front_node is None:
            raise IndexError("dequeue from an empty queue: underflow")
        node = self.front_node
        self.front_node = node.next
        if self.front_node is None:                 # the queue just emptied
            self.rear_node = None
        node.next = None
        self.n -= 1
        return node.data

    def front(self):
        if self.front_node is None:
            raise IndexError("front of an empty queue: underflow")
        return self.front_node.data

    def snapshot(self):
        out, walk = [], self.front_node
        while walk is not None:
            out.append(walk.data)
            walk = walk.next
        return out


q = LinkedQueue()
print("new: empty =", q.is_empty(), "| size =", q.size())

for person in ("A", "B", "C"):
    q.enqueue(person)
    print("enqueue %s -> %-20s front=%s rear=%s"
          % (person, str(q.snapshot()), q.front(), q.rear_node.data))

print()
print("dequeue ->", q.dequeue(), "| now", q.snapshot())
print("dequeue ->", q.dequeue(), "| now", q.snapshot())
print("dequeue ->", q.dequeue(), "| now", q.snapshot())
print("empty again:", q.is_empty(), "| rear is also cleared:", q.rear_node is None)

print()
q.enqueue("reused")
print("enqueue after emptying:", q.snapshot(), "| front == rear:",
      q.front_node is q.rear_node)

print()
big = LinkedQueue()
for i in range(100000):
    big.enqueue(i)
for _ in range(50000):
    big.dequeue()
print("100,000 in and 50,000 out: size =", big.size(),
      "| front =", big.front(), "| no capacity was ever declared")

print()
try:
    LinkedQueue().dequeue()
except IndexError as e:
    print("underflow:", e)

new: empty = True | size = 0
enqueue A -> ['A']                front=A rear=A
enqueue B -> ['A', 'B']           front=A rear=B
enqueue C -> ['A', 'B', 'C']      front=A rear=C

dequeue -> A | now ['B', 'C']
dequeue -> B | now ['C']
dequeue -> C | now []
empty again: True | rear is also cleared: True

enqueue after emptying: ['reused'] | front == rear: True

100,000 in and 50,000 out: size = 50000 | front = 50000 | no capacity was ever declared

underflow: dequeue from an empty queue: underflow

A Queue on Links

No drift, no shifting, no capacity, and the 50,000 items that passed through cost nothing extra: compare chapter 42, where 4,000 items cost nearly eight million element moves.

The two cases that break student code

Both are visible in the run above and both are about the rear pointer, which is the thing the structure has to remember.

Enqueue onto an empty queue. There is no rear node to attach to, so front and rear must both be set to the new node. Forgetting this attaches the node to nothing and the queue stays empty.

Dequeue that empties the queue. The front becomes null, and the rear must be cleared too. Forgetting this leaves the rear pointing at a node that is no longer in the queue, and the next enqueue attaches the new node to a removed node. The queue then looks empty and loses everything added afterwards.

The run tests both: the queue is emptied completely, the rear is checked to be null, and then a new item is enqueued and found correctly.

Array against links, for a queue

	Array (circular, chapter 44)	Linked
enqueue	O(1)	O(1)
dequeue	O(1)	O(1)
Capacity	fixed	none
Overflow	possible	only when memory runs out
Memory per item	one cell	one cell plus an address
Wasted space	reserved capacity	none
Cache behaviour	good	poorer
Complexity to write	index arithmetic, full-or-empty problem	two pointers, two empty cases

Both are O(1) once written correctly. Choose the circular array when the maximum is known and the contiguous memory is worth having, and links when it is not.

Quick revision

The front is the head and the rear is the tail. That is the only assignment giving O(1) both ways on a

singly linked list.

Removing from the tail would need the node before it, which requires a walk.
Enqueue onto an empty queue sets both front and rear to the new node.
Dequeue that empties the queue must clear the rear as well, or the next enqueue attaches to a removed

node and the queue silently loses everything.

No capacity, so no overflow; underflow still applies.
Against the circular array: same costs, no capacity, but an address per item and poorer cache

behaviour.

Test yourself

1. Which end of the list is the front of the queue, and why that way round? The head is the front. Removing from the head is O(1) while removing from the tail would need the node before it, which a singly linked list can only find by walking.

A Queue on Links

2. What must enqueue do when the queue is empty? Set both the front and the rear pointers to the new node, since there is no rear node to attach to.

3. What must dequeue do when it removes the last item, and what breaks if it does not? Clear the rear pointer as well. Otherwise the rear still points at the removed node, and the next enqueue attaches to a node outside the queue, so the queue appears empty and loses the items added after it.

4. Can a linked queue overflow? Not in the ADT's sense; it has no fixed capacity and fails only when the machine runs out of memory.

5. Compare the cost of passing 4,000 items through a linked queue and through the shifting array queue of chapter 42. The linked queue does a constant amount of work per item. The shifting queue performed 7,998,000 element moves for 4,000 items, because each dequeue shifted everything down.

6. When would you prefer the circular array queue? When the maximum size is known, since it avoids an address per item and its contiguous storage uses the cache better.

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