Part III — Linear Data Structures

Every data structure problem you encounter in a technical interview rests on a surprisingly small foundation. Strip away the complexity of balanced trees, hash maps, and graphs, and you find the same four building blocks underneath: arrays, linked lists, stacks, and queues. Master these, and you hold the raw materials from which every more complex structure is assembled.

This part of the book dissects each of these four structures in depth. Before diving into individual chapters, though, you need to understand why these structures exist and how they differ at the hardware level — because that understanding transforms you from someone who memorizes operations tables into someone who reasons from first principles under interview pressure.

Why Linear Data Structures Dominate Interviews

Linear data structures store elements in a sequential order. Every element has at most one predecessor and one successor. This sequential nature makes them accessible to reason about, yet rich enough to test deep algorithmic thinking.

Interviewers reach for linear structure problems because they sit at a sweet spot of difficulty. A linked list reversal problem requires no exotic knowledge — every candidate has heard of linked lists — but the in-place reversal exposes whether you can manipulate pointers under pressure without losing track of references. A stack-based expression evaluator reveals whether you can translate abstract rules into clean, bug-free code. A circular queue implementation tests your ability to handle modular arithmetic and boundary conditions.

These problems also serve as gatekeepers. If you stumble on array traversal or lose a pointer during list manipulation, the interviewer knows that tree and graph problems will not go well. Demonstrating fluency with linear structures builds confidence — yours and the interviewer’s.

Contiguous vs. Linked Memory: The Fundamental Trade-Off

At the hardware level, memory is a flat sequence of bytes. How a data structure arranges its elements within that flat space determines its performance characteristics.

Contiguous allocation places all elements side by side in a single block of memory. Arrays use this layout. When you access arr[5], the CPU computes the memory address as base + 5 * elementSize — a single arithmetic operation. No indirection, no pointer chasing. Modern CPUs exploit this layout aggressively: when you read arr[5], the processor loads an entire cache line (typically 64 bytes) into L1 cache, which means arr[6], arr[7], and several neighbors are already in cache when you need them. Sequential array traversal achieves memory bandwidth close to the theoretical maximum.

Linked allocation scatters elements across the heap. Each node holds its data plus a pointer (or two) to neighboring nodes. Accessing the fifth element requires following five pointer hops — each hop potentially causing a cache miss. On modern hardware, a cache miss costs 100–300 CPU cycles. When traversing a linked list of 10,000 nodes scattered across the heap, those cache misses accumulate into measurable performance differences.

This is not an academic distinction. Interviewers ask about memory layout because it reveals whether you understand why an ArrayList outperforms a LinkedList for sequential access in Java, not because they want you to recite textbook definitions.

Access Patterns: Random vs. Sequential

The choice between contiguous and linked storage maps directly to two access patterns:

Random access — reaching any element by index in constant time — is the superpower of arrays. Need the element at position 10,000? One address calculation. Linked lists cannot compete here; reaching position 10,000 requires 10,000 pointer traversals.

Sequential modification — inserting or removing elements in the middle — is where linked lists shine. Inserting a node into a linked list requires updating two pointers, an O(1) operation once you have a reference to the insertion point. Inserting into the middle of an array forces every subsequent element to shift right, an O(n) operation that becomes expensive as the array grows.

Understanding which access pattern a problem demands is the first decision you make when choosing a data structure in an interview.

Comparison Table: Time Complexities

Operation	Array (unsorted)	Array (sorted)	Singly Linked List	Doubly Linked List	Stack	Queue
Access by index	O(1)	O(1)	O(n)	O(n)	O(n)*	O(n)*
Search	O(n)	O(log n)	O(n)	O(n)	O(n)	O(n)
Insert at head	O(n)	O(n)	O(1)	O(1)	—	—
Insert at tail	O(1) amort.	O(n)	O(n)† / O(1)‡	O(1)	O(1)	O(1)
Insert at middle	O(n)	O(n)	O(1)§	O(1)§	—	—
Delete at head	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
Delete at tail	O(1)	O(1)	O(n)	O(1)	—	—
Delete at middle	O(n)	O(n)	O(1)§	O(1)§	—	—
Space per element	1 element	1 element	element + 1 pointer	element + 2 pointers	varies	varies

Stack and queue access by index violates their design contracts — you are not supposed to peek at arbitrary positions. Some implementations allow it in O(n), but interviewers expect you not to use it.

†Without tail pointer ‡With tail pointer §Given a reference to the node

This table belongs on your mental cheat sheet. When an interviewer describes a problem, scan the required operations, check the table, and the right structure reveals itself.

What Lies Ahead

The four chapters in this part build your mastery from the ground up:

Arrays — You start with contiguous memory, cache performance, and dynamic resizing with amortized analysis. Then you tackle the interview workhorses: two-pointer traversals, prefix sums, and Kadane’s algorithm. These patterns recur so frequently that internalizing them gives you an immediate edge.

Linked Lists — You move to pointer-based structures, where the challenge shifts from index arithmetic to reference management. Floyd’s cycle detection, in-place reversal, and sorted list merging form the core interview repertoire. The dummy node technique eliminates an entire class of edge-case bugs.

Stacks — LIFO semantics unlock a category of problems that appear deceptively complex but collapse into elegant solutions once you recognize the stack pattern. Balanced parentheses, monotonic stacks for “next greater element” problems, and expression evaluation are your targets.

Queues — FIFO ordering, circular buffers, and priority queues round out your linear structure toolkit. BFS traversal, the classic “implement queue with two stacks” problem, and task scheduling with cooldown demonstrate the queue’s versatility.

Each chapter follows the same structure: internals and memory analysis, Java 25 implementations, and then a sequence of classic interview problems with full solutions and complexity analysis. By the end of this part, you will handle any linear data structure problem an interviewer can produce — and you will handle it with the kind of fluency that distinguishes a strong hire from a borderline one.

Let’s begin with the structure you will reach for most often: the array.