AlgoMaster Logo

Design Linked List

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

This is a design problem where we need to build a linked list from scratch. Unlike most LeetCode problems that ask for a single algorithm, this one requires implementing a full data structure with multiple operations that all need to work together correctly.

Each operation in isolation is straightforward. The difficulty comes from keeping everything consistent: you need a reliable way to track the size of the list, navigate to the right position, and handle edge cases like inserting at the head, tail, or an invalid index. A single off-by-one error in your traversal will break multiple operations at once.

The main design choice is whether to use a singly linked list or a doubly linked list. A singly linked list is simpler to implement but makes some operations slower. A doubly linked list adds complexity with prev pointers but makes operations at both ends efficient.

Key Constraints:

  • 0 <= index, val <= 1000 → Indices and values are small non-negative integers. No need to handle negative indices or integer overflow.
  • At most 2000 calls → The list never holds more than 2000 nodes, so even O(n) per operation costs at most 2000 x 2000 = 4 million pointer steps in total. No need for amortized or O(1) per-operation guarantees.
  • No built-in LinkedList library → We must implement the node structure and all pointer manipulations ourselves.

Approach 1: Singly Linked List

Intuition

A singly linked list is the simpler of the two structures. Each node holds a value and a pointer to the next node, and we maintain a size counter so we can validate indices without traversing the entire list.

We also use a sentinel (dummy) head node that sits before the actual first element and never gets removed. Without it, inserting or deleting at position 0 needs separate logic to reassign the head pointer. With it, the real head is always sentinel.next and every real node has a predecessor, so insertion and deletion treat position 0 the same as any other position. This collapses addAtHead and addAtTail into one-line calls to addAtIndex.

Algorithm

For each operation:

  1. get(index): Validate 0 <= index < size. Start at sentinel.next and walk index steps forward. Return that node's value.
  2. addAtHead(val): Call addAtIndex(0, val).
  3. addAtTail(val): Call addAtIndex(size, val).
  4. addAtIndex(index, val): Validate 0 <= index <= size (index == size appends). Walk from sentinel exactly index steps to find the predecessor. Insert the new node after the predecessor. Increment size.
  5. deleteAtIndex(index): Validate 0 <= index < size. Walk from sentinel exactly index steps to find the predecessor. Set pred.next = pred.next.next to skip the target node. Decrement size.

Example Walkthrough

1Initialize: sentinel -> null, size=0
[S]
1/9

Code

In a singly linked list, every operation near the tail pays a full traversal from the head, including every addAtTail. The second approach adds backward pointers so the list can be entered from either end.

Approach 2: Doubly Linked List

Intuition

A doubly linked list gives each node both a next and a prev pointer, so the list can be walked in either direction. Operations at the tail no longer require a traversal, and operations in the second half of the list can start from the tail instead of the head.

This time we use two sentinel nodes, one at the head and one at the tail. The sentinels never hold real data and never get removed, and every real node sits between them. Each real node therefore has both a predecessor and a successor, so insertion and deletion never need null checks or head/tail special cases.

With two sentinels:

  • addAtHead inserts between headSentinel and headSentinel.next in O(1).
  • addAtTail inserts between tailSentinel.prev and tailSentinel in O(1).
  • For addAtIndex and deleteAtIndex, we traverse from whichever end is closer, cutting the average traversal in half.

Algorithm

  1. Initialization: Create headSentinel and tailSentinel. Point headSentinel.next to tailSentinel and tailSentinel.prev to headSentinel. Set size = 0.
  2. get(index): Validate the index. If index < size / 2, traverse from the head. Otherwise, traverse from the tail.
  3. addAtHead(val): Insert between headSentinel and headSentinel.next. O(1).
  4. addAtTail(val): Insert between tailSentinel.prev and tailSentinel. O(1).
  5. addAtIndex(index, val): Validate 0 <= index <= size. If index == size, the successor is tailSentinel; otherwise find the node at position index. Insert a new node between successor.prev and successor.
  6. deleteAtIndex(index): Validate 0 <= index < size. Find the node at position index. Rewire node.prev.next and node.next.prev to skip it.

Example Walkthrough

1Initialize: headSentinel <-> tailSentinel, size=0
[HS, TS]
1/9

Code