Linked Lists, Stacks, and Queues Questions

Approach & Time Complexity

• Array -> singly linked list: O(n) time to allocate nodes and copy or move values; O(1) per element.
• Linked list -> array: O(n) to allocate contiguous buffer and traverse list to copy values.
• In-place conversion without copying is generally impossible without changing representation or using pointer arithmetic, so expect O(n) work.

Memory Overhead

• Arrays: compact, one allocation for n elements, minimal per-element overhead.
• Singly linked list: O(n) extra memory for node pointers (next) plus allocator overhead and fragmentation.
• Converting temporarily increases peak memory (both structures exist) unless you reuse nodes.

Cache Behavior & Performance

• Arrays have excellent spatial locality: traversals are cache-friendly, vectorized, and faster per-element.
• Linked lists have poor locality; pointer chasing causes cache misses and branch mispredictions, much higher constant factors despite same O(n) complexity.

When Converting is Beneficial

• Streaming/producer-consumer where you build incrementally and need O(1) insert/remove at head: list useful; convert to array once batch is complete for fast random access or bulk processing.
• Adjacency lists where dynamic edge insertion/removal dominated: lists useful; convert to contiguous CSR-like arrays for fast graph algorithms/parallel scans.
• Free lists in allocators: singly linked free lists are ideal for constant-time allocation/deallocation; occasionally compacting into arrays reduces fragmentation.

When Harmful

• Frequent conversions (many toggles) cost O(n) each and memory churn; avoid if access patterns favor one representation.
• High-throughput numeric processing: converting to/from lists degrades performance due to pointer overhead and cache penalties.

Practical Guideline (Backend)

• Prefer arrays for read-heavy, bulk, and numeric work.
• Use lists for localized, constant-time insert/delete workloads or when allocator constraints demand it.
• Batch updates and convert once to exploit array locality; measure memory and CPU trade-offs in production.

Approach (brief)
Use two-pointer (fast/slow) with a dummy head so removal is easy in one pass. Advance fast n steps, then move both until fast reaches end; slow will be before the target. Validate n and handle edge cases (remove head, n=1, invalid n).

Code

// ListNode constructor provided
function ListNode(val) { this.val = val; this.next = null; }

function removeNthFromEnd(head, n) {
  if (!head || n <= 0) return null; // invalid n or empty list

  const dummy = new ListNode(0);
  dummy.next = head;
  let fast = dummy;
  let slow = dummy;

  // advance fast n steps
  for (let i = 0; i < n; i++) {
    fast = fast.next;
    if (!fast) {
      // n is larger than list length -> invalid
      return null;
    }
  }

  // move both until fast is at last node
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }

  // slow.next is the node to remove
  const removed = slow.next;
  slow.next = removed ? removed.next : null;

  // return removed node (detached) and new head if needed
  return removed;
}

Explanation & Edge Cases

• dummy handles removing head when n equals list length.
• n = 1 removes tail: fast advances 1 and traversal places slow before last.
• invalid n (<=0 or > length) returns null.
• Function returns the removed node (caller can check new head via dummy.next).

Complexity

• Time: O(L) single pass
• Space: O(1)

Notes

• In backend code, ensure callers update stored head when removed node was head (use returned dummy.next or manage head externally).

Approach (brief)
Iteratively walk the list, reversing pointers one node at a time by keeping track of previous, current, and next. This is in-place, O(n) time and O(1) extra space. Empty and single-node lists are naturally handled: loop won't run and we return head.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    # prev will become the new head
    prev = None
    curr = head
    while curr:
        nxt = curr.next      # save next
        curr.next = prev     # reverse pointer
        prev = curr          # advance prev
        curr = nxt           # advance curr
    return prev              # prev is new head (None if original was empty)

Explanation & reasoning

• Start with prev=None and curr=head. For each node, redirect curr.next to prev, then move prev and curr forward.
• For empty list (head is None), loop doesn't run; returns None.
• For single-node, first iteration sets node.next=None and returns node as new head — effectively unchanged.

Complexity

• Time: O(n) single pass
• Space: O(1) extra (few pointers)

Notes / Alternatives

• Recursive solution exists but uses O(n) call stack — avoid for large lists in backend services.

Approach summary
For backend services handling large linked data, aim to reduce per-node overhead and maximize spatial locality so CPUs and caches work efficiently. Combine allocation strategies with compact layouts and consider workload patterns (read-heavy vs mutating).

Strategies

• Block allocation: allocate many nodes in contiguous slabs to reduce allocator overhead and improve locality. Free slab-wise to avoid fragmentation.
• Pooling: reuse nodes from a free-list to avoid frequent malloc/free pauses and reduce fragmentation; keep per-thread pools to avoid contention.
• Array-of-Structs (AoS): store nodes consecutively when node size is small and nodes are traversed as whole records — good cache behavior for typical traversals.
• Struct-of-Arrays (SoA): separate fields into parallel arrays when only a subset of fields is hot (e.g., next-index and key), improving vectorized access and cache utilization.
• Pointer compression/packed nodes: replace 64-bit pointers with 32-bit offsets or relative pointers when memory < 4GB or within slab — saves space and cache lines.
• Packed nodes: pack flags/lengths into bitfields and align to cache-line boundaries; avoid pointer chasing across cache lines.

Trade-offs

• Pointer-based lists: cheap inserts/removals, flexible topology; poor cache locality and higher memory per node.
• Contiguous arrays / CSR-like: excellent cache locality and lower memory, great for read-heavy or mostly append workloads; expensive for random inserts/deletes and requires relocation or indirection (stable IDs + free-list).
• Choose hybrid: use contiguous storage with stable integer IDs (index), maintain free-list for deletes, and rebuild/compact periodically.

Practical tips

• Measure with benchmarks and perf tools (cache-misses, branch-mispredicts).
• Use per-thread arenas, jemalloc, or tcmalloc; prefer 32-bit offsets in slabs; prefer SoA for analytics-heavy fields.

Approach (brief)
Create two sublists: "less" and "greaterOrEqual". Iterate once, appending nodes to appropriate tail while reusing nodes (O(1) extra space). Preserve relative order by always appending to tail. Finally link less tail to greater head and terminate list.

Code (Java)

class ListNode {
    int val;
    ListNode next;
    ListNode(int v){ val = v; }
}

public ListNode partition(ListNode head, int x) {
    if (head == null) return null;
    ListNode lessHead = null, lessTail = null;
    ListNode geHead = null, geTail = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next; // detach safely
        cur.next = null;
        if (cur.val < x) {
            if (lessHead == null) lessHead = lessTail = cur;
            else { lessTail.next = cur; lessTail = cur; }
        } else {
            if (geHead == null) geHead = geTail = cur;
            else { geTail.next = cur; geTail = cur; }
        }
        cur = next;
    }
    if (lessTail != null) {
        lessTail.next = geHead;
        return lessHead;
    } else {
        return geHead;
    }
}

Explanation & Complexity

• Single pass, stable because nodes appended to tails in original order.
• Time: O(n). Space: O(1) extra (only constant pointers).
• Edge cases: all nodes < x, all >= x, empty list, duplicates.