Linked Lists, Stacks, and Queues Questions

Approach: use unique_ptr for owning "next" links and raw non-owning "prev" pointers (or better: observe-only raw pointers). This ensures single ownership of each node and automatic cleanup. Implement methods to push_front, insert_after, and remove a node safely.

#include <memory>
#include <iostream>

template<typename T>
class DoublyLinkedList {
    struct Node {
        T value;
        std::unique_ptr<Node> next; // owns next node
        Node* prev = nullptr;       // non-owning back pointer

        Node(const T& v) : value(v) {}
        Node(T&& v) : value(std::move(v)) {}
    };

    std::unique_ptr<Node> head;
    Node* tail = nullptr; // raw pointer to last node for O(1) push_back

public:
    DoublyLinkedList() = default;
    ~DoublyLinkedList() = default; // unique_ptr chain cleans up

    // push_front: make new head
    void push_front(const T& val) {
        auto node = std::make_unique<Node>(val);
        if (head) {
            head->prev = node.get();
            node->next = std::move(head);
        } else {
            tail = node.get();
        }
        head = std::move(node);
    }

    // push_back: append at tail
    void push_back(const T& val) {
        auto node = std::make_unique<Node>(val);
        node->prev = tail;
        if (tail) {
            tail->next = std::move(node);
            tail = tail->next.get();
        } else {
            head = std::move(node);
            tail = head.get();
        }
    }

    // Insert after a given node pointer (must belong to this list)
    Node* insert_after(Node* pos, const T& val) {
        if (!pos) { push_front(val); return head.get(); }
        auto node = std::make_unique<Node>(val);
        node->prev = pos;
        node->next = std::move(pos->next);
        if (node->next) node->next->prev = node.get();
        else tail = node.get();
        pos->next = std::move(node);
        return pos->next.get();
    }

    // Remove a node pointer; returns pointer to next node (or nullptr)
    Node* remove(Node* node) {
        if (!node) return nullptr;
        Node* next = node->next.get();

        if (node->prev) {
            // node is not head: previous owns node via its next unique_ptr
            node->prev->next = std::move(node->next);
            if (node->prev->next) node->prev->next->prev = node->prev;
            else tail = node->prev;
        } else {
            // node is head: head owns node
            head = std::move(node->next);
            if (head) head->prev = nullptr;
            else tail = nullptr;
        }
        // node unique_ptr is destroyed here (ownership transferred), memory freed
        return next;
    }

    // For external iteration/accessors:
    Node* first() const { return head.get(); }
    Node* last() const { return tail; }
};

Key points:

• unique_ptr forms a singly-owned chain; deleting head recursively destroys the list via RAII.
• prev uses raw pointer to avoid cyclic ownership (unique_ptr + shared_ptr would risk cycles).
• remove transfers unique_ptrs so ownership updates correctly; no leaks or dangling owning pointers remain.
  Time complexity: push_front/push_back/insert_after/remove are O(1). Space: O(n) for n nodes.
  Edge cases: removing head or tail, inserting after tail or into empty list — handled. Alternatives: use shared_ptr + weak_ptr for prev to allow multiple external references, at cost of overhead.

Traversal performance is dominated by CPU cache locality and branch/prefetch behavior. Arrays store elements contiguously, so sequential scans have high spatial locality: a single cache line fetch (typically 64 B) brings multiple elements, hardware prefetchers detect the stride and hide memory latency. Result: near-memory-bandwidth traversal with few cache misses.

Linked lists store nodes scattered in memory; each step is a pointer-chase (load next pointer → load node). Pointer-chasing has poor spatial locality and defeats stride-based prefetchers because the next address is only known after dereference, causing many cache misses and pipeline stalls. On modern CPUs, misses cost hundreds of cycles; out-of-order/ speculative execution helps only if independent work exists.

Practical techniques to improve locality:

• Node pooling / slab allocation: allocate many nodes from one contiguous slab so neighbors in logical order are near in memory, reducing misses.
• Cache-line aligned nodes & packing: size nodes so useful data fits within a cache line, avoid padding that wastes space; align slabs to cache-line boundaries.
• Array-of-structures → structure-of-arrays: for operations touching one field across nodes (e.g., keys), SoA improves spatial locality for that field.
• Software prefetching: issue prefetch for next pointers several iterations ahead to hide latency (use carefully; tuning required).
• Batching and blocked traversal: process nodes in blocks that fit in caches; convert linked lists to temporary arrays for bulk processing.
• Memory compaction / defragmentation: periodically compact list into contiguous buffer when locality matters.

Trade-offs: these techniques add complexity, reduce allocator generality, or increase memory use, but can make pointer-based data structures approach array-like performance in practice.

To solve this, we need O(1) push/pop/top/getMin. Two common approaches:

Approach 1 — Auxiliary stack of minimums

1. Maintain main stack for values and a min_stack that stores current minima. On push(x) push x to main; push x to min_stack if min_stack is empty or x <= min_stack[-1]. On pop(), pop main; if popped == min_stack[-1], pop min_stack. top() is main[-1]. getMin() is min_stack[-1].

class MinStackAux:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if not self.stack:
            raise IndexError("pop from empty stack")
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        if not self.stack:
            raise IndexError("top from empty stack")
        return self.stack[-1]

    def getMin(self) -> int:
        if not self.min_stack:
            raise IndexError("min from empty stack")
        return self.min_stack[-1]

Key points:

• Time: O(1) each operation.
• Space: O(n) worst-case; min_stack may hold up to n elements.
• Duplicates: Using <= on push and equality on pop preserves duplicates (multiple equal minima stored).

Approach 2 — Value encoding trick (store deltas)
2. Store only encoded values so min can be tracked in one stack and one variable current_min. On push(x):

• If stack empty: push x, set current_min = x.
• Else if x >= current_min: push x.
• Else (x < current_min): push 2x - current_min (an encoded value) and set current_min = x.
  On pop(): if popped >= current_min -> normal pop; else popped is encoded, recover previous_min = 2current_min - popped, set current_min = previous_min.
  top(): if top >= current_min return top, else return current_min.

class MinStackEncoded:
    def __init__(self):
        self.stack = []
        self.min_val = None

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(x)
            self.min_val = x
        elif x >= self.min_val:
            self.stack.append(x)
        else:
            # store encoded value and update min
            self.stack.append(2*x - self.min_val)
            self.min_val = x

    def pop(self) -> None:
        if not self.stack:
            raise IndexError("pop from empty stack")
        top = self.stack.pop()
        if top < self.min_val:
            # encoded: recover previous min
            self.min_val = 2*self.min_val - top
        if not self.stack:
            # stack empty -> reset min_val
            self.min_val = None

    def top(self) -> int:
        if not self.stack:
            raise IndexError("top from empty stack")
        top = self.stack[-1]
        return top if top >= self.min_val else self.min_val

    def getMin(self) -> int:
        if self.min_val is None:
            raise IndexError("min from empty stack")
        return self.min_val

Key points and trade-offs:

• Time: O(1) each.
• Space: O(n) for encoded approach but only one stack used; auxiliary approach uses up to 2n storage worst-case.
• Duplicates: Encoded trick handles duplicates implicitly (values >= min are stored normally). When pushing a new smaller value equal to current_min, encoding uses the <= or < logic—use strict < to avoid unnecessary encoding when equal; both methods should carefully handle equality to preserve correct pop behavior.
• Edge cases: empty operations should raise errors; ensure resetting min when stack becomes empty.

Which to choose:

• Auxiliary stack: simpler, clearer, easier to maintain and reason about.
• Encoded trick: saves memory in some cases (only one stack), but is trickier and more error-prone; use only when memory constant factors matter.

A naive recursive reverse(node) that does:

• if node==null or node.next==null return node
• newHead = reverse(node.next)
• node.next.next = node
• node.next = null
• return newHead

uses O(n) stack space because each recursive call pushes a stack frame that must remain until the deeper call returns — so for a list of length n you get ≈ n frames (local variables + return address). That leads to stack overflow for very long lists.

Tail recursion vs iterative:

• A tail-recursive function is one where the recursive call is the last action; a compiler/runtime can convert it into a loop (tail-call optimization, TCO), making stack usage O(1).
• Example tail-recursive reverse (conceptually):
  reverse(curr, prev):
  if curr==null return prev
  next = curr.next
  curr.next = prev
  return reverse(next, curr)
  With TCO this is O(1) stack; without TCO it's still O(n).

Practical techniques in Java/C++ (no reliable TCO):

1. Convert to iterative algorithm (recommended): O(1) heap and stack.

// iterative in Java
ListNode reverse(ListNode head) {
  ListNode prev = null;
  ListNode curr = head;
  while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

2. Use an explicit heap-allocated stack/queue only if you need recursion semantics — but that uses O(n) heap instead of stack and avoids stack overflow.
3. Use tail-recursive style + trampolining (functional pattern) to simulate TCO — extra complexity and overhead; rare in imperative code.
4. Process in chunks: split long lists into segments, reverse each segment iteratively, then reconnect — useful if you must limit memory or recursion depth while doing other per-node work.
5. Increase stack size only as last resort (JVM flags or linker flags) — fragile and platform-dependent.

Conclusion: For production Java/C++ code, convert the recursive algorithm to an iterative pointer-reversal loop (constant stack) — simplest, fastest, and most robust against stack overflow.

Push on a dynamic array (stack) with doubling:

• Approach: Start with capacity C. When push finds the array full, allocate a new array of size 2C and copy C elements, then push the new element.
• Worst-case cost: O(n) for a single push (the copy).
• Amortized argument (intuitive): Over a sequence of n pushes starting from empty, resizing happens rarely: capacities go 1,2,4,8,... Each element gets copied at most O(1) times across all resizes. Aggregate cost of all copies ≤ 1 + 2 + 4 + ... + n = O(n). So total work for n pushes = O(n) (for actual pushes) + O(n) (for all copies) = O(n), hence amortized cost per push = O(1). Accounting method: charge each push a small extra “credit” (e.g., 2 units); credits pay for future copies.

Circular buffer queue:

• Fixed-size circular buffer: enqueue and dequeue are O(1) worst-case (just write/read and advance index modulo capacity). No resizing means no amortization needed.
• Dynamic circular buffer (doubling when full): same resizing argument as dynamic array—worst-case enqueue can be O(n) when resizing, but amortized across many enqueues is O(1).

Memory trade-offs and comparison:

• Doubling gives amortized O(1) time but can temporarily use up to ~2n space after a resize (wasted capacity up to 50%). That’s the trade-off: time efficiency vs. extra memory.
• Alternatives: increment-by-1 resizing reduces wasted memory but makes amortized cost O(n) per resize sequence (not amortized O(1)). Halving policy: shrink when size drops below 1/4 capacity to avoid thrashing; ensures space stays Θ(n) while preserving amortized O(1).
  Summary: Doubling yields occasional expensive operations but constant amortized cost — great practical choice when you want simple O(1) average performance with acceptable memory overhead.