Computer Science · Theme B: Computational thinking and problem-solving

B4.1 — Fundamentals of ADTs

Computer Science · SL / HL · syllabus-mapped notes

1. CS_B4.1.1

   Properties and purpose of ADTs

   What an ADT is, and how it separates a data structure's behaviour from its implementation.

2. CS_B4.1.2

   Linked lists evaluated

   Singly, doubly and circular lists, their operations, and their trade-offs against arrays.

3. CS_B4.1.3

   Constructing linked lists

   Node classes and coded insertion, deletion, traversal and search for each list type.

4. CS_B4.1.4

   Binary search trees

   The BST ordering property, its node operations, and the three traversals.

5. CS_B4.1.5

   Sets as an ADT

   Unordered, unique elements with union, intersection, difference and membership code.

6. CS_B4.1.6

   Hash tables and set mechanics

   Hashing functions, collision resolution, load factor, and the language built-ins.