Data Structures Class Notes
Syllabus & goals
What you will learn: how to choose and implement core data structures for performance and clarit
Core topics: arrays, linked lists, stacks/queues, trees, heaps, hash tables, graphs.
Outcomes: Big-O fluency, trade-off reasoning, interview-style problem solving.
Prereqs: basic Python/Java/C++ syntax, recursion, and algebra.
Generated: 2025-08-30
Course: CS101-DS 09:00 Notes
| Instructor Page 1/12
Asymptotic Analysis
Big-O, Big-Theta, Big-Omega
Common classes: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).
Rules of thumb: focus on dominant term; ignore constants for growth-rate reasoning.
Space vs time: explicit about memory usage; cache friendliness matters in practice.
Amortized analysis: average per operation over a sequence (e.g., dynamic array expansion).
Generated: 2025-08-30 09:00 Page 1/12
Arrays
Contiguous memory, O(1) random access
Strengths: O(1) access by index, excellent cache locality.
Weaknesses: insertion/deletion in the middle is O(n); resizing costs.
Use cases: fixed-size collections, numeric computing, look-up tables.
Dynamic array growth factors: 1.5x 2x common; trade memory vs realloc frequency.
Generated: 2025-08-30 09:00 Page 1/12
Linked Lists
Singly, doubly, circular
Strengths: O(1) insert/delete at known node; no reallocation on growth.
Weaknesses: O(n) access by index; extra pointer memory; poor locality.
Variants: sentinel nodes, skip lists for faster search (probabilistic balancing).
Pitfalls: off-by-one in pointer rewiring; memory fragmentation.
Generated: 2025-08-30 09:00 Page 1/12
Stacks & Queues
LIFO vs FIFO
Stack ops: push/pop/top all O(1); used for recursion, undo, DFS.
Queue ops: enqueue/dequeue O(1) with circular buffer or linked list.
Deque: double-ended queue with O(1) push/pop on both ends.
Concurrency note: lock-free queues via CAS; beware ABA problem.
Generated: 2025-08-30 09:00 Page 1/12
Trees
Hierarchy & recursion
Traversal: preorder/inorder/postorder; BFS vs DFS.
Binary Search Trees (BST): average O(log n), worst O(n) if unbalanced.
n-ary trees & tries: prefix search; memory vs speed trade-offs.
Use cases: folders, DOM, indexes, routing.
Generated: 2025-08-30 09:00 Page 1/12
Balanced Trees
AVL, Red-Black, B-Trees
AVL: strict balance (height diff 1) faster lookups; more rotations on updates.
Red-Black: looser balance fewer rotations; widely used in libraries.
B/B+ Trees: optimized for disks; used in DB indexes and filesystems.
Implementation tips: isolate rotation logic; assert invariants.
Generated: 2025-08-30 09:00 Page 1/12
Heaps & Priority Queues
Binary heap; d-ary heap; heapify
Ops: insert O(log n), extract-min/max O(log n), peek O(1).
Binary heap in array: parent i (i-1)//2; children i 2i+1,2i+2.
Use cases: Dijkstra, event simulation, top-k, schedulers.
Heapify: O(n) bottom-up; avoid naïve O(n log n) inserts.
Generated: 2025-08-30 09:00 Page 1/12
Hash Tables
Hashing, collisions, resizing
Collision strategies: chaining vs open addressing (linear/quadratic probing, double hashing).
Good hash: uniform distribution, low clustering; consider SipHash for security.
Load factor: resize around 0.5 0.75; track cost of rehashing.
Pitfalls: poor equality/hash overrides; DoS via adversarial keys.
Generated: 2025-08-30 09:00 Page 1/12
Graphs
Adjacency list vs matrix
Directed vs undirected; weighted vs unweighted; sparse vs dense.
Traversals: BFS (shortest path in unweighted), DFS (topological sort, SCC).
Shortest paths: Dijkstra, Bellman-Ford, A*; MST: Kruskal/Prim.
Representation choice affects asymptotics and memory footprint.
Generated: 2025-08-30 09:00 Page 1/12
Sorting & Searching
Classic algorithms
Sorting: quicksort (avg n log n), mergesort (stable), heapsort (in-place).
Searching: binary search on sorted arrays; interpolation search for uniform keys.
Stability and in-place properties matter for downstream operations.
Practice: trace partitions/merges; reason about best/avg/worst cases.
Generated: 2025-08-30 09:00 Page 1/12
Practice Problems
Apply what you learned
Implement an LRU cache (hash map + doubly linked list).
kth largest element using a heap; k-way merge with a heap.
Implement a Trie with insert/search/prefix; add autocomplete.
Graph cloning with hash map; detect cycle in linked list (Floyd).
Generated: 2025-08-30 09:00 Page 1/12
