Fundamentals of ADTs

The **operations** available and what they mean — not how the data is stored.

**ADT.** It promises push, pop, peek and last-in-first-out order. An array or a linked list is how you build one.

So it can be **replaced** without changing any calling code, because callers only ever depended on the operations.

A **set** — duplicates cannot be stored, so the structure guarantees it rather than the programmer remembering to check.

By the operation the program performs **most**, with its complexity — and what the alternative would cost.

A **value** and a **reference to the next node**. Nothing else, and no node needs to sit beside another in memory.

There is no calculation that locates a node — you must start at the head and **follow every reference** in turn.

**Singly** points forwards only. **Doubly** points both ways, at the cost of a second reference per node. **Circular** links the last node back to the first, so there is no null end.

It gives up **direct access** (O(n) to reach position n) and gains **cheap insertion and deletion** (O(1) once in position), plus a size that grows and shrinks.

Array elements are **contiguous**, so reading one pulls its neighbours into cache. Linked-list nodes are scattered, so each hop risks a cache miss.

A **Node** holding a value and a reference to the next, and a **head** reference pointing at the first node.

**Point the new node forwards first** (new.next ← prev.next), then repoint the previous node (prev.next ← new). The other order overwrites the only reference to the rest of the list.

By **routing around it**: prev.next ← target.next. Nothing is erased — the node simply becomes unreachable.

There is no previous node to reroute, so the head itself moves: head = head.next.

When current returns to the **head**. There is no None to test for.

For **every** node, all values in its left subtree are smaller and all in its right subtree are larger — every descendant, not just the children.

Each comparison says which side the value must be on, so an **entire subtree** is discarded without being examined. About log₂ n comparisons when balanced.

Every value in **ascending order** — left subtree, node, right subtree — with no sorting step.

Every value goes the same direction, so the tree **degenerates into a line**: height n, search O(n), exactly like a linked list.

It is replaced by its **in-order successor** — the smallest value in its right subtree — which preserves the ordering rule.

**No duplicates** and **no order** — both enforced by the structure rather than by the programmer.

**Union** everything in either · **intersection** only what is in both · **difference** in the first and not the second.

**No.** With a = {1,2,3} and b = {3,4}: a − b = {1,2} but b − a = {4}. Difference is the one operation whose order matters.

The value itself computes where it would be stored, so nothing is searched for. A list must compare against every element — O(n).

When the program needs **position or order** — a set has neither, and no index to ask with.

It runs the key through a **hash function**, takes the result **modulo the table size**, and goes straight to that bucket. The address is computed, not searched for.

**Deterministic** (same key, same bucket, always), **fast** (it runs on every operation) and **uniform** (keys spread evenly).

There are more possible keys than buckets, so two keys must eventually map to the same one. It is a counting argument, not a defect.

**Chaining** stores colliding keys in a list inside the bucket. **Open addressing** puts them in the next free bucket, so the table can never hold more items than buckets.

**O(1) on average, O(n) in the worst case** — the worst case being a hash function that clusters every key into one bucket.