B4.1 · Book pp. 454–480

Fundamentals of abstract data types

HL only This whole section is for Higher Level students.

You have used lists and dictionaries without seeing inside them. Here you build these structures yourself, and learn when each one fits.

B4.1.1 What is an abstract data type?

An abstract data type (ADT) is defined by what it does, and not how it does it. A stack is “push, pop, peek”, whether it is built on an array or a linked list.

Abstraction: users see operations, not details.
Encapsulation: data changes only through those operations.
Reuse: the same ADT works in many programs.
Modularity: one part can be tested, or swapped, alone.

⚠️ Common mistake

The interface is which operations exist. The implementation is how they work. Keep the two apart.

In this section

B4.1.2 Evaluate linked lists.
B4.1.3 Construct and apply linked lists: singly, doubly and circular.
B4.1.4 Explain the structures and properties of binary search trees.
B4.1.5 Construct and apply sets.
B4.1.6 Explain the core principles of ADTs, including hash tables.

Next: linked lists →

B4.1.2 Linked lists

A linked list is a chain of nodes. Each node holds data and a pointer to the next node. The head points to the first node, and the tail is the last.

Singly linked: one pointer. The tail points to null.
Doubly linked: next and previous pointers, so you can go both ways.
Circular: the tail points back to the head.

	Linked list	Array
Size	Grows and shrinks at runtime	Fixed once created
Memory	Allocated per node, plus a pointer each	One contiguous block, reserved up front
Access	Sequential from the head: O(n)	Direct by index: O(1)
Insert or delete	Pointers change: O(1) once at the position	Items must shift: O(n)
Binary search	Impractical, as there is no index	Possible if sorted

⚠️ Common mistake

On a diagram, label the head, and show where the tail points. When inserting, set the new node’s pointer before changing the previous node’s pointer, or the rest of the list is lost.

✏️ Book correction

The book says the operating system manages the heap. The operating system gives memory to a program, but the language’s runtime allocates objects within it.

Next: coding linked lists →

B4.1.3 Coding linked lists

One class is the node, and a second holds the head. Every operation walks along the list with a current variable.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def print_list(self):
        current = self.head
        while current is not None:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def insert_at_beginning(self, data):
        node = ListNode(data)
        node.next = self.head
        self.head = node

    def insert_at_end(self, data):
        node = ListNode(data)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node

    def insert_after(self, target, data):
        current = self.head
        while current is not None:
            if current.data == target:
                node = ListNode(data)
                node.next = current.next     # this line first!
                current.next = node
                return
            current = current.next
        print(target, "not found")

    def delete(self, data):
        current = self.head
        previous = None
        while current is not None and current.data != data:
            previous = current
            current = current.next
        if current is None:
            print(data, "not found")
        elif previous is None:
            self.head = current.next        # it was the head
        else:
            previous.next = current.next    # skip over it

    def search(self, key):
        current = self.head
        while current is not None:
            if current.data == key:
                return True
            current = current.next
        return False

names = LinkedList()
names.insert_at_end("Niran")
names.insert_at_end("Fah")
names.insert_at_beginning("Mali")
names.insert_after("Niran", "Asha")
names.print_list()
names.delete("Mali")
names.delete("Ton")
names.print_list()
print(names.search("Asha"))

✏️ Book corrections

The book’s Java deleteNode takes a parameter called data, then uses a variable called key. That will not compile. Use one name.
Its Python sets current = None with the comment “Free the old head”. This only clears a local variable. What frees the node is that nothing points to it any more.

Try it: add a method that counts the nodes

Start a counter at 0, walk from the head to None, and add 1 at each node. It takes O(n), unless you store the size in a variable and keep it updated.

Next: binary search trees →

B4.1.4 Binary search trees

Each node has at most two children. Everything in a node’s left subtree is smaller than it, and everything in its right subtree is larger. The top node is the root, and a node with no children is a leaf, at whatever depth.

Search: compare, then go left or right, until you find the key or reach null. O(log n) when balanced, and O(n) when the tree is a chain. Try the sorted button to see why.
In-order (left, node, right) gives sorted output.
Pre-order (node, left, right) is useful for copying a tree.
Post-order (left, right, node) suits deleting a tree, as children go first.

Deleting a node

A leaf: set the parent’s pointer to null.
One child: link the parent directly to the child.
Two children: copy in the in-order successor (the smallest value in the right subtree), then delete the successor.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node

def search(node, key):
    while node is not None:
        if key == node.value:
            return True
        node = node.left if key < node.value else node.right
    return False

def in_order(node):
    if node is not None:
        in_order(node.left)
        print(node.value, end=" ")
        in_order(node.right)

root = None
for v in [10, 5, 12, 3, 8, 16]:
    root = insert(root, v)

in_order(root)
print()
print(search(root, 8), search(root, 7))

# Task: add pre_order, post_order and a function for the tree's height.

✏️ Book note

One practice question asks for a BST whose in-order output runs Zebu down to Armadillo. An ordinary BST gives ascending order, so this needs larger values on the left. Say so if you answer it.

Next: sets →

B4.1.5 Sets

A set is an unordered collection of unique elements. You can add and remove items, but not index them. Membership tests are very fast, which makes sets ideal for usernames or for spotting duplicates. Java uses HashSet.

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a | b)      # union
print(a & b)      # intersection
print(a - b)      # difference

a.add(9)
a.remove(1)
print(2 in a)

small = {3, 4}
print(small <= b, b >= small)

print(set(["Mali", "Niran", "Mali"]))   # duplicates vanish

# Friend suggestions
mine = {"Asha", "Fah"}
theirs = {"Asha", "Niran", "Ton"}
print("In common:", mine & theirs)
print("Suggest:", theirs - mine)

✏️ Book correction

Its Java superset check, B.containsAll(A) && !A.containsAll(B), has the comment “False”, but with its data it prints true. That check is also for a proper superset. A plain superset test is just B.containsAll(A).

Next: hash tables →

B4.1.6 Hash tables

A hash table stores data in an array, using a key instead of an index. A hash function turns the key into an index. Search, insert and delete average O(1), but can fall to O(n) when there are many collisions.

"name": 110 + 97 + 109 + 101 = 417, and 417 mod 10 = 7

A collision is when two keys give the same index. The load factor shows how full the table is, as entries ÷ slots. Above about 0.7, rehashing builds an array at least twice the size, ideally a prime length, and recalculates every position.

Method	How	For	Against
Chaining	Each slot holds a linked list	Simple, and copes with a full table	Extra memory, and long chains are slow
Open addressing	Items are placed in another empty slot	No pointers, so it uses less memory	Clustering, and deletion is awkward

Open addressing finds the next slot by linear probing (one step at a time), quadratic probing (growing steps), or double hashing (a second hash sets the step).

SIZE = 10

def hash_of(key):
    total = 0
    for letter in key:
        total = total + ord(letter)
    return total % SIZE

table = [[] for i in range(SIZE)]     # chaining

def put(key, value):
    chain = table[hash_of(key)]
    for pair in chain:
        if pair[0] == key:
            pair[1] = value           # update an existing key
            return
    chain.append([key, value])

def get(key):
    for pair in table[hash_of(key)]:
        if pair[0] == key:
            return pair[1]
    return None

put("name", "Mali")
put("mean", 72)        # same letters, so the same index!
put("age", 16)

print(hash_of("name"), hash_of("mean"))
print(get("name"), get("mean"), get("nope"))
print(table)

# Python's dict is a hash table, ready to use
d = {"name": "Mali"}
d["age"] = 16
del d["name"]
print(d)

✏️ Book corrections

It says chaining saves you from rehashing. Chaining will not overflow, but long chains drift to O(n), so real tables such as Java’s HashMap still rehash.
It says deleting from a chain is slow “due to the need to adjust pointers”. Changing pointers is quick. The cost is walking along the chain to find the item.

Next: review →

Quick quiz

1. An ADT is defined by…

2. The last node of a singly linked list points to…

3. When inserting mid-list, you first…

4. Each node in a doubly linked list has…

5. In a BST, a smaller value goes…

6. Which traversal of a BST gives sorted output?

7. To delete a BST node with two children, use its…

8. A set does not allow…

9. A − B gives elements…

10. Load factor is…

Exam-style questions

These are written for this site in the style of Paper 2. Answer on paper first, then open the mark points.

Outline three properties of an abstract data type. [3]
Mark points
- Users work through a defined interface [1].
- The implementation is hidden [1].
- It can be reused in other programs, or its implementation swapped [1].
Compare a linked list with an array for a list that changes often. [4]
Mark points
- Both store a sequence of items [1].
- A linked list changes size at runtime, while an array is fixed [1].
- A linked list inserts by changing pointers, while an array shifts items [1].
- An array has direct access, while a list is sequential [1].
Draw a doubly linked list holding Mali, Niran, Asha, Fah. [4]
Mark points
- Labelled head at Mali [1].
- Nodes in order, with data [1].
- Next and previous pointers between all nodes [1].
- Null at both ends [1].
Sketch the BST formed by inserting 40, 20, 60, 10, 30, 50, then state its pre-order traversal. [3]
Mark points
- 40 at the root, with 20 left and 60 right [1].
- 10 and 30 under 20, and 50 left of 60 [1].
- 40, 20, 10, 30, 60, 50 [1].
Explain why inserting sorted data into a BST is a problem. [2]
Mark points
- Each node gets only a right child, so the tree becomes a chain [1].
- Search falls from O(log n) to O(n) [1].
A = {2, 4, 6, 8} and B = {6, 8, 10}. State A ∪ B, A ∩ B and A − B. [3]
Mark points
- {2, 4, 6, 8, 10} [1]
- {6, 8} [1]
- {2, 4} [1]
A hash function is key MOD 100. State the index for 1042, and explain what happens if 3042 is then inserted, using chaining. [3]
Mark points
- Index 42 [1].
- 3042 also gives 42, which is a collision [1].
- It is added to the linked list at index 42 [1].
Describe how a hash table is rehashed. [3]
Mark points
- When the load factor passes a limit, make a larger array [1].
- Recalculate the hash of every key for the new size [1].
- Insert each item into the new array [1].

In-order
Pre-order
Post-order