AlgoMaster Logo

Design Linked List

Last Updated: April 1, 2026

medium
4 min read

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.

The core challenge is not any single operation in isolation. Each one is straightforward. The real 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 key decision 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 non-negative integers. No need to handle negative indices or extremely large values.
  • At most 2000 calls → With only 2000 operations, even O(n) per operation is fine. The total work is at most 2000 x 1000 = 2 million operations. 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

The most natural starting point is a singly linked list. Each node holds a value and a pointer to the next node. We maintain a size counter so we can quickly validate indices without traversing the entire list.

One important trick: we use a sentinel (dummy) head node. This dummy node sits before the actual first element and never gets removed. Why bother? Because without it, every operation needs special-case logic for the head. With a sentinel, the real head is always sentinel.next, and every real node has a predecessor. This simplifies the code significantly.

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): Create a new node. Point it to sentinel.next. Point sentinel.next to the new node. Increment size.
  3. addAtTail(val): Walk from sentinel to the last node. Create a new node and attach it at the end. Increment size.
  4. addAtIndex(index, val): Validate 0 <= index <= size. 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. Skip the target node. Decrement size.

Example Walkthrough

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

Code

This approach works but every operation near the tail requires a full traversal.

What if we maintained backward pointers too, so we could traverse from whichever end is closer?

Approach 2: Doubly Linked List

Intuition

The singly linked list works, but every operation that targets a position near the end pays the full traversal cost. A doubly linked list fixes this by giving each node both a next and a prev pointer.

The big improvement: we use two sentinel nodes, one at the head and one at the tail. These sentinels never hold real data and never get removed. The real nodes always sit between the two sentinels. This eliminates all null-checking and 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): Find the successor node at position index. Insert a new node between successor.prev and successor.
  6. deleteAtIndex(index): 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