Community Problem

Design Linked List

Difficulty: Medium

Implement a singly-linked list class with index-based get / addAtHead / addAtTail / addAtIndex / deleteAtIndex, using a sentinel head and a size counter for O(1) bound checks.

Design Linked List

Implement a singly-linked list class with index-based get / addAtHead / addAtTail / addAtIndex / deleteAtIndex, using a sentinel head and a size counter for O(1) bound checks.

MEDIUM

Free

linked-list

data-structures

By @noranasser

February 23, 2026

Updated May 18, 2026

583 views

4.5 (10)

I assign this to candidates I'm prepping who haven't internalized the sentinel pattern. Five different methods, but ALL of them reduce to one helper: walk to the i-th prev (the predecessor of the target index). Once that helper exists, every method is two or three lines. Without it, you end up with a tangle of head-special-cases.

Design Linked List

Design a singly-linked list with the following operations. Indices are 0-based.

MyLinkedList() constructs an empty list.
int get(int index) returns the value of the index-th node. If the index is invalid (out of range), return -1.
void addAtHead(int val) adds a node of value val at the head.
void addAtTail(int val) adds a node of value val at the tail.
void addAtIndex(int index, int val) inserts a node of value val BEFORE the index-th node. If index equals the list size, the node is appended at the end. If index is greater than the list size, the operation is a no-op.
void deleteAtIndex(int index) deletes the index-th node if the index is valid; otherwise no-op.

Examples

Example 1:

Operations: addAtHead(1), addAtTail(3), addAtIndex(1, 2), get(1), deleteAtIndex(1), get(1)
Output: 2, then 3
Explanation: After addAtHead(1), list is [1]. After addAtTail(3), list is [1, 3]. After addAtIndex(1, 2), list is [1, 2, 3]. get(1) returns 2. After deleteAtIndex(1), list is [1, 3]. get(1) returns 3.

Example 2:

get(0) on an empty list returns -1.

Example 3:

addAtIndex(5, 99) on a list of size 3 is a no-op (5 > size).

Example 4:

addAtIndex(0, 7) on an empty list is the same as addAtHead(7).

Constraints

0 <= index, val <= 1000
At most 2000 calls in total across all methods.
It is guaranteed that the test driver will not call get, addAtIndex, deleteAtIndex with index < 0.

Follow-up

Which operations are O(1) and which are O(n)? With a SINGLY-linked list, addAtHead is O(1) if you keep a head pointer, and addAtTail becomes O(1) only if you also maintain a tail pointer. A doubly-linked list with both head and tail sentinels gets all the boundary operations down to O(1).

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach

The whole design collapses to one helper: "walk to the node BEFORE position index". A sentinel head makes this well-defined for index = 0 (the sentinel itself), so insertion and deletion never branch on the head. A size counter makes the bound checks O(1) instead of requiring a length walk.

Key insight

Once walkToPrev(index) exists, every public method is two or three lines:

get(i): bound-check, walk to prev, return prev.next.val.
addAtIndex(i, v): bound-check 0 <= i <= size, walk, splice a new node between prev and prev.next, increment size.
deleteAtIndex(i): bound-check 0 <= i < size, walk, set prev.next = prev.next.next, decrement size.
addAtHead(v): delegate to addAtIndex(0, v).
addAtTail(v): delegate to addAtIndex(size, v).

Algorithm (per method)

Text

walkToPrev(index):
  cur = sentinel
  for i in 0..index-1: cur = cur.next
  return cur

get(index):
  if index < 0 or index >= size: return -1
  return walkToPrev(index).next.val

addAtIndex(index, val):
  if index < 0 or index > size: return
  prev = walkToPrev(index)
  prev.next = new ListNode(val, prev.next)
  size += 1

deleteAtIndex(index):
  if index < 0 or index >= size: return
  prev = walkToPrev(index)
  prev.next = prev.next.next
  size -= 1

Complexity

Text

Method          Time   Space (per op)
--------------  -----  --------------
get             O(n)   O(1)
addAtHead       O(1)*  O(1)
addAtTail       O(n)   O(1)
addAtIndex      O(n)   O(1)
deleteAtIndex   O(n)   O(1)

*addAtHead delegates to addAtIndex(0, ...) which is a single hop from the sentinel.

With a singly-linked list and only a head sentinel, addAtTail is O(n) because we walk to the size-th prev. Maintaining a tail pointer drops it to O(1) (worth mentioning in the follow-up).

Why it works

The sentinel head guarantees there is always a prev pointer, even at the front of the list. The size counter is updated on every successful insert / delete, so all bound checks are constant-time and reject all out-of-range operations BEFORE any walking.

Pitfalls

The asymmetric bound check: addAtIndex accepts index <= size (allowing append), while get and deleteAtIndex reject index >= size. Mixing these up is the most common bug.
Walking PAST the target instead of TO its predecessor: the loop should run index times (i.e. for i in 0..index-1), so cur ends at the (index)-th prev. After index iterations from the sentinel, cur.next is the node at position index.
Forgetting to update size. Bound checks rely on it.
Sandpack for...of on Maps: not used here. Plain for loops on integers are fine.

Solution Code

All Problems