Data Structures Quick Revision: Arrays, Stacks, Queues, Linked Lists, Trees and Graphs

These notes summarise the data structures topics that appear most often in Computer Science exams, with complexities, formulas and solved examples. Use them for last-week revision.

Arrays#

• Stored in contiguous memory; access by index in O(1).
• Insertion/deletion in the middle needs shifting: O(n).

Address formula (1-D): Address of A[i] = Base + (i − LB) × size

2-D array, row-major: Address of A[i][j] = Base + [(i − LR) × N + (j − LC)] × size, where N is the number of columns.

Example: int A[10][20], base 1000, 4 bytes, row-major, lower bounds 0. A[3][5] = 1000 + (3×20 + 5)×4 = 1260.

Stack (LIFO)#

Operations: push, pop, peek, all O(1). Overflow when pushing onto a full stack; underflow when popping an empty one.

Uses: function calls (recursion), undo, expression evaluation, balanced-parentheses checking.

Infix to postfix#

Rules: operands go straight to output; operators wait on the stack and pop when an operator of higher or equal precedence is on top (for left-associative operators).

Example: A + B × C − D → A B C × + D −

Evaluate postfix 6 2 3 + − 3 8 2 / + ×: push numbers, apply each operator to the top two: result 7.

Queue (FIFO)#

• enqueue at rear, dequeue from front: O(1).
• Circular queue reuses space: rear = (rear + 1) mod size.
• Deque: insert/delete at both ends.
• Priority queue: highest priority leaves first (usually built with a heap).

Linked lists#

• Insertion at head: O(1). Search: O(n). No random access.
• Advantage over arrays: dynamic size, cheap insert/delete once the position is known.

Trees#

Key terms: root, leaf, degree, height (edges on the longest root-to-leaf path), level.

Binary tree facts:

• Max nodes at level l = 2^l (root at level 0).
• Max nodes in a tree of height h = 2^(h+1) − 1.
• In any binary tree, leaves = nodes with two children + 1.

Traversals#

For the tree with root A, left child B (children D, E) and right child C:

Binary search tree (BST): left subtree < root < right subtree. Inorder traversal of a BST gives sorted order. Search/insert: O(log n) average, O(n) worst (skewed tree).

AVL tree: a self-balancing BST where each node's balance factor (height of left − height of right) is −1, 0 or +1. Search stays O(log n).

Heap: complete binary tree; in a max-heap every parent ≥ its children. Insert and delete: O(log n). Building a heap from n items: O(n).

Graphs#

• Representation: adjacency matrix (O(V²) space) or adjacency list (O(V + E)).
• BFS uses a queue (finds shortest path in unweighted graphs); DFS uses a stack or recursion.
• Both run in O(V + E) with an adjacency list.
• Sum of degrees of all vertices = 2 × number of edges.
• A tree with n vertices has n − 1 edges.

Hashing#

A hash function maps keys to table slots. Collisions are handled by:

• Chaining: each slot holds a list.
• Open addressing: linear probing, quadratic probing or double hashing.

Average search: O(1); worst: O(n).

Complexity cheat sheet#

*once the position is known

Quick practice#

1. Convert (A + B) × (C − D) to postfix.
2. A binary tree has 20 leaves. How many nodes have exactly two children?
3. Which traversal of a BST prints keys in ascending order?

Answers: 1) A B + C D − ×. 2) 19. 3) Inorder.