Data Structures course

1. 1.Arrays and Lists

   An array stores a sequence of values in consecutive memory, so any element can be reached instantly by its index. Most languages count from 0, so an array of length $n$ has indices $0$ to $n - 1$. Reading or writing `a[i]` takes constant time, which is the array's great strength.

   • Index access: $O(1)$; search an unsorted array: $O(n)$.
   • Insert or delete in the middle: $O(n)$ because of shifting.
   • Appending to a dynamic array is $O(1)$ amortised.
   Quick check: What is the last valid index of an array of length 12?

   $11$

   Includes a worked example, 3 common mistakes and 3 practice questions with answers. Study arrays and lists

2. 2.Stacks and Queues

   A stack is a last-in, first-out (LIFO) collection: you push items onto the top and pop them off the top, like a pile of plates. A queue is first-in, first-out (FIFO): you enqueue at the back and dequeue from the front, like a checkout line. Both restrict access on purpose, which makes them simple, fast and hard to misuse.

   • Stack: push, pop, peek at the top, all $O(1)$.
   • Queue: enqueue at the back, dequeue at the front, all $O(1)$ with a linked list or circular buffer.
   • Popping an empty stack is an underflow error; check first.
   Quick check: Push 1, 2, 3 onto a stack, then pop twice. What remains on top?

   $1$

   Includes a worked example, 3 common mistakes and 3 practice questions with answers. Study stacks and queues

3. 3.Hash Tables

   A hash table stores key-value pairs so that looking up a key takes, on average, constant time. A hash function turns each key into an index in an underlying array. Python dictionaries, JavaScript objects and Maps, and Java HashMaps are all hash tables.

   • Average insert, lookup and delete: $O(1)$; worst case $O(n)$ if everything collides.
   • Load factor $\alpha = \frac{n}{m}$ for $n$ entries in $m$ slots.
   • Good hash functions spread keys uniformly and are fast to compute.
   Quick check: Slot for key 38 with $h(k) = k \bmod 10$.

   $8$

   Includes a worked example, 3 common mistakes and 3 practice questions with answers. Study hash tables

These topics belong to the course outline. Full explainers for them have not been written yet, so they are summarised here rather than given pages of their own.

Trees

Binary trees, binary search trees and heaps.

• Data Structures overview
• All subjects