Arrays, Stacks, Queues and Linked Lists
The linear structures are the part of this section where the questions are most predictable, which makes them the most reliably scored. Arrays ask for an address: an element's position is arithmetic on the base address, and the only thing to be careful about is which index varies fastest — row-major runs along a row, column-major down a column, and the same element in the same array has two different addresses under the two conventions. Stacks ask you to run something: evaluate a postfix expression, convert infix to postfix, check balanced brackets, or say how deep the stack gets. All of those are the same skill, which is simulating a last-in-first-out discipline without losing your place. Queues ask about the boundary: in a circular queue implemented in an array of size n, the full and empty conditions collide unless one slot is sacrificed, so the usual implementation holds only n − 1 elements and is full when (rear + 1) mod n equals front — a question about a size-10 circular queue almost always wants the answer 9. And linked lists ask which operations are cheap. That is decided entirely by what a node can reach: a singly linked list cannot go backwards, so deleting the last node is O(n) no matter how many pointers you keep to the ends, because you need the second-to-last node. Add backward links and the same operation is O(1). Nothing in this chapter is deep, and all of it is easy to get wrong at speed, so the value is in having the boundary conditions settled in advance.
Stacks: Evaluate, Convert, and Measure the Depth
| Token | Action | Stack after |
|---|---|---|
| 5, 3, 2 | Push each | 5, 3, 2 |
| * | Pop 2 and 3, push 3 × 2 | 5, 6 |
| + | Pop 6 and 5, push 11 | 11 |
| 8, 4 | Push each | 11, 8, 4 |
| / | Pop 4 and 8, push 8 / 4 | 11, 2 |
| − | Pop 2 and 11, push 11 − 2 | 9 |
🧠 The order of the two pops is the whole of the difficulty
For a non-commutative operator the second value popped is the left operand. Seeing 8 4 / and computing 4 / 8 instead of 8 / 4 is the single commonest error in postfix evaluation, and it is invisible in the answer because both produce a number. Addition and multiplication hide the mistake entirely, which is why questions always include a subtraction or a division. The same reversal governs prefix evaluation, scanned right to left, where the first value popped is the left operand — so the two notations need opposite habits and are worth practising separately rather than as one topic.Circular Queues, and What a Linked List Cannot Reach
🎯 Why a size-n circular queue holds only n − 1
With two indices, front and rear, an empty queue and a completely full queue look identical — front equals rear in both — so the implementation cannot tell them apart. The standard fix is to waste one slot: the queue is full when (rear + 1) mod n equals front, and empty when rear equals front, which are now distinguishable conditions. The cost is one element of capacity, so an array of 10 holds 9. The alternative fix is to keep an explicit count or a full flag, which recovers the tenth slot at the cost of an extra field — and a question that says "without using a counter" is telling you which convention it wants.| Operation | Singly linked, head + tail pointers | Doubly linked, head + tail |
|---|---|---|
| Insert at front | O(1) | O(1) |
| Insert at end | O(1) — tail pointer suffices | O(1) |
| Delete at front | O(1) | O(1) |
| Delete at end | O(n) — the previous node is unreachable | O(1) |
| Delete a node given a pointer to it | O(n) in general | O(1) |
The pattern in that table is worth stating as a rule rather than memorised row by row: an operation is O(1) exactly when every pointer it must modify is reachable in constant time. Deleting at the end requires writing the second-to-last node's next field, and a singly linked list gives no way to that node from the tail — which is why a tail pointer does not help, a fact worth being sure of because it looks as though it should.
Key takeaways
- Row-major: base + w × (i × cols + j). Column-major: base + w × (j × rows + i). Same element, different addresses.
- With explicit lower bounds, subtract them from both indices — and compute the row length from the bounds too.
- In postfix evaluation the second value popped is the left operand — the error is invisible for + and ×.
- A circular queue in an array of size n holds n − 1 elements; full is (rear + 1) mod n == front.
- An operation is O(1) exactly when every pointer it must modify is reachable in constant time.
- Deleting the last node of a singly linked list is O(n) even with a tail pointer — you need the node before it.
- Insertion at either end of a singly linked list is O(1) if both head and tail pointers are kept.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
An array int A[10][20] is stored row-major starting at address 1000, with 4 bytes per element and 0-based indices. What is the address of A[5][7]?
Numerical answer — type the value.
Show answer
Answer: 1428
Row-major means whole rows precede the element: five complete rows of 20, then seven elements. 1000 + 4 × (5 × 20 + 7) = 1000 + 4 × 107 = 1428. Two checks. Column-major on the same array gives 1000 + 4 × (7 × 10 + 5) = 1300, so if your answer matched that you used the wrong convention. And if the declaration had read A[1..10][1..20], the indices would each drop by one and the answer would be 1344 — which is why the bounds are the first thing to read.Evaluate the postfix expression 5 3 2 * + 8 4 / − using integer arithmetic.
Numerical answer — type the value.
Show answer
Answer: 9
Push 5, 3, 2. On*pop 2 then 3 and push 6, leaving 5, 6. On+push 11. Push 8, 4. On/pop 4 then 8 and push 8/4 = 2. On−pop 2 then 11 and push 11 − 2 = 9. The two operators that can go wrong are/and−, because the second value popped is the left operand: computing 4/8 = 0 and then 2 − 11 = −9 is the standard failure, and it produces a plausible-looking number. In infix the expression is 5 + 3 × 2 − 8 / 4, which is 5 + 6 − 2 = 9 — worth doing as a check, since converting back is quick and catches operand-order slips immediately.A circular queue is implemented in an array of size 10 using only front and rear indices, with no separate counter. Its maximum capacity is:
Show answer
Answer: B — 9
With only two indices, "empty" and "completely full" both give front == rear, so the two states are indistinguishable. Sacrificing one slot separates them: full becomes (rear + 1) mod 10 == front, empty stays rear == front, and the capacity is 9. The phrase "no separate counter" in the question is the instruction to use this convention — with a counter or a full flag the tenth slot is usable and the answer would be 10. Reading which convention is being asked for matters more here than the arithmetic does.In a singly linked list with pointers kept to both the head and the tail, which operation still takes O(n) time?
Show answer
Answer: C — Deleting the last node
Deleting the last node means setting the second-to-last node'snextto NULL, and in a singly linked list there is no way from the tail back to that node — so it must be found by walking from the head, which is O(n). A tail pointer lets you reach the last node in O(1) but not the one before it, and that gap is the whole answer; it is worth being sure of, because intuition says a tail pointer ought to solve every end-of-list problem. Inserting at the end is fine (B) because it only writes the current tail'snext, which the tail pointer reaches directly. Making the list doubly linked reduces the deletion to O(1).An array A[1..10][1..20] of 4-byte elements is stored row-major with base address 1000. What is the address of A[5][7]?
Numerical answer — type the value.
Show answer
Answer: 1344
The lower bound is 1, so both indices reduce by one before use: 1000 + 4 × ((5 − 1) × 20 + (7 − 1)) = 1000 + 4 × 86 = 1344. Compare with the 0-based version of the same array, which gives 1428 — an 84-byte difference produced entirely by the declaration, and the reason the bounds must be read before the arithmetic begins. The row length is 20 in both cases here, but in general it too comes from the bounds as hi₂ − lo₂ + 1, and assuming it rather than computing it is the second way this question is lost.Which of the following are O(1) in a doubly linked list holding pointers to both ends? (More than one may be correct.)
Show answer
Answer: A — Deleting the last node; B — Deleting a node given only a pointer to that node; D — Inserting before a node given a pointer to it
A, B and D, and they are one property three times: a doubly linked node reaches both its neighbours, so every pointer any of these operations must rewrite is available immediately. That is exactly what a singly linked list cannot do — B and D are O(n) there, because reaching the previous node requires a walk. C is O(n) in both, and that is the honest limit of linked lists: they give up indexed access, which is what an array is for. A question offering "find the k-th element" among linked-list operations is testing whether the trade-off is understood rather than the mechanics.A stack is used to check whether a string of brackets is balanced. The stack reaches its maximum depth when:
Show answer
Answer: B — The nesting is deepest
Each unmatched opening bracket sits on the stack until its partner arrives, so the depth at any moment is the current nesting level and the maximum is the deepest nesting. Length is irrelevant:()()()()()is ten characters with a maximum depth of one, while((((()))))is the same length with a depth of five. That distinction is the point of the question, and the same reasoning gives the standard result for expression evaluation — the stack depth needed is the depth of the expression tree, not the number of tokens.The same element A[5][7] of int A[10][20] based at 1000 has address 1428 row-major. Its column-major address is:
Show answer
Answer: B — 1300
Column-major stores columns contiguously, so seven whole columns of 10 elements precede the target, then five more: 1000 + 4 × (7 × 10 + 5) = 1000 + 300 = 1300. Note which dimension multiplies: row-major multiplies the row index by the number of columns, column-major multiplies the column index by the number of rows, and swapping those two is the error the question is built to catch. Option C is the 1-based row-major answer, included because these three numbers — 1428, 1344, 1300 — are the three ways the same element can be addressed depending on convention and bounds.