Module 1 in One Sitting

A doubly linked list adds a backward link: one address per node, insertion goes from two assignments to four, and it buys O(1) deletion of a held node, O(1) deletion of the last node, and backward traversal. Its invariant is that x.next.prev is x, and both chains must always agree.

Polynomials are the named application: one node per non-zero term, exponents strictly decreasing, no zero coefficients. Addition is a one pass merge, O(m + n). The array representation is better for dense polynomials and for multiplication.

Stacks

Access at one end only, the top. Last in, first out. push, pop, peek, is_empty, size, all O(1).

Underflow is popping an empty stack and applies to every implementation. Overflow is pushing onto a full one and applies only to a fixed capacity, so to the array version.

The array stack keeps top as the index of the topmost item, with -1 meaning empty. push increments then writes; pop reads then decrements. The linked stack makes the top the head of the list, because that is the only end where adding and removing are both free.

Applications. Balanced delimiters: a counter fails because it forgets which kind of bracket was opened, and accepts ([)]. Expression conversion: infix needs precedence, associativity and brackets, while postfix and prefix need none, which is why machines use them. Shunting yard converts; postfix is evaluated by pushing operands and applying operators to the top two, with the first value popped being the right operand.

2 ^ 3 ^ 2 is 512, not 64: the exponent is right associative.

Queues

Add at the rear, remove from the front. First in, first out. All operations should be O(1).

The naive array queue drifts: both markers only move up, so every dequeue abandons a cell, and the queue reports itself full while nearly empty. Shifting on dequeue fixes the space and makes dequeue O(n). The circular queue fixes both by advancing indices with (index + 1) mod capacity.

In a circular queue, empty and full both give front == rear. The three answers are: keep a count (count == 0, count == capacity); sacrifice one cell (front == rear, (rear + 1) mod capacity == front); or keep a flag. Do not mix one method's test with another's.

The linked queue takes the head as front and the tail as rear. Its two traps are enqueueing onto an empty queue, which must set both pointers, and the dequeue that empties it, which must clear the rear.

Job scheduling is the named application. Turnaround is completion minus arrival; waiting is turnaround minus burst. First come first served suffers the convoy effect: one long job delays every short one behind it.

A deque is open at both ends and contains the stack and the queue as special cases; the restricted structures are still preferred, because a structure that permits only what is needed cannot be misused.

The six "advantages and disadvantages", in one line each

MU asks this per structure, and they are different answers.

Singly linked list. For: O(1) insertion and deletion at a known position, no fixed size, no wasted capacity, no contiguous block needed. Against: O(n) access, an address per item, no backward link, poor cache behaviour, no binary search even when sorted.

Doubly linked list. For: O(1) deletion of a held node and of the last node, O(1) insertion before a node, backward traversal. Against: a second address per item, four assignments per insertion, two chains to keep in step.

Stack. For: all operations O(1), an exact match for nested problems, impossible to misuse. Against: only the top is reachable, no search, traversal destroys it, fixed capacity on the array version.

Queue. For: all operations O(1), fair with bounded waiting, decouples producer from consumer. Against: only the front is reachable, no search, and it cannot serve by urgency.

What Module 1 cannot do

None of these structures can find anything without looking at everything: not the most urgent job, not a particular value, not the largest item. Searching is O(n) on every one of them except a sorted array, which cannot then be cheaply changed.

Module 2 is the answer to exactly that.

The five mark answers most likely to be asked

1. Write the ADT for a stack, or a queue, or a linked list. (Operations, behaviour, errors, costs. No

code.)

1. Advantages and disadvantages of one named structure. (Its own, not another's.)
2. Convert an infix expression to postfix or prefix, with the stack traced.
3. Evaluate a postfix or prefix expression, with the stack traced.
4. Why does a circular queue need a count or a sacrificed cell?
5. Insert or delete a node at a given position in a linked list, with the pointer assignments in order.
6. Add two polynomials represented as linked lists.
7. First come first served scheduling: compute turnaround and waiting times, and name the convoy effect.

Test yourself

1. Give the access, front insertion and search costs of an array and of a singly linked list. Array: O(1) access, O(n) front insertion, O(n) search or O(log n) if sorted. Singly linked list: O(n) access, O(1) front insertion, O(n) search.

2. State the ordering rule for linked list pointer assignments and what happens when it is broken. Point the new node forward before redirecting its predecessor. Reversed, the new node points at itself, the list gains a cycle and the following nodes become unreachable while remaining intact.

3. Why does a counter fail to check balanced brackets? It records how many brackets are open and not which kinds, so it accepts crossing pairs such as ([)] and mismatched pairs such as (].

4. Give the empty and full tests for both standard circular queue methods. With a count: empty is count == 0, full is count == capacity. Sacrificing a cell: empty is front == rear, full is (rear + 1) mod capacity == front.

5. What does a doubly linked list buy, and what does it cost? It buys O(1) deletion of a held node and of the last node, O(1) insertion before a node, and backward traversal. It costs one address per node, four assignments per insertion, and a second chain to keep in step.

6. What single thing can none of Module 1's structures do? Find anything without examining everything: the most urgent item, a particular value or the largest. Only a sorted array searches quickly, and it cannot then be changed cheaply.