YOUR B4 REVISION ROUTE | HL ONLY
This page covers B4.1.1 to B4.1.6: ADT specifications, evaluation and construction of linked lists, binary search trees, sets and hash-table mechanics. All B4 content on this page is HL-only.
Revise by reconstructing operations on paper before reading the worked results. For a linked structure, track references and metadata; for a BST, preserve ancestor bounds; for set operations, identify the membership rule; for hashing, state the capacity and collision policy.
There are 180 flashcards, 30 for each objective. Filter by topic or individual objective, flip a card after answering and select uncertain ideas. The revision list retains hidden selections and can be copied. Selections last while this page is open.
B4.1.1 | SPECIFICATION BEFORE REPRESENTATION
An abstract data type describes possible logical data or states and associated operations with their meanings. The representation is the concrete storage and code used to provide those behaviours. A caller should depend on the contract rather than internal fields.
A stack ADT promises LIFO behaviour. It can use an array-backed sequence with the top at one end, or linked nodes with the top at the first node. A list, set and map have different logical contracts even if some implementations share storage machinery.
Do not confuse an ADT with an abstract class. A concrete class or module can implement an ADT. An interface or abstract class may declare operations, but method names and signatures alone do not prove correct semantics.
WORKED | CONTRACTS AND OBSERVABLE BEHAVIOUR
| Stack operation | Result | Logical state bottom to top |
|---|---|---|
| Create | Empty stack | [] |
| push A, then push B | No useful result specified | [A,B] |
| peek | B, without removal | [A,B] |
| pop | B | [A] |
| pop | A | [] |
| pop on empty | Documented failure | [] |
A precondition describes the situation required for normal success. A postcondition states the promised result or change. An invariant holds across valid states, such as size matching the stored element count. Specify empty and full policies rather than assume them.
A compatible implementation can replace another if it preserves all required observations, including failure, capacity and any explicit performance requirements. A bounded stack can reject a request an unbounded-in-the-model stack would accept; matching method names does not hide that contract change.
CHOOSE THE ADT FROM THE QUESTION
| Required behaviour | ADT | Reason |
|---|---|---|
| Most recent saved action first | Stack | LIFO removal |
| Earliest waiting job first | FIFO queue | First-arrival removal |
| Meaningful numbered positions | List | Sequence and position |
| Unique member IDs | Set | Membership without duplicates |
| ID associated with a record | Map | Lookup by key |
The ADT does not determine a universal complexity. ListStack append is amortized constant time in a standard dynamic-array model, while linked-stack push uses constant link work under allocation assumptions. Cost depends on the stated representation.
In an explanation, connect the interface to a benefit: because the caller uses push and pop rather than array indexes, a compatible linked implementation can replace the storage without changing those caller operations.
B4.1.2 | EVALUATE THE THREE LINKED FORMS
| Form | Structure | Strength | Relevant cost |
|---|---|---|---|
| Singly linear | One next link; final next absent | Simple forward processing and head operations | No direct backward route |
| Doubly linear | next and prev; outer ends absent | Two-way movement and known-node unlinking | Extra reference and reciprocal updates |
| Circular | End returns to start; can be singly or doubly | Repeated cycling | Traversal and singleton rules need care |
Nodes need not occupy adjacent memory locations. Array-backed reference slots are contiguous, while referenced objects themselves may be elsewhere. Linked nodes add link and allocation overhead; arrays may reserve spare capacity. Neither representation universally uses fewer bytes.
Evaluate a whole task. A splice after a known predecessor has constant-size link work, but first finding it by value can take O(n). A tail reference helps singly linked append; it does not directly supply the predecessor needed for arbitrary tail removal.
WORKED | COMPARE COSTS WITH ASSUMPTIONS
| Operation | Resizable array | Singly: head and tail | Doubly: head and tail |
|---|---|---|---|
| Arbitrary indexed access | O(1) | O(n) | O(n) worst case |
| Search unsorted values | O(n) | O(n) | O(n) |
| Prepend | O(n) shifting | O(1) | O(1) |
| Append | Amortized O(1) | O(1) link work | O(1) link work |
| Remove last item | Amortized O(1), allowing resize costs | O(n) predecessor location | O(1) unlinking |
| Edit at known internal place | Usually O(n) shifting | O(1) if predecessor route known | O(1) if required node known |
These are standard asymptotic models, not measured seconds. Array locality, node allocation, element type and runtime overhead affect actual timings. A doubly linked list can walk from the nearer endpoint, but arbitrary index access remains linear in the worst case.
B4.1.3 | CONSTRUCT SINGLY LINKED OPERATIONS
| Task | Reference updates and boundaries |
|---|---|
| Append | Link old tail to new node; on empty also set head; update tail and size |
| Prepend | New.next = old head, then move head; on empty also set tail |
| Insert X after A | Preserve old A.next in X.next before assigning A.next = X |
| Delete current | Change head if first; otherwise previous.next = current.next |
| Delete tail / only node | Update tail to previous; only-node removal leaves both endpoints absent |
Move a temporary current during traversal instead of consuming head. Check that current is not None/null before reading its fields. find returns the first matching node in the lesson implementation; absent-target insert/delete returns False without mutation.
Duplicate values can belong to distinct nodes. Use identity when checking whether a particular node is tail or whether a circular traversal has returned to its start. Count one added or removed node exactly once.
WORKED | PRESERVE THE SUCCESSOR BEFORE REDIRECTING
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.next = c
x = Node(15, a.next)
a.next = x
current = a
result = []
while current is not None:
result.append(current.value)
current = current.next
print(result)
# [10, 15, 20, 30]
X first remembers B, then A is redirected to X. Reversing that order without another preserved reference can lose the old route or create a self-link. The node values did not shift; references changed the sequence.
To remove B now, X.next = B.next bypasses it. Other live references can still reach B, so unlinking is separate from memory reclamation.
DOUBLY LINKED | REPAIR BOTH DIRECTIONS
| Insert X between A and B | Delete B between A and C |
|---|---|
| X.prev = A; X.next = B | A.next = C |
| B.prev = X | C.prev = A |
| A.next = X | Detach B’s old links after reconnection |
Handle absent neighbours by updating head or tail instead of dereferencing a missing node. The lesson’s endpoint branches also remove the only node correctly. After a complete operation, head.prev and tail.next are absent.
Forward output can look correct while backward links remain broken. Compare reverse traversal with the reversed forward sequence. For every adjacent pair, the forward and backward routes must agree.
CIRCULAR | APPEND, PREPEND AND ROTATE
The lesson’s circular singly linked representation stores tail and size, with head derived as tail.next when non-empty. Empty means tail is None; a singleton has tail.next is tail.
For non-empty append and prepend, connect the new node between old tail and old head. Append then moves tail to the new node; prepend keeps the old tail, making the new node the derived head. rotate advances tail to its successor without changing node links.
For deletion, begin previous at tail and current at head. Bypass a match, update tail if the last node is removed and handle the only-node case separately by setting tail None. Detach the removed next reference and decrement size.
WORKED | A CIRCULAR TRAVERSAL WITH DUPLICATE VALUES
class Node:
def __init__(self, value):
self.value = value
self.next = None
a, b, c = Node(7), Node(7), Node(9)
a.next, b.next, c.next = b, c, a
head = a
current = head
values = []
while True:
values.append(current.value)
current = current.next
if current is head:
break
print(values)
# [7, 7, 9]
This fragment starts with a known non-empty valid circle. A general function first handles an empty head. Equal stored values do not indicate that the traversal has returned to its starting node.
The alternative range(size) visits a bounded number of nodes and depends on correct size metadata. Waiting for None in a valid non-empty circle never reaches the boundary.
LINKED-LIST TESTS AND EVALUATION
Test empty, singleton and multi-node structures; head/middle/tail edits; duplicate and absent targets; and reuse after all nodes have been removed. Verify endpoint metadata as well as the displayed sequence.
A cursor-based editor with frequent local edits and backward movement can justify doubly linked nodes. A browser dominated by random numbered jumps can favour an array-backed sequence. A circular list can model turns, but it is not automatically superior to every ring-buffer or indexed alternative.
State what is already known before quoting costs. A public delete_first(value) that searches is O(n) worst case even when the final doubly linked unlinking is O(1).
B4.1.4 | BST ORDERING AND SKETCHING
A strict unique-key BST requires every left-subtree key to be smaller than the node key and every right-subtree key larger. Ancestor bounds apply throughout the subtree. A 60 under the right child of 30 still violates a root 50 if it lies inside 50’s left subtree.
A binary node has at most two children, not necessarily exactly two. Sketch from the insertion order: follow comparisons until an absent child is reached and attach the new leaf. The lesson ignores duplicate insertions and returns False.
Insertion order affects shape. An ordinary BST does not automatically rebalance; sorted insertion can produce a chain.
WORKED | SEARCH AND THE THREE TRAVERSALS
| Task on the main tree | Result |
|---|---|
| Search 60 | 50, 70, 60 |
| Search absent 99 | 50, 70, 80, then absent right child |
| Inorder: left, node, right | 20, 30, 40, 50, 60, 70, 80 |
| Preorder: node, left, right | 50, 30, 20, 40, 70, 60, 80 |
| Postorder: left, right, node | 20, 40, 30, 60, 80, 70, 50 |
Inorder is ascending because the BST invariant already orders the subtrees. It does not rearrange the tree. Preorder and postorder change when the node is recorded relative to its recursive child calls.
Minimum follows left links to the end; maximum follows right. Search can exclude the other subtree after a comparison only because the full ordering invariant is valid.
BST DELETION | PRESERVE ALL REMAINING KEYS
| Case | Replacement of the incoming reference |
|---|---|
| Leaf | None/null |
| One child | The existing child subtree |
| Two children | Copy a suitable successor/predecessor key and remove its old occurrence |
For a two-child target, the inorder successor is the minimum of the right subtree: go right once, then left as far as possible. It has no left child but can have a right child. That child must be reconnected when removing the original successor.
The helper returns the new subtree root; assign it back to the relevant parent child or to tree.root. Ignoring that result can break root deletion. For record-bearing nodes, key and associated record must move consistently under the chosen identity policy.
WORKED | A SUCCESSOR WITH A RIGHT CHILD
Before this deletion, root is 50 and its successor is 60, with right child 65. Copy 60 into the root position, then remove the original 60 from the right subtree by setting 70.left to 65.
The final inorder sequence is 20, 30, 40, 60, 65, 70, 80. Exactly key 50 disappears. Key 60 occurs once, 65 remains, and both subtree bounds still hold.
BST COSTS AND INVARIANTS
Use height as edges on the longest downward path: a singleton has height 0. A successful path can visit h + 1 nodes. Search, insertion and deletion follow O(h) paths under the standard model.
Well-controlled height supports O(log n) paths; a skewed tree has O(n) worst-case paths. Full traversal remains O(n) visits in either shape. Recursive traversal and deletion can retain O(h) call frames, and returned traversal values need O(n) output space.
Test inherited bounds, membership and deletion cases independently. Include an empty tree, root-only, one-child root, missing keys, duplicates, an immediate-right successor and a deeper successor with its own right child.
B4.1.5 | SETS: UNIQUENESS AND MEMBERSHIP
A set represents distinct members without an intrinsic index order. Adding an existing equal member does not create another occurrence. Unordered does not require random display: it means the abstract contract does not promise that sequence.
Python uses set() for an empty set; {} is a dictionary. {"S01"} is one ID, while set("S01") constructs a set of characters. in tests element membership; <= and issubset test inclusion of every member of a set.
Keep event data separately if order or repeats matter. A set of scanned IDs answers distinct attendance questions but cannot recover how many times each student scanned.
WORKED | UNION, INTERSECTION AND DIRECTIONAL DIFFERENCE
| A = {S01,S02,S03}, B = {S03,S04} | Result |
|---|---|
| A union B | {S01,S02,S03,S04} |
| A intersection B | {S03} |
| A minus B | {S01,S02} |
| B minus A | {S04} |
Union is inclusive OR; intersection is AND. Both are commutative. Difference is directional, so identify which group the question starts from before excluding the other.
Python |, & and - produce new sets. Java addAll, retainAll and removeAll mutate the receiver, so start with a copy if the original membership must be preserved.
SUBSETS, SUPERSETS AND EMPTY MEMBERSHIP
| Relation or law | Meaning / result |
|---|---|
| Team <= Robotics | Every Team member occurs in Robotics; equality allowed |
| Robotics >= Team | The same inclusion viewed as superset |
| Team < Robotics | Inclusion with unequal membership: proper subset |
| Empty <= A | True for every set A |
| A <= A; A < A | True; False |
| A intersection empty; A minus A | Empty; empty |
In Java, robotics.containsAll(team) checks whether Team is a subset of Robotics, equivalently whether Robotics is a superset. A smaller finite size distinguishes proper inclusion. One overlapping member is insufficient.
Python == and Java Set.equals compare set membership. Java == checks reference identity. Python remove raises KeyError for an absent member; discard tolerates absence. Java Set.remove returns whether membership changed.
WORKED | PRESENT, ABSENT AND UNEXPECTED
registered = {"S01", "S02", "S03", "S04"}
scans = ["S01", "S03", "S01", "S99"]
scanned = set(scans)
present = registered & scanned
absent = registered - scanned
unexpected = scanned - registered
print(sorted(present))
print(sorted(absent))
print(sorted(unexpected))
# ['S01', 'S03']
# ['S02', 'S04']
# ['S99']
Sorting creates a separate presentation list; it does not give the set a numbered order. An alias to a mutable set sees its changes, while copy() creates a separate shallow membership container.
Python set members and dict keys must be hashable. Java HashSet relies on consistent equals/hashCode. Agree identifier normalization deliberately instead of expecting S01 and s01 to be automatically treated as equal.
B4.1.6 | HASHING CONNECTS KEYS TO LOCATIONS
A hash table supplies one representation for sets and maps. Derive a hash, reduce or mix it into a valid bucket/slot range, then follow the collision policy and compare actual keys. The original key is still needed because location alone does not prove equality.
In the toy division model with m = 7, keys 10, 17 and 24 all have index 3. They are unequal colliding keys and must all remain stored. An equal-key map update replaces a value without increasing the distinct-key count.
Hashing for collection lookup is not encryption or a password-storage design. Good distribution and reasonably inexpensive key processing support expected performance; no small toy formula is universally good.
COLLISION POLICIES | CHAINING AND PROBING
| Policy | Storage and lookup | Deletion rule |
|---|---|---|
| Separate chaining | Bucket 3 holds pairs for 10,17,24; inspect stored keys | Remove only the matching pair |
| Linear probing | Those keys occupy slots 3,4,5; follow the same wrapped route for lookup | Preserve later routes using a tombstone or a correct cluster-repair method |
In open addressing, a never-used slot can terminate a valid search, but DELETED cannot. If 17 is removed from slot 4, lookup for 24 must pass that marker to reach slot 5. Probe loops must be bounded for full or marker-filled tables.
Insertion may remember a tombstone but must still check for an equal key farther along before creating a new entry. Updating existing 24 at slot 5 must not create another 24 at slot 4. An absent new 31 can reuse that marker under the stated policy.
WORKED | LOAD FACTORS AND REHASHING
| Calculation | Result / meaning |
|---|---|
| 3 live entries / 7 buckets | α ≈ 0.429 |
| 6 entries / 8 slots | α = 0.75 |
| 7 entries / 16 slots after growth | α = 0.4375 |
| 10,17,24 under MOD 7 | All index 3 |
| 10,17,24 under MOD 11 | Indices 10,6,2 |
Current load is n/m; a growth threshold is a separate policy. Chaining can have α > 1 because a bucket can hold several entries. Ordinary open addressing has at most one live entry per slot; tombstones can still lengthen probes independently of the live-entry count.
When capacity changes, reinsert or reposition entries according to the new index rule. Simply expanding storage and keeping the old locations can make lookup miss keys. Resizing may be expensive for one operation even when sequence-level amortized costs are good.
PYTHON AND JAVA | DO NOT CONFUSE THE APIS
| Property | Python | Java examples |
|---|---|---|
| Map | dict | HashMap used through Map |
| Map membership | key in d | containsKey(key) |
| Missing lookup | Index raises KeyError; get can supply default | get can return null; containsKey distinguishes stored null from absence |
| Set | set | HashSet used through Set |
| Map iteration order | dict preserves insertion order | HashMap makes no sequence promise |
| Set iteration order | set makes no sequence promise | HashSet makes no sequence promise |
HashSet uses a backing HashMap, but its public contract is distinct membership rather than separate user values. Real implementations need not match the toy chained or linear models exactly.
Equal keys must have equal hashes; unequal keys may collide. Keep hash/equality-relevant key state stable while stored. Expected constant-time operations require appropriate distribution and capacity assumptions; a list-chained bucket can take O(n) to search.
WORKED | DICTIONARY KEYS AND ORDER
students = {10: "Maya", 17: "Leo", 24: "Sam"}
students[17] = "Leo updated"
print(24 in students)
print("Sam" in students)
print("Sam" in students.values())
print(list(students))
# True
# False
# True
# [10, 17, 24]
Membership in a dictionary checks keys. Updating existing 17 changes its value but not its insertion position. Ordered iteration does not mean binary search is used for lookup.
Use the lesson’s integer-only chained map to practise forced collisions, updating, removing and rehashing. Test the logical mappings against an independent dictionary rather than depending only on a visually plausible bucket table.
COMMON MISTAKES | STRUCTURE AND ORDER
| Mistake | Correction |
|---|---|
| ADT is the same as abstract class | Logical contract differs from a language mechanism |
| All linked edits are O(1) | Include locating the node and required predecessor |
| A circular walk waits for None | Use a correct identity/size stopping rule |
| A valid BST needs only local parent checks | Propagate ancestor bounds |
| Every BST guarantees logarithmic paths | Height depends on shape unless balancing is enforced |
| Inorder is a separate sorting process | The visit order exploits the existing BST invariant |
COMMON MISTAKES | MEMBERSHIP AND HASHING
| Mistake | Correction |
|---|---|
| One overlap proves subset | Every required member must be included |
| Difference can be reversed freely | A minus B and B minus A answer different questions |
| A collision means duplicate key | Compare actual keys |
| A deleted slot is never used | A tombstone preserves probe continuation |
| First tombstone always permits immediate insertion | First establish whether the key exists farther along |
| Load factor counts collisions | It relates current entries to capacity |
| Every hashed operation is guaranteed O(1) | State assumptions, collisions and rebuild costs |
EXPLAIN, CONSTRUCT AND EVALUATE
For explain, identify the mechanism and consequence: a tombstone preserves the probe route, therefore lookup continues to later colliding keys. A connective should express an accurate causal link rather than decorate a vague claim.
For construct, supply complete initial state, link updates, endpoint branches and stopping rules. For a diagram, show exact child or next/prev relationships and a clear root or head. For trace, separate references from stored values and output.
For evaluate, name the workload, weigh costs and reach a supported judgement. A cursor-based linked editor, ordered tree catalogue and hashed ID membership service need different trade-offs. Use selected flashcards to target weaknesses, then attempt the separate end-of-topic review.