Design Linked List
Build your own linked list from scratch (no built-in list library) supporting six operations. get(index) returns the value of the node at position index (0-indexed), or -1 if the index is invalid. addAtHead(val) inserts a node at the front. addAtTail(val) appends a node at the end. addAtIndex(index, val) inserts before the node currently at index; if index equals the list's length it appends at the tail, if index is greater than the length it does nothing, and if index is negative it inserts at the head. deleteAtIndex(index) removes the node at index if the index is valid.
- 0 <= index, val <= 1000
- Do not use the built-in linked-list library
- At most 2000 calls will be made across all operations
addAtHead(1), addAtTail(3), addAtIndex(1,2), get(1), deleteAtIndex(1), get(1)null, null, null, 2, null, 3addAtHead(7), get(1), addAtIndex(5,9), get(0)null, -1, null, 7Before writing a line of code, picture what we are actually building. A linked list stores a sequence of values, but — unlike an array — it does not keep them in one solid contiguous block of memory. Instead each value lives in its own little container called a node, and every node holds two things: the value itself, and a pointer — the memory address of the next node in the line. The list itself is just a single pointer called head, aimed at the first node; follow the pointers from node to node and you visit the whole sequence, until you reach a node whose pointer is null, which marks the end.
The whole reason this structure earns its place is a single trade. In an array, the values sit shoulder to shoulder in memory, so jumping to position 500 is instant — the computer computes exactly where it is. But inserting a value in the middle is painful: to make room, every element after the insertion point must physically slide over one slot. Insert near the front of a million-element array and you shift a million values. A linked list flips this. There is no sliding — to splice a node into the middle you only change two pointers. The price you pay for that cheap splicing is that you lose instant addressing: to reach position k you must start at head and follow the pointer chain k times, one hop at a time. So "designing" a linked list is really about handling those pointer rewirings correctly, and the tricky part is always the edges.
Watch what goes wrong at the front of the list. To delete the node at some position, the natural move is: find the node just before it, and point that predecessor's next past the doomed node. To insert, same idea — find the predecessor and rewire it. This works beautifully everywhere except one spot: the very first node has nothing before it. It has no predecessor to rewire; the only thing pointing at it is head itself. So a naive implementation ends up with a special if branch for "am I touching the head?" in every add and delete method — extra code, and exactly where the subtle bugs hide.
Give every real node a predecessor by planting a permanent fake node in front of the list — a dummy (or sentinel) node that holds no real data and never moves. head no longer points at the first real value; it points at the dummy, and the dummy points at the first real value. Now the first real node has a predecessor just like everyone else — the dummy — so the head is no longer a special case. One piece of logic handles every position. This is the single most useful trick in linked-list code, and it costs one wasted node.
To insert at position index, walk from the dummy exactly index steps to land on the predecessor — the node the new one should sit after — then perform the two-pointer splice:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class MyLinkedList:
def __init__(self):
self.dummy = Node(0) # fake node; the real list starts at dummy.next
self.size = 0
def add_at_index(self, index, val):
if index > self.size: # past the end: do nothing
return
if index < 0: # negative: clamp to the head
index = 0
prev = self.dummy
for _ in range(index): # walk to the node BEFORE the target slot
prev = prev.next
node = Node(val)
node.next = prev.next # (1) new node points to the old successor
prev.next = node # (2) predecessor now points to the new node
self.size += 1prev.next (the old successor) and saves it inside the new node first; only then does line (2) overwrite prev.next. Swap them and you overwrite prev.next before you've saved it — the old rest of the list is lost, and you've silently truncated everything after the insertion point. Deletion is the mirror image: walk to the predecessor and set prev.next = prev.next.next, snipping the target out of the chain in one move.dummy -> null, size 0.addAtHead(1) → walk 0 steps, splice after dummy: dummy -> 1 -> null, size 1.addAtTail(3) → the tail is index == size, so this is addAtIndex(1, 3): dummy -> 1 -> 3 -> null, size 2.addAtIndex(1, 2) → walk 1 step to the node holding 1 (the predecessor), splice: dummy -> 1 -> 2 -> 3 -> null, size 3.get(1) → walk 1 step past the dummy to reach position 1, which holds 2.get(9) (the non-happy path) → 9 is past the end. We never walk off into null and crash; we check index >= size up front and return -1.deleteAtIndex(1) → walk to predecessor (node 1), set its next to skip node 2: dummy -> 1 -> 3 -> null. Now get(1) returns 3.Reaching a position costs O(index) hops because there is no shortcut through the chain, while the actual insert or delete — once you're standing on the predecessor — is O(1), just a couple of pointer swaps. That is the linked list's whole personality: slow to find a spot, instant to edit once you're there. Train the reflex: reach for a linked list whenever the job is heavy on splicing in the middle and light on random indexing, and reach for the dummy-node trick the instant you notice the head turning into a special case. That exact combination returns later, doubled up as a dummy head and tail, when we build the LRU Cache — the sentinels are what make its constant-time evictions clean.
The Sentinel Architecture
dummy -> 1 -> 3