Computer Science › Foundations of Computer Science
The distinction between an Abstract Data Type — what operations a structure supports — and a data structure — how it's actually built in memory to support them.
A tree where every node has at most two children — how the graph-theoretic tree from discrete math becomes a concrete node-and-pointer data structure.
Four standard orders for visiting every node in a binary tree exactly once — three defined recursively, one defined by processing level by level with a queue.
A binary tree with an ordering invariant — everything in a node's left subtree is smaller, everything in its right subtree is larger — that turns search into following one path from the root.
A binary search tree's operations are O(log n) on average but degrade to O(n) on a lopsided tree — the exact problem that motivates the self-balancing trees covered later, in Data Structures II.
Mapping a key to an array index via a hash function, aiming for near-constant-time lookup — and the properties (determinism, uniformity) a good hash function needs.
Resolving a collision by probing for the next open slot in the array itself, rather than chaining elsewhere — and the clustering problems that come with it.
Resolving two keys that hash to the same index by storing a small list at each array slot — simple to implement, degrading gracefully as collisions accumulate.
The ratio of stored elements to table capacity, and why a hash table must resize (rehash) once that ratio grows too large to keep operations close to O(1).
A sequence built from nodes scattered anywhere in memory, each pointing to the next — trading array's O(1) random access for O(1) insertion at a known position.
A linked list whose nodes also point backward, enabling O(1) removal of a known node and O(1) traversal in either direction, at the cost of an extra pointer per node.
A fixed-size, contiguous block of memory that supports O(1) access to any element by index — and why that contiguity is exactly what makes random access fast.
An array that grows by doubling its capacity when full — and why that doubling strategy makes appending an element O(1) on average (amortized), even though any single append can be O(n).
Neither structure dominates the other — a side-by-side comparison of access, insertion, deletion, and memory locality to decide which sequence fits a given problem.
A First-In-First-Out structure exposing enqueue and dequeue — and why a naive array implementation needs a circular buffer to keep both operations O(1).
A double-ended queue supporting O(1) insertion and removal at both ends — a strict generalization that subsumes both the stack and the queue.
A Last-In-First-Out structure exposing only push and pop — and how the same ADT can be implemented equally well atop a resizing array or a linked list.
A uniform way to walk through any collection's elements one at a time without exposing how that collection is actually stored underneath.
Part of the Computer Science curriculum.
The distinction between an Abstract Data Type — what operations a structure supports — and a data structure — how it's actually built in memory to support them.
A tree where every node has at most two children — how the graph-theoretic tree from discrete math becomes a concrete node-and-pointer data structure.
Four standard orders for visiting every node in a binary tree exactly once — three defined recursively, one defined by processing level by level with a queue.
A binary tree with an ordering invariant — everything in a node's left subtree is smaller, everything in its right subtree is larger — that turns search into following one path from the root.
A binary search tree's operations are O(log n) on average but degrade to O(n) on a lopsided tree — the exact problem that motivates the self-balancing trees covered later, in Data Structures II.
Mapping a key to an array index via a hash function, aiming for near-constant-time lookup — and the properties (determinism, uniformity) a good hash function needs.
Resolving a collision by probing for the next open slot in the array itself, rather than chaining elsewhere — and the clustering problems that come with it.
Resolving two keys that hash to the same index by storing a small list at each array slot — simple to implement, degrading gracefully as collisions accumulate.
The ratio of stored elements to table capacity, and why a hash table must resize (rehash) once that ratio grows too large to keep operations close to O(1).
A sequence built from nodes scattered anywhere in memory, each pointing to the next — trading array's O(1) random access for O(1) insertion at a known position.
A linked list whose nodes also point backward, enabling O(1) removal of a known node and O(1) traversal in either direction, at the cost of an extra pointer per node.
A fixed-size, contiguous block of memory that supports O(1) access to any element by index — and why that contiguity is exactly what makes random access fast.
An array that grows by doubling its capacity when full — and why that doubling strategy makes appending an element O(1) on average (amortized), even though any single append can be O(n).
Neither structure dominates the other — a side-by-side comparison of access, insertion, deletion, and memory locality to decide which sequence fits a given problem.
A First-In-First-Out structure exposing enqueue and dequeue — and why a naive array implementation needs a circular buffer to keep both operations O(1).
A double-ended queue supporting O(1) insertion and removal at both ends — a strict generalization that subsumes both the stack and the queue.
A Last-In-First-Out structure exposing only push and pop — and how the same ADT can be implemented equally well atop a resizing array or a linked list.
A uniform way to walk through any collection's elements one at a time without exposing how that collection is actually stored underneath.