Lists, Stacks, Queues, and Deques

Lists, Stacks, Queues, and Deques

Building on the core data structures introduced in Chapter 2—such as ArrayList and LinkedList for lists, and HashMap for maps—this section delves into linear structures essential for sequential data processing. Leveraging modern Java 21+ features, we define and implement linked lists, stacks, queues, and deques, with a focus on interview-ready operations and explicit trade-offs. We integrate pattern matching for type-safe hierarchies, virtual threads for concurrency previews where applicable, and complexity analysis for every algorithm.

Linked lists offer dynamic memory allocation, contrasting with arrays’ contiguous storage covered in sibling sections like CH2-S1 on arrays and strings. Stacks and queues, as abstract data types, enforce last-in-first-out (LIFO) and first-in-first-out (FIFO) semantics, respectively, with deques extending this to bidirectional operations. By mastering these structures, readers can implement solutions for problems like valid parentheses or cycle detection, and prepare for system design tasks like LRU caches.

Linked Lists: Singly and Doubly Linked Implementations

A singly linked list is a linear data structure where each node contains data and a reference to the next node, allowing sequential traversal from head to tail. Conversely, a doubly linked list includes references to both next and previous nodes, enabling bidirectional traversal and O(1) deletion given a node reference. In Java, these structures are often implemented using custom node classes, with generics for type safety and Records for immutable data carriers when applicable.

The foundational unit is the Node, a basic unit containing data and references. Using Java Records, we can define an immutable node variant, but for mutability required in many interview problems, a standard class suffices. Here is a mutable Node class for singly linked lists, with generics and explicit complexity analysis:

// Node class for singly linked list with generics, using standard class for mutability
public class Node<T> {
    public T data;
    public Node<T> next;
    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}

This Node class supports operations like insertion and deletion, with time complexities depending on position: insertion at the head is O(1), while deletion without a previous pointer reference can be O(n) to locate the prior node. For doubly linked lists, similar classes include prev references, enabling O(1) deletions given a node.

A critical operation is reversal, which can be performed iteratively with O(n) time and O(1) auxiliary space. The algorithm reverses pointers in-place, avoiding extra node allocation:

// Reversal of singly linked list iteratively
public static <T> Node<T> reverse(Node<T> head) {
    Node<T> prev = null, current = head, next = null;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev; // new head
}
// Time Complexity: O(n) where n is number of nodes, Space Complexity: O(1) extra space.

This code demonstrates pointer manipulation without recursion, adhering to logic constraints that reserve recursion for CH3-S2. Edge cases include null inputs, empty lists, or single-node lists, which the algorithm handles by returning null or the same head appropriately.

For cycle detection, Floyd’s Tortoise-Hare Algorithm uses two pointers moving at different speeds to identify cycles in O(n) time with O(1) auxiliary space. The correctness proof relies on the distance between pointers reducing by one each step within a cycle, ensuring meeting within the cycle. This algorithm is essential for preventing infinite loops in traversal, especially in graph-related problems.

Merging two sorted singly linked lists can be done in O(n + m) time using a dummy node and pointer adjustments, where n and m are the lengths. This operation leverages the linear traversal capabilities of linked lists, contrasting with arrays’ O(n log n) merge sorts due to random access limitations.

Stack and Queue Implementations with Modern Java

A Stack is a Last-In-First-Out (LIFO) data structure with core operations push (add element), pop (remove and return top element), and peek (view top element without removal). A Queue is a First-In-First-Out (FIFO) structure with enqueue (add to rear) and dequeue (remove from front). In Java, the Collections Framework provides efficient implementations, with ArrayDeque as a preferred choice for both stack and queue operations due to its resizable array backing and O(1) amortized operations.

Using ArrayDeque, we can implement a stack as follows, with explicit complexity notes:

// Stack implementation using ArrayDeque (preferred in Java)
import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample<T> {
    private final Deque<T> stack = new ArrayDeque<>();
    public void push(T item) { stack.push(item); } // O(1) amortized
    public T pop() { return stack.pop(); } // O(1)
    public T peek() { return stack.peek(); } // O(1)
    public boolean isEmpty() { return stack.isEmpty(); }
}
// Complexity: All operations O(1) amortized, Space: O(n) for n elements.

ArrayDeque is implemented as a circular array, providing efficient O(1) operations for addFirst, addLast, removeFirst, and removeLast, making it suitable for deque use. This contrasts with the legacy Stack class, which extends Vector and has synchronization overhead, and LinkedList, which has higher memory overhead.

For custom queue implementations, a circular buffer achieves O(1) enqueue and dequeue by maintaining front and rear indices that wrap around. Here is a Java implementation with edge case handling:

// Queue implementation using circular buffer with array
public class CircularQueue<T> {
    private T[] array;
    private int front = 0, rear = 0, size = 0, capacity;
    @SuppressWarnings("unchecked")
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        array = (T[]) new Object[capacity];
    }
    public void enqueue(T item) {
        if (size == capacity) throw new IllegalStateException("Queue full");
        array[rear] = item;
        rear = (rear + 1) % capacity;
        size++;
    } // O(1)
    public T dequeue() {
        if (size == 0) throw new IllegalStateException("Queue empty");
        T item = array[front];
        array[front] = null; // aid GC
        front = (front + 1) % capacity;
        size--;
        return item;
    } // O(1)
    public T peek() { return array[front]; } // O(1)
}
// Time Complexity: O(1) for enqueue/dequeue/peek, Space Complexity: O(capacity).

This circular buffer approach minimizes memory overhead compared to linked list-based queues, as discussed in memory diagrams.

Complexity and Trade-off Analysis

To aid in rapid selection between data structures, we present a complexity table comparing key operations, derived from primary materials:

Data Structure	Access (Random)	Insertion (End)	Deletion (End)	Space Overhead
ArrayList	O(1)	O(1) amortized	O(1) amortized	Low, contiguous array
LinkedList	O(n)	O(1)	O(1)	High, per-node object overhead
Stack (ArrayDeque)	O(1) peek	O(1) push	O(1) pop	O(n)
Queue (Circular Buffer)	O(1) peek	O(1) enqueue	O(1) dequeue	O(n)
Deque (ArrayDeque)	O(1) peekFirst/Last	O(1) addFirst/Last	O(1) removeFirst/Last	O(n)

Memory overhead differences are critical: LinkedList nodes in Java consist of an object header (approx. 12-16 bytes), data field (depends on type), and pointers (next and possibly prev, each 4-8 bytes). This leads to higher per-element memory usage (e.g., ~24-40 bytes per node) compared to ArrayList’s contiguous array storage (e.g., ~4 bytes per reference plus array overhead). ArrayDeque uses a circular array with similar overhead to ArrayList but may have unused capacity.

Trade-offs must be explicitly stated. For instance, ArrayList provides fast random access at the cost of slower middle insertions/deletions, while LinkedList offers fast insertions/deletions but slow random access. Here is a trade-off matrix:

Feature	ArrayList	LinkedList	Trade-off Statement
Random Access	Fast (O(1))	Slow (O(n))	ArrayList provides fast access at the cost of slower middle insertions/deletions.
Insertion/Deletion at Ends	Fast (O(1) amortized)	Fast (O(1))	Both are efficient, but LinkedList has no resizing overhead.
Memory Usage	Contiguous, cache-friendly	Dispersed, higher overhead	ArrayList is more memory-efficient for large datasets.
Use Case	Frequent access, fixed size	Frequent insertions/deletions, dynamic size	Choose based on operation frequency.

Stack-Based Problem Solving

Stack data structures excel in problems requiring nested or matching patterns. For example, the valid parentheses problem can be solved using a stack to match opening and closing brackets in O(n) time and O(n) space in the worst case. Similarly, evaluating reverse Polish notation (RPN) involves using a stack to process operators and operands, with O(n) time complexity where n is the number of tokens.

Implementing a queue with two stacks can achieve amortized O(1) enqueue and dequeue by using one stack for input and another for output, with lazy transfer. This demonstrates the flexibility of stacks in simulating other structures.

LinkedHashMap for LRU Cache Skeletons

LinkedHashMap is a HashMap in Java that maintains a doubly linked list of entries, preserving insertion order for iteration. It is useful for implementing LRU cache skeletons without full eviction logic, as detailed eviction is reserved for CH7-S2. By default, LinkedHashMap preserves insertion order (access-order set to false), and it can be extended to override removeEldestEntry for basic eviction. This provides a preview for cache implementations, aligning with the node goal of coding an LRU cache skeleton in 5 minutes.

Failure Modes and Interview Strategies

Common failure modes in linked list and stack/queue interviews must be addressed to avoid errors:

1. Not handling null or empty input (e.g., head == null).
2. Incorrect pointer manipulation in reversal or deletion (off-by-one errors).
3. Forgetting to check for cycles in traversal algorithms.
4. Misstating time or space complexity (e.g., O(n^2) for simple traversal).
5. Stack underflow/overflow without validation (e.g., pop on empty stack).
6. Using String concatenation in loops for output, leading to O(n^2) time.
7. Ignoring memory overhead differences between data structures.
8. Not testing edge cases like single-element lists or full/empty queues.

A structured interview pattern template guides problem-solving:

1. Understand the problem: Clarify inputs, outputs, and constraints (e.g., time/space limits).
2. Choose data structure: Select based on required operations (e.g., LinkedList for O(1) insertions, ArrayDeque for stack/queue).
3. Plan algorithm: Outline steps with pseudocode, then translate to Java 21+ using features like Records if applicable.
4. Implement: Write compilable code with clear variable names, include complexity analysis in comments.
5. Test edge cases: Check null, empty, single element, cycles, and boundary conditions.
6. Verify and optimize: Re-evaluate time/space complexity, consider alternative implementations if needed.

Summary and Verification Exercise

This section equips readers to implement linked list operations, select appropriate Collection types for stacks and queues, and solve stack-based problems. Trade-offs between ArrayList and LinkedList, or ArrayDeque and LinkedList, are explicitly stated to inform rapid decisions. As a verification exercise, implement an LRU cache skeleton using LinkedHashMap in Java 21+, leveraging its order-preserving properties for basic eviction previews. Ensure all code adheres to modern Java features, with complexity analysis and edge case handling integrated throughout.

By mastering these linear structures, readers build on prerequisite knowledge from CH2 and CH2-S1, preparing for advanced topics in subsequent chapters while avoiding scope creep into concurrent queues or priority queues as per logic constraints.