Design linked list

Implement MyLinkedList with get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val) and deleteAtIndex(index). Indexes are 0-based; invalid indexes return -1 from get and are ignored by the other operations.

Before you code

Every method needs "the node before position i". If you write one helper that returns it, the rest are a few lines each. The head is the only position without a node before it, unless you give it one.

Hints

1. Keep a dummy head node and a size counter. Then addAtHead is addAtIndex(0, ...) and addAtTail is addAtIndex(size, ...).
2. To reach the node before index i, start at the dummy and follow next i times.
3. Validate the index against size before walking: 0 <= i <= size for adding, 0 <= i < size for get and delete.
4. Variant: make it doubly linked with a tail pointer, so that addAtTail is O(1).

Production & complexity notes

When solving Design linked list on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Nodes and pointers to reinforce the underlying pattern.

What it practices

Building a list from nodes and next pointers, from Nodes and pointers, and the dummy head from the next lesson.