Arrays, Stacks, Queues & Linked Lists

The linear data structures look like four separate topics and are really one. Each is a different answer to a single question: where in the sequence are insertions and deletions allowed?

An array allows access anywhere and insertion nowhere cheaply. A linked list allows insertion anywhere cheaply and access nowhere cheaply. A stack allows both, but only at one end. A queue allows insertion at one end and deletion at the other.

Every cost, every implementation choice and every application follows from that restriction, so a question about any of them is answered by asking what the restriction permits.

The second organising fact is that arrays and linked lists trade the same two costs in opposite directions. An array stores elements contiguously, so it can compute any element's address arithmetically but must shift elements to make room. A linked list stores each element with a pointer to the next, so it can splice in a node by changing two pointers but must walk from the start to find anything.

There is no third option that wins both. Every more elaborate structure in later chapters is an attempt to buy back one cost without paying the other in full.

1. Arrays

An array occupies contiguous memory, so the address of element $i$ is computed rather than searched for.

$\text{address}(a[i])=\text{base}+i\times \text{sizeof(element)}$

That single formula is the array's entire advantage: constant-time access to any element regardless of position, and perfect cache behaviour on sequential traversal because consecutive elements share cache lines.

The costs follow equally directly from contiguity.

Inserting at position $i$ requires shifting every later element up by one, costing $O(n)$ in the worst case and $O(n)$ on average. Deleting requires shifting down. Only insertion and deletion at the very end avoid the shift.

The size is fixed at allocation. A dynamic array grows by allocating a larger block and copying, and doubling the capacity on each growth gives amortised constant-time appends — because the total copying cost across $n$ appends is bounded by $2n$.

2. Linked Lists

A linked list stores each element in a node containing the data and a pointer to the next node. The nodes need not be adjacent in memory.

Insertion and deletion cost $O(1)$ — given a pointer to the right place. Splicing a node in changes two pointers and touches nothing else, which is the whole reason linked lists exist.

The qualification is where the marks are. Finding that place costs $O(n)$, because the only way to reach node $i$ is to follow $i$ pointers from the head.

Deleting a node from a singly linked list requires a pointer to its predecessor, since the predecessor's next pointer must be updated. Given only the node itself, the standard trick is to copy the successor's data into it and delete the successor instead — which fails for the last node.

Three variants address specific weaknesses.

A doubly linked list adds a previous pointer, making backward traversal possible and making deletion $O(1)$ given only the node. The cost is one extra pointer per node and two extra updates per operation.

A circular list makes the last node point to the first, so traversal never falls off the end and any node can serve as an entry point. This suits round-robin scheduling directly.

A header or sentinel node removes the special case for an empty list, since the list is never truly empty and no operation needs to check for a null head.

3. Arrays Versus Linked Lists

The comparison is examined constantly and reduces to three points.

Access is the array's win: constant time against linear time, because the address is computed rather than followed.

Structural modification is the list's win: two pointer updates against shifting half the elements on average.

Memory behaviour favours the array more than the asymptotics suggest. An array stores only data, while a list pays a pointer per node — often as much as the data itself for small elements. And contiguous storage means a traversal reads full cache lines, while list nodes scattered across memory can miss on every access.

The practical consequence is that for small $n$, or for any workload dominated by traversal, an array frequently outperforms a list even where the asymptotic analysis favours the list.

4. Stacks

A stack permits insertion and deletion at one end only, giving last-in-first-out order.

Both operations are $O(1)$ in either implementation. An array implementation keeps a top index and is fastest, but has a fixed capacity. A linked implementation pushes at the head and has no capacity limit, at the cost of a pointer per element.

Underflow is popping an empty stack and overflow is pushing a full array-based one, and both must be checked.

The applications are what GATE actually examines.

Function calls use a stack, because the nesting discipline of calls matches last-in-first-out exactly, and this is what makes recursion possible.

Balanced-parenthesis checking pushes each opening symbol and pops on each closing one, verifying the popped symbol matches. The string is balanced if every pop matches and the stack is empty at the end.

Infix-to-postfix conversion uses a stack to hold operators awaiting their right operands, popping any operator of higher or equal precedence before pushing a new one.

Postfix evaluation pushes operands and, on each operator, pops two, applies, and pushes the result. The final stack holds one value.

Depth-first traversal of a graph or tree uses a stack, explicitly or via recursion, and that is the same structure in a different guise.

5. Queues

A queue permits insertion at the rear and deletion at the front, giving first-in-first-out order.

A naive array implementation moves the front index forward on each dequeue, wasting the vacated space and eventually reporting full while most of the array is empty.

A circular queue fixes this by wrapping the indices modulo the capacity, so the space is reused. The wrap introduces one genuine difficulty.

Full and empty both give front equal to rear, and distinguishing them requires either keeping one slot permanently unused or maintaining an explicit count.

With one slot sacrificed, a queue of capacity $N$ holds $N-1$ elements, and the conditions become:

$\text{empty}\equiv (\text{front}=\text{rear})\text{full}\equiv ((\text{rear}+1)\mathrm{mod}N=\text{front})$

The number of elements is $(\text{rear}-\text{front}+N)\mathrm{mod}N$, and the $+N$ is what handles the wrap correctly.

A deque permits insertion and deletion at both ends, and it generalises both stack and queue — restricting it to one end gives a stack, and to opposite ends gives a queue.

A priority queue dequeues by priority rather than arrival order, which breaks the first-in-first-out contract entirely and is implemented with a heap rather than a linear structure.

The applications mirror the stack's and are examined in the same way.

Breadth-first traversal uses a queue, exactly as depth-first uses a stack, and the choice of container is the only difference between the two algorithms. Replacing the queue with a stack in a breadth-first search turns it into a depth-first one.

Scheduling uses a queue whenever fairness matters, since first-in-first-out guarantees that no waiting job is passed over indefinitely. Round-robin scheduling is a circular queue read repeatedly.

Buffering between a fast producer and a slow consumer uses a queue, absorbing bursts so that neither side blocks unnecessarily. Keyboard input, print spooling and network packet handling are all this pattern.

The unifying observation is that a stack reverses order while a queue preserves it, and each application picks whichever property it needs.

6. Implementing One From Another

Two conversions are examined regularly, and both are worth being able to derive.

A queue can be built from two stacks. Push incoming elements onto stack A. To dequeue, if stack B is empty, pop everything from A into B, which reverses the order; then pop from B.

Each element is moved between stacks at most twice, so the amortised cost per operation is $O(1)$ even though a single dequeue can cost $O(n)$.

A stack can be built from two queues, but less gracefully. One approach makes push $O(1)$ and pop $O(n)$: to pop, dequeue all but the last element into the second queue and return the last. The other makes push $O(n)$ and pop $O(1)$ by reversing on every insertion.

The asymmetry is instructive. Two stacks give an efficient queue because reversal is exactly what converts last-in-first-out into first-in-first-out, while two queues cannot reverse anything and must therefore move elements repeatedly.

7. Worked Examples

Example 1. An array a[10][20] of 4-byte integers has base address 1000 and is stored in row-major order. Find the address of a[6][12].

Row-major means all of row 0 is stored first, then row 1, and so on. Reaching a[i][j] skips $i$ complete rows of 20 elements, then $j$ further elements.

$\text{address}=1000+(6\times 20+12)\times 4=1000+132\times 4=1000+528=1528$

The address is 1528.

Under column-major storage the formula reverses to base plus $(j\times R+i)$ times the element size, giving $1000+(12\times 10+6)\times 4=1000+504=1504$.

C uses row-major, so the first answer applies to C code, and the difference matters for performance as well as correctness: traversing along rows walks contiguous memory while traversing along columns strides across it.

Example 2. A circular queue has capacity 8 with one slot sacrificed. Front is 6 and rear is 2. How many elements does it hold, and is it full?

The element count wraps, so use the modular formula.

$(\text{rear}-\text{front}+N)\mathrm{mod}N=(2-6+8)\mathrm{mod}8=4$

The queue holds 4 elements.

For fullness, check whether advancing rear would collide with front: $(2+1)\mathrm{mod}8=3$, which is not equal to 6, so the queue is not full.

With one slot sacrificed, the maximum occupancy is $8-1=7$ elements, and this queue is holding 4 of them.

Note why the $+N$ matters. Computing $2-6$ directly gives $-4$, and taking a negative value modulo 8 is either wrong or implementation-dependent depending on the language. Adding $N$ first guarantees a non-negative operand.

Example 3. Convert the infix expression A + B * C - D / E to postfix using a stack.

Scan left to right, outputting operands immediately and using the stack for operators.

A is an operand: output. Output so far: A.

+ : the stack is empty, so push it.

B : output. Output: A B.

* : the stack top is +, which has lower precedence than *, so do not pop. Push *.

C : output. Output: A B C.

- : the stack top is *, which has higher precedence, so pop and output it. Now the top is +, equal precedence and left-associative, so pop and output that too. Then push -. Output: A B C * +.

D : output. Output: A B C * + D.

/ : the stack top is -, lower precedence, so push /.

E : output. Output: A B C * + D E.

End of input: pop the remaining operators. Pop /, then -.

The postfix expression is A B C * + D E / -.

The rule that does the work is: pop while the stack top has higher or equal precedence, then push. Equal precedence is popped because the operators are left-associative; for a right-associative operator such as exponentiation, equal precedence is not popped.

Example 4. Evaluate the postfix expression 5 3 + 8 2 - * using a stack.

Scan left to right, pushing operands and applying operators to the top two.

Push 5. Push 3. Stack: 5, 3.

+ : pop 3 and 5, compute $5+3=8$, push 8. Stack: 8.

Push 8. Push 2. Stack: 8, 8, 2.

- : pop 2 and 8, compute $8-2=6$, push 6. Stack: 8, 6.

* : pop 6 and 8, compute $8\times 6=48$, push 48. Stack: 48.

The result is 48.

The critical detail is operand order for non-commutative operators. The first value popped is the right operand and the second is the left, so 8 2 - means $8-2$ and not $2-8$. Getting this backwards is the single most common error in postfix evaluation, and it is invisible for + and *.

Example 5. Given only a pointer to a node in the middle of a singly linked list, delete it in constant time. What breaks?

The obvious approach fails: deleting a node requires updating its predecessor's next pointer, and a singly linked list gives no way to reach the predecessor except by walking from the head, which is $O(n)$.

The standard trick sidesteps this. Instead of removing the node, copy the successor's data into the node and then delete the successor.

Concretely, if the node holds value $X$ and its successor holds $Y$, overwrite $X$ with $Y$ and then splice out the successor by setting the node's next pointer to the successor's next.

The list now contains the right sequence of values, the node count is right, and the cost is $O(1)$.

Two things break. The trick fails for the last node, since there is no successor to copy from, and it leaves the last node's predecessor pointing at a node that should be gone. And any external pointer that referred to the successor node now refers to a freed node, which is a dangling pointer.

The clean solution is a doubly linked list, where the previous pointer makes the predecessor immediately available and the deletion is genuinely $O(1)$ with no caveats.

Example 6. Implement a queue using two stacks and analyse the amortised cost.

Keep two stacks, called in and out.

Enqueue pushes onto in, which is $O(1)$ unconditionally.

Dequeue checks out. If it is non-empty, pop from it. If it is empty, pop every element from in and push each onto out, then pop from out.

The transfer reverses the order, so the element that entered in first ends up on top of out — which is exactly first-in-first-out.

For the cost: a single dequeue can cost $O(n)$ when a transfer happens. But each element is pushed onto in once, popped from in once, pushed onto out once and popped from out once — four operations over its entire lifetime, regardless of how many dequeues occur.

So $n$ operations cost $O(n)$ in total, giving $O(1)$ amortised per operation.

The contrast with building a stack from two queues is worth noting. That direction has no cheap solution, because a queue cannot reverse a sequence, so one of push or pop must move every element on every call.

Summary

Every linear structure answers one question: where are insertions and deletions allowed.

An array computes element addresses arithmetically, giving $O(1)$ access and perfect cache behaviour, but insertion and deletion cost $O(n)$ because elements must shift. Doubling on growth makes appends amortised $O(1)$.

A linked list splices nodes with two pointer updates, giving $O(1)$ insertion and deletion given a pointer, but $O(n)$ access because the only route to a node is through its predecessors.

Deleting from a singly linked list needs the predecessor. A doubly linked list makes it $O(1)$ at the cost of one extra pointer, a circular list removes the end case, and a sentinel node removes the empty case.

The array's advantage is larger in practice than in the asymptotics, because a list pays a pointer per node and scatters its data across cache lines.

A stack is one-ended and gives last-in-first-out. It underlies function calls, balanced-parenthesis checking, infix-to-postfix conversion, postfix evaluation and depth-first traversal.

A queue is two-ended and gives first-in-first-out. A circular implementation reuses space, and full and empty are distinguished by sacrificing a slot or keeping a count. The element count is the difference of indices plus the capacity, taken modulo the capacity.

A deque generalises both; a priority queue abandons arrival order entirely and is built on a heap.

Two stacks give a queue at $O(1)$ amortised cost, because reversal converts one ordering into the other. Two queues give a stack only awkwardly, because a queue cannot reverse.