Lesson 3 · Foundations

Introduction to Data Structures

A data structure is a contract about how information is arranged, reached, updated, and removed. Choosing one is not a vocabulary exercise: it determines which operations are cheap and which become bottlenecks.

What a Data Structure Actually Is

A data structure is a way of organising values in memory together with the operations that organisation makes efficient. The second half of that sentence is the part people skip, and it is the part that matters: a structure is not chosen for how it stores data but for which operations it makes cheap.

Every structure is a set of trades, never a strict improvement. An array makes access by position O(1) and pays for it with O(n) insertion. A hash table makes lookup by key O(1) and gives up ordering entirely. A balanced tree keeps everything sorted and accepts O(log n) for the privilege. There is no structure that is fast at everything, and expecting one is the most common beginner error.

So the question is never 'which data structure is best'. It is which operations does this program perform most often, and which structure makes those cheap — accepting that whatever it makes expensive is something you rarely do.

Structures are commonly split into linear, where elements sit in a single sequence with each having one predecessor and one successor, and non-linear, where an element may connect to many others. Arrays, linked lists, stacks, and queues are linear; trees, graphs, and hash tables are not. The distinction is useful mainly because it predicts how you will traverse them: linear structures with a loop, non-linear ones with recursion or an explicit worklist.

A layout plus the operations it makes efficient
Every structure trades one operation's speed for another's
Ask what the program does most, not what is generally best
Linear structures iterate; non-linear ones recurse

The Contract and the Implementation

Two different things get called by the same names, and separating them clears up most confusion in this subject.

An abstract data type is a contract: the operations available and what they promise, with nothing said about mechanism. 'A stack supports push and pop, and pop returns the most recently pushed item' is a complete ADT definition. A data structure is a concrete arrangement of memory that implements such a contract.

One contract admits many implementations, and the choice among them changes the performance without changing the meaning. A stack can be backed by an array or a linked list — same guarantees, different memory behaviour. A queue can be a circular array or a pair of pointers into a linked list. A map can be a hash table, giving O(1) average lookup and no ordering, or a balanced tree, giving O(log n) lookup with sorted iteration.

This is why library names differ from textbook names. Python's list is a dynamic array, not a linked list. Java's HashMap and TreeMap implement the same Map interface with completely different structures and guarantees. Reading a language's documentation for the representation behind a type, rather than assuming it from the name, is a habit worth forming early — it is the difference between code that is accidentally O(n²) and code that is not.

ADT = the operations and their promises
Data structure = the memory arrangement implementing them
One contract, several implementations with different costs
Check what a library type actually is — names mislead

The Structures Worth Knowing First

A small set covers the overwhelming majority of real work, and each exists because it makes a specific operation cheap.

Arrays and dynamic arrays store elements contiguously, giving O(1) access by index and excellent cache behaviour. They are the correct default for a sequence, and the structure to reach for unless something specific argues otherwise.

Linked lists store elements in scattered nodes joined by pointers, trading O(n) access for O(1) insertion and deletion at a position you already hold. Stacks and queues are restrictions rather than new layouts — a stack enforces last-in-first-out, a queue first-in-first-out — and their value lies in what they forbid.

Hash tables convert a key into a bucket index directly, giving O(1) average lookup, insertion, and deletion. They are the reason 'have I seen this before' is a cheap question, and the single highest-leverage structure in practical programming. The cost is unordered iteration and an O(n) worst case when hashing degrades.

Trees impose hierarchy. A balanced binary search tree keeps keys sorted with O(log n) operations and, unlike a hash table, supports range and ordered queries. Heaps are trees specialised so the minimum or maximum is always available in O(1), which is what makes priority queues work. Graphs drop the hierarchy restriction entirely and model arbitrary relationships — road networks, dependencies, social connections — with the traversal doing the work rather than the layout.

What each structure makes cheap, and what it gives up
Structure	Cheap	Costly	Reach for it when
Dynamic array	Index access, iteration	Middle insertion	You need an ordered sequence — the default
Linked list	Insert/delete at a held node	Access by index	Edits dominate and you hold the nodes
Stack / queue	Push and pop at the ends	Anything in the middle	Order of processing is the requirement
Hash table	Lookup, insert, delete by key	Ordered iteration	You ask 'have I seen this?'
Balanced tree	Ordered and range queries	Constant factors	You need sorted order maintained
Heap	Finding the extreme	Searching for anything else	You repeatedly need the min or max
Graph	Modelling arbitrary relations	Nothing is O(1)	Entities connect many-to-many

Dynamic array is the default sequence
Hash table answers membership and lookup in O(1) average
Balanced trees keep order; hash tables discard it
Heaps give the extreme element, not fast search

Key reference

Terms, operations, and practical uses

Core vocabulary

ElementOne stored value or record.
KeyThe identifier used to find a record without relying on its numeric position.
InvariantA condition the representation must preserve after every operation.
Abstract data typeThe promised behavior—such as stack or queue—independent of the storage used underneath.

Operation checklist

AccessRead an item by index, key, or reference.
UpdateReplace data while preserving the structure's rules.
Insert and removeMeasure both the local change and any shifting, rebalancing, or rehashing it causes.
TraverseVisit all reachable items in a defined order.

Selection questions

OrderingMust records keep insertion order, sorted order, or no order at all?
Lookup frequencyRepeated key searches often justify a hash table or ordered index.
Memory layoutContiguous storage improves locality; node-based storage permits local rewiring.

Implementation

One lookup, three structures, three costs

values = [10, 20, 30, 40, 50]
target = 40

# 1. Unsorted array: check every element. O(n)
def linear_search(data, x):
    for i, v in enumerate(data):
        comparisons = i + 1
        if v == x:
            return i, comparisons
    return -1, len(data)

# 2. Sorted array: discard half each step. O(log n)
def binary_search(data, x):
    lo, hi, comparisons = 0, len(data) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        comparisons += 1
        if data[mid] == x:
            return mid, comparisons
        if data[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

# 3. Hash map: jump straight to the slot. O(1) average
lookup = {v: i for i, v in enumerate(values)}

_, a = linear_search(values, target)
_, b = binary_search(values, target)
c = 1 if target in lookup else 0

print(f"Unsorted array {a} comparisons · sorted array {b} · hash map {c}")

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// 1. Unsorted array: check every element. O(n)
int linearSearch(const vector<int>& data, int x, int& comparisons) {
    for (int i = 0; i < (int)data.size(); i++) {
        comparisons = i + 1;
        if (data[i] == x) return i;
    }
    comparisons = (int)data.size();
    return -1;
}
// 2. Sorted array: discard half each step. O(log n)
int binarySearch(const vector<int>& data, int x, int& comparisons) {
    int lo = 0, hi = (int)data.size() - 1;
    comparisons = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        comparisons++;
        if (data[mid] == x) return mid;
        if (data[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
int main() {
    vector<int> values = {10, 20, 30, 40, 50};
    int target = 40, a = 0, b = 0;
    // 3. Hash map: jump straight to the slot. O(1) average
    unordered_map<int, int> lookup;
    for (int i = 0; i < (int)values.size(); i++) lookup[values[i]] = i;
    linearSearch(values, target, a);
    binarySearch(values, target, b);
    int c = lookup.count(target) ? 1 : 0;
    cout << "Unsorted array " << a << " comparisons · sorted array " << b
    << " · hash map " << c << '\n';
}

import java.util.HashMap;
import java.util.Map;
class Main {
    static int comparisons = 0;
    // 1. Unsorted array: check every element. O(n)
    static int linearSearch(int[] data, int x) {
        for (int i = 0; i < data.length; i++) {
            comparisons = i + 1;
            if (data[i] == x) return i;
        }
        comparisons = data.length;
        return -1;
    }
    // 2. Sorted array: discard half each step. O(log n)
    static int binarySearch(int[] data, int x) {
        int lo = 0, hi = data.length - 1;
        comparisons = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            comparisons++;
            if (data[mid] == x) return mid;
            if (data[mid] < x) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] values = {10, 20, 30, 40, 50};
        int target = 40;
        // 3. Hash map: jump straight to the slot. O(1) average
        Map<Integer, Integer> lookup = new HashMap<>();
        for (int i = 0; i < values.length; i++) lookup.put(values[i], i);
        linearSearch(values, target);
        int a = comparisons;
        binarySearch(values, target);
        int b = comparisons;
        int c = lookup.containsKey(target) ? 1 : 0;
        System.out.println("Unsorted array " + a + " comparisons · sorted array " + b
        + " · hash map " + c);
    }
}

Watch it run

Step through it

Running on Values 10 20 30 40 50 — is 40 present?

Output

Read all 12 Steps

The task: does this list contain 40? One question, asked over and over. Which structure you store the values in decides how much work each answer costs. Watch the same lookup run three ways.
Unsorted array — check index 0 Nothing is known about the order, so the only safe method is to look at every element. 10 is not 40.
Unsorted array — check index 1 20 is not 40. No information gained except that one more slot is eliminated.
Unsorted array — check index 2 30 is not 40. Still scanning one at a time.
Unsorted array — found at index 3 40 matches. It took four comparisons. Had 40 been absent, all five would have run: this is O(n).
Sorted array — start in the middle Same values, but now sorted, and that unlocks a different method. Look at the middle element first: 30.
Sorted array — discard the left half 40 is greater than 30, and the array is sorted, so 40 cannot be to the left. Half the data is eliminated by a single comparison.
Sorted array — found The middle of what remains is 40. Two comparisons instead of four, and the gap widens fast: a million elements need twenty comparisons, not a million. This is O(log n).
Hash map — compute the bucket A third approach: store each value in a slot chosen by hashing it. To find 40, hash it once and go straight to that slot. No scanning at all.
Hash map — one lookup The value is either in that slot or absent. One step, regardless of how many values are stored: O(1) on average.
The trade-off No structure is best at everything. The hash map gave the fastest lookup but lost sort order and range queries. The sorted array kept order but must be re-sorted after inserts. The unsorted array is slowest to search and cheapest to append to.
How to choose List the operations your program actually performs, count how often each runs, then pick the structure whose cheap operation is your frequent one. That is the whole method — the rest is knowing what each structure costs.

Choosing One, Repeatably

A method that works under exam or interview pressure, in four steps.

First, list the operations and their frequencies. Write down what the program actually does — inserts, lookups by key, iteration in order, finding the maximum — and roughly how often. The operation performed in the inner loop is the one that decides; an operation performed once at startup is nearly free no matter what it costs.

Second, ask whether order matters. Do you need elements sorted, or to answer range queries, or to retrieve them in insertion order? If yes, hash tables are out and a tree or a sequence is indicated. If no, a hash table is usually the strongest candidate, since it is faster than a tree on the operations they share.

Third, ask where insertions and deletions happen. Only at the ends points to a stack, queue, or deque. In the middle, at positions you already hold, points to a linked structure. Rarely or never suggests a plain array, which will beat everything else on iteration.

Fourth, check the constraints the notation hides. Bounded memory may rule out per-node pointer overhead. Hard latency limits may rule out amortised guarantees, since a single resize can stall. Persistence to disk changes the calculus entirely — which is why databases use B-trees rather than binary search trees, optimising for block reads instead of comparisons.

When two structures tie on big-O, prefer the one with better cache locality. Modern hardware makes a contiguous scan several times faster than pointer-chasing over the same number of elements, which is why an array-backed structure frequently wins in practice against a theoretically equivalent linked one. Measure when it is close; the notation describes growth, not speed.

Rank operations by how often the inner loop performs them
Ordering requirements eliminate hash tables immediately
Where edits happen decides between array and linked structures
On a big-O tie, take the better cache behaviour