Algorithms and data structures

Data structures

• Arrays (static), records, files.
• Stack (LIFO): push and pop; used for subroutine calls, recursion and undo.
• Queue (FIFO): enqueue and dequeue; circular queues reuse space; used for printing and scheduling.
• Linked list: nodes with data and pointers; easy insertion and deletion.
• Binary tree: each node has up to two children; in a binary search tree, left < node < right. Traversals: pre-order, in-order (gives sorted output), post-order.
• Hash tables: a hashing function gives a storage address; collisions handled by overflow or open addressing.

Searching

• Linear search: O(n); works on unsorted data.
• Binary search: O(log n); requires sorted data.

Sorting

• Bubble sort and insertion sort: O(n²).
• Merge sort: O(n log n) – divide and conquer.
• Quick sort: average O(n log n).

Recursion

A function that calls itself, with a base case to stop. Each call uses the stack.

Big O notation

Describes how time or space grows with input size: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).

Check yourself

1. Which data structure works on a last-in, first-out basis?
2. How many comparisons at most does binary search need for 1 000 items?
3. Which tree traversal outputs a binary search tree in order?