Data Structures
How data is organized
Linked List
Nodes chained by pointers: O(1) insertion at the head, sequential traversal to search or delete.
Time O(n) search · Space O(n)
Stack
LIFO container: push and pop happen at the same end, so the last element in is the first one out.
Time O(1) push/pop · Space O(n)
Queue
FIFO container implemented as a circular buffer: enqueue at the rear, dequeue from the front.
Time O(1) enqueue/dequeue · Space O(n)
Hash Table
Maps keys to buckets with a hash function; collisions are chained as linked lists inside each bucket.
Time O(1) average · Space O(n)
Union-Find (Disjoint Set)
Forest of sets: find walks to a root and flattens the path behind it, union hangs the lower-rank root under the higher one.
Time O(α(n)) · Space O(n)