Design Linked List (Implementation)

Overview

Design linked list means implementing a linked list that supports: get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val), deleteAtIndex(index). Index is 0-based. This exercise ties together Dummy Head, pointer updates, and careful handling of edge cases (empty list, single node, insert/delete at head/tail, invalid index). Use a sentinel (dummy) node so the head is always "dummy.next" and operations at index 0 are consistent with others.

Key idea: With a dummy, "add at head" is addAtIndex(0, val). Maintain a size so you can validate index in O(1) and avoid traversing to count. For get/add/delete at index, traverse from dummy (or head) to the node before the target position so you can rewire next pointers.

When to Use

• Implement a full linked list API — Interview or design problem.
• Practice pointer discipline — All the patterns (dummy, prev, size) in one place.

How It Works

1. Node: val, next. List: dummy head (sentinel), optional size.
2. get(index): If index < 0 or index >= size return -1. Traverse from dummy.next, index steps; return node.val.
3. addAtHead(val): addAtIndex(0, val).
4. addAtTail(val): addAtIndex(size, val).
5. addAtIndex(index, val): If index > size return. If index < 0 treat as 0. Find the node prev at position index - 1 (start from dummy so index 0 means prev = dummy). Create newNode, newNode.next = prev.next, prev.next = newNode, size++.
6. deleteAtIndex(index): If index < 0 or index >= size return. Find prev at position index - 1; set prev.next = prev.next.next; size--.

Example 1: Singly Linked List with Dummy

Problem: Implement the MyLinkedList class with get, addAtHead, addAtTail, addAtIndex, deleteAtIndex (0-based index).

class ListNode {
  val: number; next: ListNode | null;
  constructor(val: number) { this.val = val; this.next = null; }
}
class MyLinkedList {
  private dummy = new ListNode(-1);
  private size = 0;
  get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let curr = this.dummy.next;
    for (let i = 0; i < index; i++) curr = curr!.next;
    return curr!.val;
  }
  addAtHead(val: number): void { this.addAtIndex(0, val); }
  addAtTail(val: number): void { this.addAtIndex(this.size, val); }
  addAtIndex(index: number, val: number): void {
    if (index > this.size) return;
    if (index < 0) index = 0;
    let prev = this.dummy;
    for (let i = 0; i < index; i++) prev = prev.next!;
    const node = new ListNode(val);
    node.next = prev.next;
    prev.next = node;
    this.size++;
  }
  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    let prev = this.dummy;
    for (let i = 0; i < index; i++) prev = prev.next!;
    prev.next = prev.next!.next;
    this.size--;
  }
}

• Time: get/add/delete at index: O(index); addAtHead O(1); addAtTail O(n) unless you keep a tail pointer. Space: O(1) per operation.

Optional: Tail Pointer

To make addAtTail O(1), maintain a tail reference. Update tail when adding at tail or when the last node changes (e.g. delete the last node—then tail must be updated by traversing from dummy to find the new last node, or maintain prev in delete).

Edge Cases

• Empty list — size = 0; get/delete invalid index; addAtHead/addAtTail work via addAtIndex.
• addAtIndex(0) — prev = dummy; correct.
• deleteAtIndex(0) — prev = dummy; dummy.next = head.next; correct.
• Invalid index — get: return -1; addAtIndex: return if index > size; deleteAtIndex: return if index invalid.

Common Mistakes

1. Off-by-one — addAtIndex(index, val) inserts at index, so the new node should be after the node at index - 1; prev must be at index - 1 (so index 0 → prev = dummy).
2. Forgetting size — Increment on add, decrement on delete; use for bounds checking.
3. Not using dummy — Without it, addAtHead and deleteAtIndex(0) need special cases.

Time and Space Complexity

• get(index): O(index). addAtHead: O(1). addAtTail: O(n) without tail; O(1) with tail. addAtIndex/deleteAtIndex: O(index).
• Space: O(1) per node plus dummy.

Summary

• Design linked list: Dummy head + size; addAtIndex(0) for head, addAtIndex(size) for tail; find prev at index - 1 for add/delete; validate index with size.
• Uses Dummy Head. Optional: Doubly Linked List for O(1) delete at tail if you store tail.