Bytebook Compiler

Searching & Sorting

Data Structures Cheat Sheet

Every structure and algorithm from CSE 102 on one page: operation costs, when to use what, key formulas and the programs to practise.

4 min read4-question quiz

Operation costs

Structure Access Search Insert Delete Notes
Array O(1) O(n) O(n) O(n) O(1) at the end
Sorted array O(1) O(log n) O(n) O(n) binary search
Singly linked list O(n) O(n) O(1)* O(1)* *at head or after a known node
Doubly linked list O(n) O(n) O(1)* O(1)* delete with only the node pointer
Stack top only O(n) O(1) push O(1) pop LIFO
Queue front only O(n) O(1) enqueue O(1) dequeue FIFO
BST (balanced) — O(log n) O(log n) O(log n) O(n) if skewed
AVL tree — O(log n) O(log n) O(log n) guaranteed
Binary heap O(1) max/min O(n) O(log n) O(log n) extract priority queue
Hash table — O(1) avg O(1) avg O(1) avg O(n) worst
Graph (adj. list) — O(V + E) traversal O(1) edge O(deg) edge sparse graphs

Choosing a structure

You need to… Use
access by position, rarely insert array
insert/delete often in the middle linked list
undo, backtrack, match brackets, evaluate expressions stack
process in arrival order, BFS, scheduling queue
always get the smallest/largest next heap / priority queue
keep keys sorted with fast search balanced BST (AVL)
look up by key, fastest on average hash table
model connections or networks graph

Key formulas

Fact Formula
Max nodes at level l of a binary tree 2ˡ
Max nodes in a binary tree of height h 2ʰ⁺¹ − 1
Min height for n nodes ⌈log₂(n + 1)⌉ − 1
Heap/complete tree in an array (0-based) parent (i−1)/2, children 2i+1, 2i+2
AVL balance factor height(left) − height(right) ∈ {−1, 0, 1}
Edges in a tree with n vertices n − 1
Sum of degrees (undirected) 2 × edges
Max edges, simple undirected graph n(n − 1) / 2
Load factor of a hash table α = n / m
Circular queue next index (i + 1) % capacity

Sorting summary

Algorithm Average Worst Stable In place
Bubble / Insertion O(n²) O(n²) yes yes
Selection O(n²) O(n²) no yes
Merge O(n log n) O(n log n) yes no
Quick O(n log n) O(n²) no yes
Heap O(n log n) O(n log n) no yes
Counting O(n + k) O(n + k) yes no

Programs to practise

  1. Insert/delete at a position in an array.
  2. Singly linked list: insert at head, tail and position; delete by value; reverse; find middle; detect a cycle.
  3. Doubly and circular linked list insert and delete.
  4. Stack using an array and a linked list; balanced brackets; infix → postfix; postfix evaluation.
  5. Circular queue; queue using a linked list.
  6. Binary tree traversals (recursive), height, count leaves.
  7. BST insert, search, delete; check if a tree is a BST.
  8. Heap insert and extract; heap sort.
  9. BFS and DFS on an adjacency matrix and an adjacency list.
  10. Hash table with chaining and with linear probing.
  11. Linear and binary search; all six sorts.

Theory questions to prepare

  1. Classify data structures with examples; define ADT.
  2. Array vs linked list.
  3. Stack and queue applications; why a circular queue?
  4. Convert and evaluate an expression (show the stack table).
  5. Tree terminology; types of binary trees; traversals of a given tree.
  6. Construct a BST / AVL tree from a key sequence; show rotations.
  7. Heapify an array; trace heap sort.
  8. Adjacency matrix vs list; BFS vs DFS with a traced example.
  9. Hash functions and collision resolution; load factor.
  10. Compare sorting algorithms (table above); define stable and in-place.

Final check: mixed revision

4 questions · pick an answer to check it instantly

  1. 1

    Which structure would you use to check for balanced parentheses?

  2. 2

    What is the postorder traversal of a BST built by inserting 8, 3, 10, 1, 6?

  3. 3

    Which needs the array to be sorted?

  4. 4

    A max-heap's array is [50, 40, 45, 10, 20]. After extracting the max, what is the new root?

Esc
↑↓ move↵ open