Cheat Sheet

Quick Reference

Recursion

  • ›n / 10 — removes last digit
  • ›n % 10 — gets last digit
  • ›a × b = a + a×(b-1)
  • ›b^p = b × b^(p-1)
  • ›n! = n × (n-1)!
  • ›Base case: n == 0 or n == 1
  • ›Print before call → descending
  • ›Print after call → ascending

Singly Linked List

  • ›class Node { data; next; }
  • ›head = NULL initially
  • ›Insert beginning: O(1)
  • ›Insert end: traverse to temp->next == NULL
  • ›Delete end: temp->next->next == NULL
  • ›Position traversal: i < pos - 1
  • ›Display: while(temp != NULL)

Circular LL Differences

  • ›Last node → head (not NULL)
  • ›Empty first node: next = itself
  • ›One node check: head->next == head
  • ›Traverse: temp->next != head
  • ›Display: do-while loop ⚠️
  • ›Insert/delete beginning: update last too
  • ›Self-loop: newNode->next = newNode

Stack

  • ›LIFO — Last In, First Out
  • ›Array: top = -1, arr[++top]
  • ›LL: top = NULL, insert at head
  • ›isEmpty: top == -1 (arr) or NULL
  • ›isFull: top == maxSize-1 (array only!)
  • ›Pop: return arr[top--]
  • ›Display: top to bottom

Queue Formulas

  • ›FIFO — First In, First Out
  • ›Both: front = rear = -1
  • ›Simple full: rear == size-1
  • ›Circular full: (rear+1) % size == front
  • ›Circular enqueue: rear = (rear+1) % size
  • ›Circular dequeue: front = (front+1) % size
  • ›Last element removed: reset to -1

Node Swap Steps

  • ›Find currX, prevX, currY, prevY
  • ›Check if either value not found
  • ›Handle head node cases
  • ›prevX->next = currY
  • ›prevY->next = currX
  • ›Swap their next pointers
  • ›Use temp variable for swap

Final Exam Checklist

✅ Always use class — NEVER struct

✅ Node class needs public: for data and next

✅ LinkedList class has private: head

✅ Check for empty list and single node edge cases

✅ Always delete nodes when removing

✅ Circular LL display uses do-while

✅ Circular Queue uses % operator

✅ Stack LL has NO isFull()