Data Structures and Algorithms

This is Unit Three of Computer Science: data structures and algorithms. The unit runs long, so it comes in two parts, and this is the first. The unit's organising distinction arrives early and does a great deal of work. An abstract data type is a set of promises — what operations you can perform. A data structure is one way of keeping those promises. One error entry protects that distinction, and it is worth previewing. Treating a type as identical to one particular structure hides every alternative — the same set of operations can be built several ways, and the ways differ in what they cost. That is the shape of this part. Five families of promise, and then implementations compared against each other — where the comparison is never which is better, but which costs are acceptable for the use you have. By the end you will be able to do five things. One: tell an abstract type from a structure, and say why it matters. Two: name five abstract types by what each promises. Three: say what each of two list implementations buys. Four: say why arrival order changes a search tree's performance. Five: say what a heap maintains, and what that is good for.

Five entries, and the fourth and fifth are the load-bearing pair. Separating what a thing promises from how it delivers is the move that makes the rest of the unit comparative rather than merely descriptive.

What a type fixes.

CS 0091 The Data Type

A data type fixes two things — the values that are possible, and the operations available on all of them. Both halves are part of the definition.

Idea, and implementation.

CS 0092 Algorithm and Program

An algorithm is the idea — precise instructions on data. A program is its implementation, written in a language a machine runs. The distinction repeats one level up in a moment.

A structure.

CS 0094 The Data Structure

A complex data type with two equally important parts: a particular way of organising a collection, and the operations that organisation supports.

And the family above it.

CS 0095 The Abstract Data Type

An abstract type is the family of all structures sharing the same functionality while differing in how they represent it. It names what is promised rather than how the promise is kept.

The confusion to avoid.

CS 0096 "The Type Is the Structure"

Treating an abstract type as one specific structure conceals every other way of providing the same operations — and the alternatives differ in cost, which is the whole point of separating them.

Five entries, each naming a family by the operations it promises. Read them as contracts rather than as things — what you can ask of one, and what it guarantees about order and uniqueness.

The first.

CS 0097 The List

An ordered sequence allowing adding, retrieving and removing at a given position. Order is part of the promise.

The second.

CS 0098 The Set

An unordered collection of unique elements — less functionality than the first, and that reduction is what it is for.

The third.

CS 0099 The Map

Unordered associations between keys and values, with each key appearing exactly once. Looking something up by name rather than by position.

The fourth.

CS 0100 The Priority Queue

Every element carries a priority, and retrieval and removal always serve the highest. What comes out is decided by the elements rather than by arrival order.

And the fifth.

CS 0101 The Graph

Binary relations among entities — the entities as vertices and each relation as an edge between two of them. The most general of the five.

Two entries making the unit's distinction concrete. Both deliver the same promises from Topic Two, and they are almost exactly opposite in what they are good at — which is the clearest demonstration of why type and structure are separated.

The first.

CS 0103 The Array List

Elements stored adjacently, which grants access to any position directly. Reaching the thousandth element costs the same as reaching the first.

The second.

CS 0104 The Linked List

Each element holds a link to the following one, so access is sequential — reaching the thousandth means walking a thousand links. Insertion, though, costs almost nothing.

Four entries, and the interesting one is the third. A search tree's performance depends not on the data it holds but on the order the data arrived in — which is an unusual property and the reason the fourth entry exists.

The structure.

CS 0106 The Tree

Nodes descending from a single root through parent-child links to childless leaves. A hierarchy rather than a sequence.

Made searchable.

CS 0107 The Binary Search Tree

At most two children per node, and elements ordered smaller-to-the-left. Those two properties together are what make searching it fast.

The problem.

CS 0108 The Balance Problem

The order elements arrive in shapes the tree. Arriving already sorted stacks it into a single chain — which is the worst possible shape, produced by the most orderly possible input.

The fix.

CS 0109 The AVL Tree

A search tree with one further requirement — that the two sides of every node stay close in height. That single condition prevents the collapse.

One entry closing Part One with a different ordering principle. A search tree keeps everything sorted; this keeps only one guarantee — and that narrower promise is exactly what makes it fast for a particular job.

The structure.

CS 0110 The Binary Heap

A tree where every node's priority is at least its children's. Nothing else is sorted — but the highest-priority element is always at the top, which is what the priority queue from Topic Two needed.

Five things you can now do — and Part Two is about what gets done with these. You can tell an abstract type from a structure — promises against ways of keeping them — and say why merging the two hides every alternative. You can name five abstract types by what each promises: an ordered sequence, a unique collection, keyed associations, retrieval by priority, and relations between entities. You can say what each list implementation buys — direct access to any position, against insertion that costs almost nothing. You can say why arrival order changes a search tree, and that already-sorted input produces the worst possible shape. And you can say what a heap maintains — one guarantee about the top rather than full ordering — and what that makes it good for.