Data structures

Map of content for data structures and algorithms — how to organize data so that operations on it are efficient. The path: foundations → linear structures → trees → hash tables → sorting/searching → graphs.

Foundations

The C and analysis prerequisites.

• Data structure — what one is, how they’re classified.
• Pointer arithmetic — C pointers, the building block for linked structures.
• C struct — composite types in C.
• Dynamic memory allocation — malloc, free, the heap.
• Recursion — the natural way to operate on tree-like structures.
• Algorithm analysis — counting basic operations.
• Big O notation — asymptotic complexity.

Linear data structures

One element at a time, ordered.

• Linked list — singly linked.
• Doubly linked list — with backward pointers.
• Circular linked list — last node wraps to the first; useful for round-robin and cyclic sequences.
• Dynamic array — array that grows on demand (vector, ArrayList).
• Stack (computing) — LIFO; also the processor stack.
• Queue — FIFO.
• Deque — both ends accessible.
• Priority queue — extracts highest-priority element.

Trees

Hierarchical structures.

• Tree (data structure) — definitions, terminology, types.
• Binary tree — at most two children per node.
• Binary tree traversal — pre-order, in-order, post-order, level-order.
• Binary search tree — ordered binary tree, $O(\log n)$ search.
• AVL tree — self-balancing BST.
• Red-black tree — alternative self-balancing.
• Heap (data structure) — complete binary tree with heap property.

Hash tables

Constant-time access by key.

• Hash table — overview, collision handling.

Sorting

Ordering a sequence.

• Selection sort — $O(n^2)$, simplest baseline.
• Bubble sort — $O(n^2)$, stable, easy to understand.
• Insertion sort — $O(n^2)$ worst case but $O(n)$ on nearly-sorted; widely used as a subroutine.
• Heap sort — $O(n\log n)$ via the heap structure.
• Quick sort — $O(n\log n)$ average, dominant in practice.
• Merge sort — $O(n\log n)$ guaranteed, stable.
• Shell sort — gap-based, breaking the $O(n^2)$ barrier.
• Bucket sort — distribution-based for known ranges.
• Counting sort — linear-time for small integer keys.
• Radix sort — digit-by-digit, $O(n)$ for fixed-width keys.

Searching

Finding an element.

• Binary search — $O(\log n)$ in sorted arrays.

Graphs

Vertices and edges; the most general structure.

• Graph — definitions, directed vs undirected, weighted.
• Adjacency matrix — dense graph representation.
• Adjacency list — sparse graph representation.

Graph traversal

Visiting every reachable vertex.

• Breadth-first search (BFS) — level by level using a queue.
• Depth-first search (DFS) — depth-first using a stack or recursion.

Shortest paths and spanning trees

Optimization on weighted graphs.

• Dijkstra’s algorithm — single-source shortest paths.
• Spanning tree — minimum spanning tree concept.
• Prim’s algorithm — greedy MST construction.

---

Connects to Computer architecture (the runtime stack, virtual memory) and to Differential equations only loosely (graph algorithms appear in network analysis, but the math is different).