IB COMPUTER SCIENCE | B4

ABSTRACT DATA TYPES REVISION

Connect ADT contracts, linked lists, BSTs, sets and hash tables. Reconstruct worked examples, filter by topic or objective and build your revision list.

B4 | HL ONLY

Filters retain all selections, including hidden cards. Your complete revision list remains available.

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.

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

Main BST for revision 20 30 40 50 60 70 80
Main BST for revision. The root is pink; absent children are omitted.

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

After deleting 50 and preserving successor child 65 20 30 40 60 65 70 80
After deleting 50 and preserving successor child 65. The root is pink; absent children are omitted.

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

Shared club membership for revision A | Robotics B | Coding S01 S02 S03 S04
Shared club membership for revision. Shading marks the result region; each ID belongs in one region.
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.