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.

Start with the operations

Before selecting a structure, list what the program must do most often. Arrays provide direct indexed access; linked lists make local insertion simple once a node is known; hash tables target expected constant-time lookup; heaps expose one extreme value efficiently.

There is no universally best structure. A representation that makes reads fast may make ordered iteration or updates expensive. State the workload first: search by key, append in order, repeatedly remove the minimum, or explore relationships.

Access by numeric position: array
Membership or key lookup: hash table
Last-in-first-out work: stack
Repeated minimum or maximum: heap
Relationships and paths: graph

Abstract data type versus representation

A stack describes behavior—push, pop, and peek—not its physical storage. It may be implemented with a dynamic array or a linked list. Likewise, a queue can use a circular array, linked nodes, or two stacks.

This distinction keeps reasoning clean. First prove an algorithm using the operations promised by the interface. Then choose an implementation whose time, space, and locality fit the environment.

Interface says what operations mean
Implementation says how operations are achieved
The implementation must keep the promised behavior correct

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.

Code example

Store names by ID and look one up

students = {101: "Ana", 205: "Ben", 309: "Chen"}
student_id = 205
print(students[student_id])

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, string> students = {
        {101, "Ana"}, {205, "Ben"}, {309, "Chen"}
    };
    int studentId = 205;
    cout << students[studentId] << '\n';
}

import java.util.Map;

class Main {
    public static void main(String[] args) {
        Map<Integer, String> students = Map.of(
            101, "Ana", 205, "Ben", 309, "Chen"
        );
        int studentId = 205;
        System.out.println(students.get(studentId));
    }
}

Input[(101, Ana), (205, Ben), (309, Chen)], search ID 205

OutputBen

Example

Run the example step by step

Output

Time, space, and locality

Big-O describes growth, but constants and memory layout still matter. Contiguous arrays benefit from CPU caches and compact storage. Pointer-heavy structures pay for node objects and may jump around memory even when their asymptotic bound looks attractive.

Amortized analysis also matters. Appending to a dynamic array is usually O(1) amortized because occasional O(n) resizing is spread across many cheap appends.

Worst case protects latency-sensitive paths
Expected bounds depend on assumptions such as good hashing
Amortized bounds average a sequence of operations, not random inputs

A repeatable selection method

Write down data size, operation frequency, ordering needs, duplicate policy, and memory constraints. Compare two plausible structures operation by operation. Finally, test the choice with adversarial inputs rather than only a friendly example.

The correct choice often becomes obvious once the dominant operation is named. If it does not, keep the representation behind an interface so measurement can guide a later change.

Define the dominant operation
Identify the invariant
Estimate asymptotic and practical cost
Test boundary and adversarial cases