B4 Abstract data types

Introduction

An abstract data type (ADT) describes a collection of data by the operations allowed on it and what each operation does, without saying how the data is stored. A program that uses a set only needs to add items, remove them and test membership; whether the set is built on an array, a tree or a hash table is hidden inside the implementation.

The choice of implementation decides how fast those operations run. Searching an unsorted array checks every element, a balanced binary search tree halves the remaining data at each step, and a hash table usually finds an item in a single step. Choosing the right ADT and implementation for a situation is one of the main design decisions in any program that handles a lot of data.

How the ideas connect

The topic has one subtopic, B4.1, Fundamentals of ADTs, which starts with the idea of an ADT and then studies four structures. The stack and queue of subtopic B2.2, Data structures, are already ADTs; B4.1 adds structures that grow and shrink by linking nodes together instead of shifting elements in a block of memory.

A linked list stores each item in a node that holds a reference to the next node, in singly, doubly and circular forms, and is evaluated against an array. A binary search tree (BST) keeps smaller values to the left and larger to the right, so a search halves the data at each step while the tree stays balanced. A set holds each value at most once and supports union, intersection, difference and subset tests. A hash table uses a hash function to turn a key into a position, which is how Java's HashMap and HashSet and Python's dict and set work.

The subtopic and its statements

Because B4 has a single subtopic, the table lists its six statements, all HL only.

Linked lists and sets are written in code in both languages. Binary search trees are explained and sketched; their traversals use the branching recursion of subtopic B2.4.

Links to other topics

The topic draws on most of theme B. Nodes are objects joined by references, so it uses the classes of topic B3; operations are compared with the Big O notation of subtopic B2.4; and BST traversals use recursion (HL). Set operations mirror the Boolean logic of subtopic A1.2: an item is in the union of two sets if it is in the first OR the second.

The structures also appear outside programming. Database indexes in subtopic A3.3 are commonly built as B-trees, a relative of the BST, and the round robin scheduling of subtopic A1.3 cycles through processes in the way a circular linked list cycles through its nodes. The hash function of a hash table aims at speed and an even spread of keys, unlike the cryptographic hash functions of subtopic A2.4, which aim to be impossible to reverse.