Review the key points with a cheat sheet, six code-reading questions, and a checklist of common mistakes.
| Structure | Characteristic | Typical use |
|---|---|---|
| Array | Direct indexed access | Fixed-length data |
| Linked list | Fast insertion and deletion at a known position | Data whose length changes |
| Stack | Last in, first out (LIFO) | Function calls and undo |
| Queue | First in, first out (FIFO) | Waiting lines and BFS |
struct Node { int value; struct Node *next; // Pointer to the next node }; // The last node has next == NULL
// Stack (LIFO): push / pop push(1); push(2); push(3); pop(); // → 3 (inserted last) // Queue (FIFO): enqueue / dequeue enqueue(1); enqueue(2); enqueue(3); dequeue(); // → 1 (inserted first)
| Name | Approach | Complexity |
|---|---|---|
| Bubble | Compare and swap neighbors | O(N²) |
| Selection | Select the minimum and move it to the front | O(N²) |
| Insertion | Insert into the correct position in the sorted portion | O(N²) |
| Method | Requirement | Complexity |
|---|---|---|
| Linear search | None | O(N) |
| Binary search | Sorted input is required | O(log N) |
// Push onto a stack, then pop once: what is returned? push(10); push(20); push(30); int v = pop(); printf("%d\n", v);
30. Think of taking the top plate off a pile.enqueue(10); enqueue(20); enqueue(30); int v = dequeue(); printf("%d\n", v);
10. Think of the first person in a checkout line being served first.int a[] = {5, 2, 8, 1, 9}; // N=5 for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1 - i; j++) { if (a[j] > a[j+1]) /* swap */; } }
10. In general this version makes N(N-1)/2 comparisons and has O(N²) complexity.// Find an item among 1024 sorted values // Approximately how many comparisons does binary search need at worst?
10. An implementation may need one final comparison. Complexity is O(log N), and sorted input is required.struct Node *cur = head; while (cur->next != NULL) { cur = cur->next; } // What does cur point to now?
cur->next != NULL, the loop stops on the last node, whose next is NULL. With cur != NULL, it would instead stop after cur itself becomes NULL.int a[] = {5, 2, 8, 1, 9}; // One selection-sort pass: find the minimum and move it to the front
{1, 2, 8, 5, 9}. Later passes repeat the process on the remaining unsorted portion.push/pop is LIFO; enqueue/dequeue is FIFO. Remember their everyday analogies : plates versus a checkout line. cur != NULLand cur->next != NULLwere confused free a linked-list node free to avoid a memory leaks . Save next in a separate variable before freeing the current node. j < N - 1 - ior j >= 1: an off-by-one boundary can cause Out-of-bounds access .
O(N²)Underestimated the cost of a = b; b = a; makes both variables equal the old b. int t = a; a = b; b = t; preserves the value through a temporary variable. next when its meaning is unclear
Dynamic memory Review allocating and releasing nodes
Cheat sheet Review complexity and data structures on one page