A data structure is a way of organising data in memory so that specific operations can be performed efficiently. Arrays give O(1) random access. Hash tables give O(1) lookup by key. Linked lists give O(1) insertion at the head. The wrong structure for a workload makes programs slow; the right one makes them fast.
Every page in this section includes: a canonical definition, formal Big O complexity table, memory layout diagram, and implementations in at least C, Python, and Java. Sources from Cormen et al. CLRS and Knuth TAOCP.
Linear Structures
Data arranged in a sequence — each element has a position.
Contiguous memory. O(1) random access by index. The most cache-friendly structure. Foundation of all other structures.
Built · Session 08 · Access: O(1) · Insert: O(n)Nodes connected by pointers. O(1) insert/delete at head. O(n) random access. No memory reallocation needed for growth.
Built · Session 08 · Insert head: O(1) · Access: O(n)Last-in, first-out (LIFO). Push and pop at the top. The call stack, undo history, and expression evaluation all use this structure.
Built · Session 08 · Push/Pop: O(1)First-in, first-out (FIFO). Enqueue at back, dequeue from front. Task schedulers, BFS, and message queues all use this structure.
Built · Session 08 · Enqueue/Dequeue: O(1)Key-Value Structures
Key-value storage using hash functions. Average O(1) lookup, insert, delete. The structure behind Python dicts, JavaScript objects, and database indexes.
Built · Session 08 · Avg lookup: O(1) · Worst: O(n)Sorted tree structure with O(log n) average search, insert, delete. Self-balancing variants (AVL, Red-Black) guarantee O(log n) worst case.
Coming · Session 10Trees & Graphs
Hierarchical structure. Binary trees, N-ary trees, heaps. Used in file systems, compilers, and priority queues.
Coming · Session 10Specialised tree satisfying the heap property. O(log n) insert/extract-max. Foundation of heapsort and priority queues.
Coming · Session 10Vertices and edges. Directed, undirected, weighted. The structure behind social networks, maps, and dependency graphs.
Coming · Session 11Quick complexity reference
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | N/A | O(1) avg | O(1) avg | O(1) avg | O(n) |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
* Insert/delete at known node (head/tail). O(n) if finding the node first. All complexities are worst-case unless noted.