DATA STRUCTURES
The Complete Course Guide — All 43 Topics
Algorithms · Linear Structures · Stacks & Queues · Trees · Graphs · Searching · Sorting
Definitions, worked examples, pseudocode, complexity analysis, and exam questions for every topic.
Contents
● Part I — Foundations: [Link] to Algorithms [Link] Analysis [Link] Complexity [Link]
Complexity [Link] Notations
● Part II — Arrays: [Link] & Non-Linear DS [Link] [Link] Matrix
● Part III — Linked Lists: [Link] Linked List [Link] Linked List [Link] Linked List
● Part IV — Stacks: [Link] ADT [Link] (Array) [Link] (Linked List) [Link] [Link]→Postfix
[Link] Evaluation
● Part V — Queues: [Link] ADT [Link] (Array) [Link] (Linked List) [Link] Queue [Link]
● Part VI — Trees: [Link] [Link] [Link] Tree [Link] Tree Reps [Link]
[Link] Binary Trees [Link] Priority Queue [Link] Heap
● Part VII — Graphs: [Link] to Graphs [Link] [Link] [Link]
● Part VIII — Searching & Sorting: [Link] Search [Link] Search [Link] [Link] Sort
[Link] Sort [Link] Sort [Link] Sort [Link] Sort [Link]
● Final: Master Cheat-Sheet + Predicted Exam Questions
PART I — ALGORITHM FOUNDATIONS
1. Introduction to Algorithms
An algorithm is a finite set of well-defined, unambiguous, step-by-step instructions for solving a problem, which
can be translated into a computer program.
Characteristics: Input (0+ supplied values), Output (≥1 result), Definiteness (unambiguous steps), Finiteness
(must terminate), Effectiveness (each step is basic/executable), Feasibility, Language-independence.
Relationship: Algorithm (logic) + Data Structure (organisation of data) = Program (Niklaus Wirth). Algorithms are
commonly expressed as pseudocode or flowcharts before being coded.
2. Performance Analysis
Performance analysis measures how much time and memory an algorithm needs as input size n grows, so that
competing algorithms can be compared.
Priori analysis: Theoretical, done before running the program; machine-independent.
Posteriori analysis: Empirical, done by actually running the program and measuring; machine-dependent.
3. Space Complexity
Total memory an algorithm needs: S(n) = Fixed part (constants, simple variables, instruction space —
independent of n) + Variable part (arrays, recursion stack — depends on n).
Example: summing n numbers in an array needs n (array) + 3 (n, counter, total) → S(n)=n+3=O(n).
4. Time Complexity
The number of elementary operations (the 'step count') an algorithm performs, as a function of n.
Best case: minimum time (most favourable input).
Worst case: maximum time (least favourable input) — most commonly quoted, guaranteed upper bound.
Average case: expected time over all inputs of size n.
5. Asymptotic Notations
Notation Meaning Bound type
O(g(n)) f(n) grows no faster than g(n) Upper bound (worst case)
Ω(g(n)) f(n) grows at least as fast as g(n) Lower bound (best case)
Θ(g(n)) f(n) grows at exactly the rate of g(n) Tight bound (average/typical case)
Growth order (best→worst): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
PART II — ARRAYS & CLASSIFICATION OF DATA STRUCTURES
6. Linear vs Non-Linear Data Structures
Linear Data Structure Non-Linear Data Structure
Elements arranged sequentially, one after another Elements arranged hierarchically/in a network, not
sequentially
Each element has at most one predecessor and one An element can connect to multiple elements
successor
Single-level; traversed in one pass Multi-level; needs special traversal techniques
Examples: Array, Linked List, Stack, Queue Examples: Tree, Graph
7. Arrays
An array is a linear data structure that stores a fixed-size, contiguous collection of elements of the same data
type, each directly accessible via an index.
Key properties: Fixed size, contiguous memory, O(1) random access, O(n) insertion/deletion (must shift
elements).
Operation Time Complexity
Access (by index) O(1)
Search (unsorted) O(n)
Insertion (end) O(1) amortised
Insertion (middle/start) O(n)
Deletion (middle/start) O(n)
8. Sparse Matrix
A sparse matrix is a matrix in which most elements are zero. Storing every element (dense form) wastes
memory, so a sparse matrix is stored compactly — only non-zero elements are kept, each as a triple (row,
column, value).
Representation: The table usually starts with a header triple (total rows, total columns, number of non-zero
terms), followed by one triple per non-zero element.
Advantage: Saves memory/computation by skipping zero entries — important for large scientific matrices and
graph adjacency matrices.
PART III — LINKED LISTS
9. Singly Linked List
A linked list is a linear data structure where each element (node) holds data plus a pointer to the next node.
Unlike arrays, nodes need not be stored contiguously — they are linked purely by pointers, allowing dynamic
growth.
Node structure: [ data | next ] — the last node's next pointer is NULL.
Operation Array Singly Linked List
Access by index O(1) O(n) — must traverse from
head
Insertion at head O(n) (shift) O(1)
Insertion at end O(1) amortised O(n) unless a tail pointer is
kept
Memory Contiguous, fixed size Non-contiguous, dynamic size
+ pointer overhead
Advantage over arrays: dynamic size, efficient head insertion/deletion. Disadvantage: no random access, extra
memory per node, not cache-friendly.
10. Circular Linked List
A variation where the last node's 'next' pointer points back to the FIRST node instead of NULL, forming a circle.
Any node can be used as a starting point, and traversal can continue indefinitely round the list.
Use cases: Round-robin CPU scheduling, circular buffers, multiplayer turn-based games/applications.
11. Doubly Linked List
Each node holds data PLUS two pointers — one to the next node, one to the previous node — allowing traversal
in both directions.
Node structure: [ prev | data | next ]
Advantage: Bidirectional traversal; deleting a known node is easier since its predecessor is directly accessible
(no need to search for it).
Disadvantage: Extra memory for the second pointer; more complex insertion/deletion logic.
PART IV — STACKS
12. Stack ADT
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle — the last element added is
the first one removed. Think of a stack of plates: you add and remove from the top only.
Core operations: push (insert at top), pop (remove from top), peek/top (view top element without removing),
isEmpty, isFull.
Applications: Function call/recursion management, undo mechanisms in editors, expression evaluation
(infix/postfix), backtracking algorithms (maze solving), browser back button.
13. Stack Using Array
Implemented using a fixed-size array plus a variable 'top' that tracks the index of the topmost element (initially
top = -1).
push(x): if top == size-1 → Stack Overflow
else top = top+1; arr[top] = x
pop(): if top == -1 → Stack Underflow
else x = arr[top]; top = top-1; return x
Complexity: push/pop/peek are all O(1). Limitation: fixed maximum size, can overflow.
14. Stack Using Linked List
Implemented using a linked list where insertions/deletions happen only at the head (the 'top' of the stack),
avoiding the fixed-size limitation of the array version.
push(x): create new node with data=x; new_node.next = top; top = new_node
pop(): if top == NULL → Stack Underflow
else x = [Link]; top = [Link]; return x
Advantage over array stack: Grows dynamically — no fixed size limit / stack overflow (until memory runs out).
15. Expressions (Infix, Prefix, Postfix)
Notation Form Example (A+B)
Infix operator BETWEEN operands A+B
Prefix (Polish) operator BEFORE operands +AB
Postfix (Reverse Polish) operator AFTER operands AB+
Infix is natural for humans but requires operator precedence and brackets to disambiguate. Postfix/Prefix
remove the need for precedence rules and parentheses, making them easier for a computer/stack to evaluate
directly.
16. Infix to Postfix Conversion (Stack-based algorithm)
Uses an operator stack and precedence rules: scan the infix expression left to right —
● If the token is an operand, append it directly to the output.
● If it's '(', push it onto the stack.
● If it's ')', pop from the stack to output until '(' is found (discard both parentheses).
● If it's an operator, pop and output all stack operators with ≥ precedence, then push the current
operator.
● After scanning, pop all remaining operators from the stack to the output.
Example: A+B*C → Postfix: A B C * + (multiplication has higher precedence, so it is resolved first).
17. Postfix Evaluation
Postfix expressions are evaluated directly using a single operand stack, scanning left to right:
● If token is an operand, push it onto the stack.
● If token is an operator, pop the top two operands (second-popped is the left operand), apply the
operator, and push the result back.
● After scanning the whole expression, the single value left on the stack is the final result.
Example: Evaluate '5 3 4 * +' → push 5; push 3; push 4; see '*' → pop 4,3 → 3*4=12 → push 12; see '+' → pop
12,5 → 5+12=17 → push 17. Result = 17.
PART V — QUEUES
18. Queue ADT
A queue is a linear data structure that follows the FIFO (First In, First Out) principle — the first element added is
the first removed. Like a queue of people at a bank: whoever joins first is served first.
Core operations: enqueue (insert at rear), dequeue (remove from front), peek/front, isEmpty, isFull.
Applications: CPU/process scheduling, printer job scheduling, handling of requests in a web server, breadth-first
search, buffering (IO, streaming).
19. Queue Using Array
Implemented with a fixed-size array plus two pointers: 'front' (index of first element) and 'rear' (index of last
element).
Limitation: A simple (linear) array queue suffers from a false-full condition — once rear reaches the end of the
array, no more items can be enqueued even if slots at the front were freed by dequeues. This is solved by the
Circular Queue (Topic 21).
20. Queue Using Linked List
Implemented with a linked list plus two pointers: 'front' (head of list, for dequeue) and 'rear' (tail of list, for
enqueue). Enqueue adds a node after rear; dequeue removes the node at front.
Advantage: Grows dynamically, no false-full problem, no wasted array slots.
21. Circular Queue
A circular queue is a fixed-size array queue where the rear, after reaching the last index, wraps around to index 0
(if it is free), forming a logical circle. This solves the array queue's false-full problem, since freed front slots can
be reused.
Formula: rear = (rear + 1) % size; front = (front + 1) % size.
Use case: Traffic light control systems, CPU scheduling (round robin), streaming data buffers.
22. Double Ended Queue (Deque)
A deque (pronounced 'deck') allows insertion AND deletion from BOTH ends — front and rear — unlike a normal
queue which only inserts at rear and deletes at front.
Types: Input-restricted deque (insertion allowed at one end only, deletion at both); Output-restricted deque
(deletion allowed at one end only, insertion at both).
Use case: Can function as both a stack and a queue; used in sliding-window algorithms, undo/redo systems,
palindrome checking.
PART VI — TREES
23. Tree Terminology
Tree: A non-linear, hierarchical data structure consisting of nodes connected by edges, starting from a single
'root' node, with no cycles.
Root: The topmost node of the tree (has no parent).
Parent / Child: A node directly above/below another connected node.
Leaf (terminal node): A node with no children.
Siblings: Nodes sharing the same parent.
Degree of a node: The number of children it has.
Depth/Level of a node: The number of edges from the root to that node (root is level 0).
Height of a tree: The number of edges on the longest path from root to a leaf.
Subtree: Any node together with all its descendants, treated as its own tree.
24. Tree Representations
● List representation: nested lists/records showing parent-child relationships.
● Left child–right sibling representation: each node stores a pointer to its first child and a pointer to its
next sibling — allows a tree of any degree to be represented using only 2 pointers per node.
● Array representation: nodes stored in an array where a node at index i has children at computable
indices (commonly used for complete binary trees / heaps: left child = 2i+1, right child = 2i+2).
25. Binary Tree
A binary tree is a tree in which each node has AT MOST 2 children, conventionally called the left child and the
right child.
Types of binary trees: Full binary tree (every node has 0 or 2 children); Complete binary tree (all levels filled
except possibly the last, filled left to right); Perfect binary tree (all internal nodes have 2 children and all leaves
are at the same level); Skewed binary tree (each node has only one child, left-skewed or right-skewed); Balanced
binary tree (height difference between left and right subtrees is minimal, e.g. AVL tree).
Application: Used to represent hierarchical/mathematical expressions, e.g. an expression tree where internal
nodes are operators and leaves are operands.
26. Binary Tree Representations
● Array (sequential) representation: suited to complete binary trees — for a node at index i, left child is at
2i+1 and right child at 2i+2 (0-indexed); wastes space for non-complete trees.
● Linked representation: each node is a structure with fields [ left pointer | data | right pointer ]; more
common for general binary trees since it doesn't waste memory on missing nodes.
27. Binary Tree Traversals
Traversal means visiting every node of the tree exactly once in a systematic order. There are 3 classic depth-first
traversal orders, defined recursively:
In-order (Left, Root, Right): Visits nodes in ascending sorted order for a Binary Search Tree. Used to get sorted
output.
Pre-order (Root, Left, Right): Visits the root before its subtrees. Used to create a copy of the tree, or a prefix
expression.
Post-order (Left, Right, Root): Visits the root after its subtrees. Used to delete a tree, or evaluate a postfix
expression.
Inorder(node):
if node != NULL:
Inorder([Link])
visit(node)
Inorder([Link])
Worked example — tree with root A, left child B, right child C, B's children D & E: Pre-order: A B D E C. In-order:
D B E A C. Post-order: D E B C A.
28. Threaded Binary Trees
In a normal binary tree, many left/right pointers of leaf nodes are wasted as NULL. A threaded binary tree
replaces these NULL pointers with 'threads' — pointers directly to the node's in-order predecessor or successor
— enabling faster traversal WITHOUT using a stack or recursion.
Single-threaded: Only the NULL right pointers are threaded (point to in-order successor).
Double-threaded: Both NULL left and NULL right pointers are threaded (to in-order predecessor and successor
respectively).
Advantage: Enables faster, non-recursive tree traversal and efficient use of otherwise-wasted NULL pointers.
29. Max Priority Queue
A priority queue is an abstract data type where each element has a 'priority', and the element with the HIGHEST
priority is served first, regardless of insertion order (unlike a normal FIFO queue). A Max Priority Queue always
retrieves/removes the maximum-priority (largest key) element first.
Core operations: insert(x), extractMax() — remove and return the maximum element, peekMax() — view the
max without removing.
Common implementation: A Max Heap (see next topic) implements a max priority queue efficiently, with O(log
n) insert and O(log n) extract-max.
Application: CPU task scheduling by priority, Huffman coding, Dijkstra's/Prim's graph algorithms.
30. Max Heap
A max heap is a complete binary tree in which every parent node's value is GREATER THAN OR EQUAL TO the
values of its children (the 'heap property'). This guarantees the maximum element is always at the root.
Array representation: For a node at index i (0-indexed): parent = (i-1)/2, left child = 2i+1, right child = 2i+2.
Key operations: insert (add at the end, then 'heapify-up'/bubble up by swapping with parent while it's larger);
extractMax (remove root, move last element to root, then 'heapify-down'/sift down by swapping with the larger
child).
Operation Time Complexity
Get max O(1)
Insert O(log n)
Extract max O(log n)
Build heap from n elements O(n)
Application: Heap Sort (Topic 42), priority queues, finding the k largest/smallest elements efficiently.
PART VII — GRAPHS
31. Introduction to Graphs
A graph is a non-linear data structure consisting of a set of vertices (nodes) V and a set of edges E connecting
pairs of vertices. Unlike a tree, a graph can have cycles and no single 'root'.
Directed graph (digraph): Edges have a direction (an ordered pair), e.g. one-way streets, Twitter 'follows'.
Undirected graph: Edges have no direction (an unordered pair), e.g. Facebook friendship.
Weighted graph: Each edge carries a numeric weight/cost, e.g. road distances.
Key terms: Adjacent vertices (connected by an edge), Degree of a vertex (number of edges incident to it;
directed graphs split this into in-degree and out-degree), Path (sequence of vertices connected by edges), Cycle
(a path that starts and ends at the same vertex).
32. Graph Representations
Representation Description Space
Adjacency Matrix A V×V matrix where cell [i][j] = 1 (or weight) if an O(V²)
edge exists between vertex i and j, else 0
Adjacency List Each vertex keeps a list of the vertices it is directly O(V + E)
connected to
Incidence Matrix A V×E matrix showing which vertices are endpoints O(V × E)
of which edges
Adjacency List is generally preferred for sparse graphs (few edges) since it uses less memory; Adjacency Matrix
gives O(1) edge-existence checks and is simpler for dense graphs.
33. Graph Traversal — Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking — it goes 'deep' before going 'wide'. It is
implemented using a Stack (explicitly, or implicitly via recursion).
DFS(v):
mark v as visited
for each unvisited neighbour u of v:
DFS(u)
Applications: Detecting cycles, topological sorting, solving maze/puzzle problems, finding connected
components.
Complexity: O(V + E) using adjacency list.
34. Graph Traversal — Breadth-First Search (BFS)
BFS explores all neighbours of a vertex first (level by level) before moving deeper — it goes 'wide' before going
'deep'. It is implemented using a Queue.
BFS(start):
create empty queue Q; mark start visited; enqueue start
while Q not empty:
v = dequeue(Q)
visit(v)
for each unvisited neighbour u of v:
mark u visited; enqueue(u)
Applications: Finding the shortest path in an unweighted graph, level-order traversal, peer-to-peer networks,
social network 'friends of friends'.
Complexity: O(V + E) using adjacency list.
DFS vs BFS: DFS uses a Stack and goes deep first (good for exhaustive search, cycle detection); BFS uses a Queue
and goes level-by-level (good for shortest path in unweighted graphs).
PART VIII — SEARCHING & SORTING
35. Linear Search
Also called sequential search — checks each element of the list one by one, from the start, until the target is
found or the list ends. Works on both sorted and unsorted lists.
linearSearch(a, n, key):
for i = 0 to n-1:
if a[i] == key: return i
return -1 // not found
Case Complexity
Best case O(1) — found at first position
Worst case O(n) — found at last position or absent
Average case O(n)
36. Binary Search
Works ONLY on a sorted array. Repeatedly compares the target with the middle element and eliminates half of
the remaining search space each time.
binarySearch(a, low, high, key):
while low <= high:
mid = (low+high)/2
if a[mid] == key: return mid
else if a[mid] < key: low = mid+1
else: high = mid-1
return -1
Case Complexity
Best case O(1)
Worst/Average case O(log n)
Requirement: Data MUST be sorted first — this is the key trade-off vs linear search.
37. Hashing
Hashing maps a key to an index in a table (called a hash table) using a hash function, giving very fast average-
case insertion, search and deletion — close to O(1).
Hash function: A function h(key) that computes an array index, e.g. h(key) = key % table_size.
Collision: Occurs when two different keys hash to the same index. Resolved by: Chaining (each table slot holds a
linked list of all keys hashing there) or Open Addressing (probe for the next free slot — linear probing, quadratic
probing, or double hashing).
Operation Average Case Worst Case
Search O(1) O(n) — many collisions
Insert O(1) O(n)
Delete O(1) O(n)
38. Insertion Sort
Builds the sorted array one element at a time — it takes each element and inserts it into its correct position
among the already-sorted elements to its left, shifting larger elements right.
insertionSort(a, n):
for i = 1 to n-1:
key = a[i]; j = i-1
while j >= 0 and a[j] > key:
a[j+1] = a[j]; j = j-1
a[j+1] = key
Case Complexity
Best case (already sorted) O(n)
Worst case (reverse sorted) O(n²)
Space O(1) — in-place
Good for: Small or nearly-sorted data sets; it is stable (keeps equal elements in their original relative order).
39. Selection Sort
Repeatedly finds the MINIMUM element from the unsorted portion of the array and swaps it into its correct
sorted position at the front.
selectionSort(a, n):
for i = 0 to n-2:
min_idx = i
for j = i+1 to n-1:
if a[j] < a[min_idx]: min_idx = j
swap(a[i], a[min_idx])
Case Complexity
Best/Average/Worst case O(n²) — always scans remaining array
Space O(1) — in-place
Note: Performs the minimum possible number of swaps (at most n-1), useful when swap cost is high, but it is
NOT stable.
40. Radix Sort
A non-comparison sort that sorts numbers digit by digit, starting from the Least Significant Digit (LSD) to the
Most Significant Digit, using a stable sub-sort (typically Counting Sort) at each digit position.
Process: 1) Find the max number to know the digit count. 2) Sort by the 1's digit using a stable sort. 3) Sort by
the 10's digit. 4) Continue until the most significant digit is sorted.
Complexity: O(d × (n+k)) where d = number of digits, n = number of elements, k = digit range (usually 10).
Effectively O(n) for fixed-size integers.
Requirement: Works on non-negative integers (or fixed-length keys); needs a stable sub-sort to work correctly.
41. Quick Sort
A divide-and-conquer algorithm: picks a 'pivot' element, partitions the array so all elements less than the pivot
come before it and all greater elements come after, then recursively sorts the two partitions.
quickSort(a, low, high):
if low < high:
p = partition(a, low, high) // places pivot in correct position
quickSort(a, low, p-1)
quickSort(a, p+1, high)
Case Complexity
Best/Average case O(n log n)
Worst case (already sorted, bad pivot choice) O(n²)
Space O(log n) — recursion stack
Note: Very fast in practice due to good cache performance and in-place partitioning; NOT stable. Worst case
avoided in practice using randomised or median-of-three pivot selection.
42. Heap Sort
Uses a Max Heap (Topic 30) to sort: first build a max heap from the array, then repeatedly swap the root
(maximum) with the last element and 'heapify-down' the reduced heap, placing the largest remaining element
correctly each time.
heapSort(a, n):
buildMaxHeap(a, n)
for i = n-1 downto 1:
swap(a[0], a[i])
heapify(a, i, 0) // restore heap property on the reduced heap
Case Complexity
Best/Average/Worst case O(n log n) — consistent, no bad-case degradation
Space O(1) — in-place
Advantage over Quick Sort: Guaranteed O(n log n) even in the worst case, and sorts in-place with O(1) extra
space. Disadvantage: generally slower in practice than Quick Sort due to poorer cache locality, and it is NOT
stable.
43. Comparison of Sorting Methods
Algorithm Best Average Worst Space Stable?
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Radix Sort O(nk) O(nk) O(nk) O(n+k) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Rule of thumb: use Insertion Sort for small/nearly-sorted data; Quick Sort for general-purpose fast average-case
sorting; Heap Sort when a guaranteed worst-case bound and O(1) space matter more than raw speed; Radix Sort
when sorting integers/fixed-length keys and O(n)-like performance is needed.
Predicted Exam / Test Questions (All Topics)
Q: 1. What is an algorithm and what are its characteristics?
A: A finite, well-defined, step-by-step procedure for solving a problem. Characteristics: input, output,
definiteness, finiteness, effectiveness, feasibility, language-independence.
Q: 2. Differentiate between time complexity and space complexity.
A: Time complexity measures the number of operations (steps) an algorithm performs as a function of input size
n; space complexity measures the memory it needs (fixed part + variable part), also as a function of n.
Q: 3. Explain Big-O, Big-Omega and Big-Theta notations.
A: Big-O gives an upper bound (worst case); Big-Omega gives a lower bound (best case); Big-Theta gives a tight
bound (both upper and lower — typical/average case).
Q: 4. Differentiate between a linear and a non-linear data structure, with examples.
A: Linear structures arrange elements sequentially with at most one predecessor/successor each (array, linked
list, stack, queue); non-linear structures arrange elements hierarchically or in a network where an element can
connect to multiple others (tree, graph).
Q: 5. Compare arrays and linked lists.
A: Arrays give O(1) random access but O(n) insertion/deletion and a fixed size; linked lists give O(1)
insertion/deletion at the head but O(n) access and extra pointer memory, with dynamic size.
Q: 6. What is a sparse matrix, and how is it efficiently represented?
A: A matrix with mostly zero elements; represented compactly using triples (row, column, value) for only the
non-zero entries, preceded by a header triple (rows, columns, number of non-zero terms).
Q: 7. Differentiate between a singly linked list, circular linked list, and doubly linked list.
A: Singly: each node points only to the next, last node's next is NULL. Circular: last node's next points back to the
first node. Doubly: each node has both next and previous pointers, allowing bidirectional traversal.
Q: 8. Define a Stack and state its principle of operation.
A: A linear data structure operating on the LIFO (Last In, First Out) principle — the last element pushed is the
first popped. Core operations: push, pop, peek.
Q: 9. Convert the infix expression A+B*C to postfix, and explain your method.
A: Postfix: A B C * +. Method: scan left to right; operands go straight to output; operators are pushed to a stack
but higher/equal precedence operators already on the stack are popped to output first (here, * has higher
precedence than +, so it is resolved before + is pushed).
Q: 10. Evaluate the postfix expression '5 3 4 * +' using a stack.
A: Push 5, push 3, push 4 → see '*' → pop 4 and 3, compute 3*4=12, push 12 → see '+' → pop 12 and 5,
compute 5+12=17, push 17. Final result = 17.
Q: 11. Define a Queue and state its principle of operation.
A: A linear data structure operating on the FIFO (First In, First Out) principle — the first element enqueued is the
first dequeued. Core operations: enqueue, dequeue, peek.
Q: 12. Why is a Circular Queue preferred over a simple array-based Queue?
A: A simple array queue suffers a false-full condition once rear reaches the last index, even if front slots have
been freed; a circular queue wraps rear back to index 0 using modulo arithmetic, reusing freed slots and
avoiding wasted space.
Q: 13. What is a Deque, and what are its two types?
A: A double-ended queue allows insertion and deletion at BOTH ends. Types: input-restricted deque (insertion at
one end only) and output-restricted deque (deletion at one end only).
Q: 14. Define the following tree terms: root, leaf, sibling, degree, height.
A: Root = topmost node (no parent); Leaf = node with no children; Siblings = nodes with the same parent;
Degree of a node = number of its children; Height of a tree = number of edges on the longest root-to-leaf path.
Q: 15. What is a Binary Tree, and list its types.
A: A tree where each node has at most 2 children. Types: full, complete, perfect, skewed, and balanced binary
trees.
Q: 16. Given a binary tree, write out its Pre-order, In-order and Post-order traversals.
A: Pre-order = Root, Left, Right. In-order = Left, Root, Right (gives sorted order for a BST). Post-order = Left,
Right, Root. Example (root A, left B, right C, B's children D,E): Pre: A B D E C. In: D B E A C. Post: D E B C A.
Q: 17. What is a Threaded Binary Tree and why is it used?
A: A binary tree where NULL child pointers are replaced with 'threads' pointing to the in-order
predecessor/successor, enabling faster traversal without a stack/recursion and putting otherwise-wasted NULL
pointers to use.
Q: 18. What is a Max Heap, and what is its complexity for insert and extract-max?
A: A complete binary tree where every parent's value ≥ its children's values, keeping the maximum at the root.
Insert and extract-max are both O(log n).
Q: 19. Differentiate between an Adjacency Matrix and an Adjacency List for graph representation.
A: Adjacency Matrix uses a V×V grid (O(V²) space, O(1) edge check) — good for dense graphs. Adjacency List
stores each vertex's neighbours in a list (O(V+E) space) — more memory-efficient for sparse graphs.
Q: 20. Differentiate between DFS and BFS graph traversal.
A: DFS uses a Stack (or recursion) and explores as deep as possible before backtracking; BFS uses a Queue and
explores level by level. DFS suits exhaustive search/cycle detection; BFS suits shortest path in an unweighted
graph.
Q: 21. Differentiate between Linear Search and Binary Search.
A: Linear search checks elements sequentially, O(n), works on unsorted data. Binary search repeatedly halves
the search space, O(log n), but REQUIRES the data to be sorted first.
Q: 22. What is hashing, and how are collisions resolved?
A: Hashing maps a key to a table index via a hash function for near-O(1) average access. Collisions (two keys
mapping to the same index) are resolved by chaining (linked list per slot) or open addressing (probing for the
next free slot).
Q: 23. Compare Insertion Sort and Selection Sort.
A: Both are O(n²) in the worst case and O(1) space, but Insertion Sort is adaptive (O(n) best case on nearly-
sorted data) and stable, while Selection Sort always does O(n²) comparisons regardless of input order and is not
stable, though it minimises the number of swaps.
Q: 24. Explain how Radix Sort works and state its complexity.
A: Radix sort sorts numbers digit by digit from least to most significant digit using a stable sub-sort (e.g. counting
sort) at each digit position. Complexity: O(d(n+k)), effectively linear for fixed-length keys.
Q: 25. Compare Quick Sort and Heap Sort.
A: Quick Sort averages O(n log n) and is usually faster in practice (good cache locality) but degrades to O(n²)
worst case; Heap Sort guarantees O(n log n) in all cases and uses O(1) space, but is generally slower in practice
and not stable.
Q: 26. Which sorting algorithm would you choose for (a) nearly sorted data (b) guaranteed worst-case
performance (c) sorting large integers?
A: (a) Insertion Sort — adaptive, fast on nearly-sorted input. (b) Heap Sort — guarantees O(n log n) with no bad-
case degradation. (c) Radix Sort — near-linear time for fixed-length integer keys.
Master Cheat-Sheet
● Algorithm = finite, unambiguous, step-by-step solution. 7 characteristics: input, output, definiteness,
finiteness, effectiveness, feasibility, language-independence.
● Space complexity = fixed part + variable part. Time complexity = step count → expressed with
Big-O/Ω/Θ.
● Growth order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
● Linear DS: array, linked list, stack, queue. Non-linear DS: tree, graph.
● Array: O(1) access, O(n) insert/delete. Linked List: O(n) access, O(1) head insert/delete.
● Sparse matrix: store only non-zero (row, col, value) triples.
● Singly list: one-way. Circular list: last→first. Doubly list: prev + next pointers both ways.
● Stack = LIFO (push/pop/peek). Queue = FIFO (enqueue/dequeue/peek). Deque = both ends.
● Circular Queue fixes array queue's false-full problem via modulo wraparound.
● Infix→Postfix uses an operator stack + precedence rules. Postfix evaluation uses a single operand stack.
● Tree traversals: Pre(Root-L-R), In(L-Root-R, sorted for BST), Post(L-R-Root).
● Threaded binary tree: NULL pointers replaced by threads to in-order predecessor/successor.
● Max Heap: parent ≥ children; array indices — left=2i+1, right=2i+2, parent=(i-1)/2. Insert/extract-max =
O(log n).
● Graph reps: Adjacency Matrix O(V²) (dense, O(1) lookup); Adjacency List O(V+E) (sparse, memory-
efficient).
● DFS = Stack, goes deep first, O(V+E). BFS = Queue, goes level-by-level, O(V+E), gives shortest path
(unweighted).
● Linear search O(n) any order. Binary search O(log n), requires sorted data.
● Hashing ≈ O(1) average; collisions resolved via chaining or open addressing.
● Insertion Sort: O(n²) worst, O(n) best, stable. Selection Sort: always O(n²), not stable, fewest swaps.
● Radix Sort: O(d(n+k)), non-comparison, digit-by-digit, needs a stable sub-sort.
● Quick Sort: O(n log n) avg, O(n²) worst, not stable, in-place, fast in practice.
● Heap Sort: O(n log n) guaranteed always, O(1) space, not stable, generally slower in practice than Quick
Sort.
Good luck — go topic by topic, and use the pseudocode blocks to practise tracing through small examples by
hand.