Design Linked List
Problem
Design a singly linked list class supporting: get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val), deleteAtIndex(index).
addAtHead(1); addAtTail(3); addAtIndex(1, 2); get(1); deleteAtIndex(1); get(1);2, 3class MyLinkedList:
class Node:
__slots__ = ("val", "next")
def __init__(self, v=0, n=None): self.val = v; self.next = n
def __init__(self):
self.head = MyLinkedList.Node() # sentinel
self.size = 0
def get(self, index):
if index < 0 or index >= self.size: return -1
cur = self.head.next
for _ in range(index): cur = cur.next
return cur.val
def addAtIndex(self, index, val):
if index < 0 or index > self.size: return
prev = self.head
for _ in range(index): prev = prev.next
prev.next = MyLinkedList.Node(val, prev.next)
self.size += 1
def addAtHead(self, val): self.addAtIndex(0, val)
def addAtTail(self, val): self.addAtIndex(self.size, val)
def deleteAtIndex(self, index):
if index < 0 or index >= self.size: return
prev = self.head
for _ in range(index): prev = prev.next
prev.next = prev.next.next
self.size -= 1class MyLinkedList {
constructor() { this.head = { val: 0, next: null }; this.size = 0; }
get(i) {
if (i < 0 || i >= this.size) return -1;
let cur = this.head.next;
while (i--) cur = cur.next;
return cur.val;
}
addAtIndex(i, v) {
if (i < 0 || i > this.size) return;
let prev = this.head;
while (i--) prev = prev.next;
prev.next = { val: v, next: prev.next };
this.size++;
}
addAtHead(v) { this.addAtIndex(0, v); }
addAtTail(v) { this.addAtIndex(this.size, v); }
deleteAtIndex(i) {
if (i < 0 || i >= this.size) return;
let prev = this.head;
while (i--) prev = prev.next;
prev.next = prev.next.next;
this.size--;
}
}class MyLinkedList {
static class Node { int val; Node next; Node(int v, Node n) { val = v; next = n; } }
Node head = new Node(0, null); int size = 0;
public int get(int i) {
if (i < 0 || i >= size) return -1;
Node cur = head.next; while (i-- > 0) cur = cur.next;
return cur.val;
}
public void addAtIndex(int i, int v) {
if (i < 0 || i > size) return;
Node prev = head; while (i-- > 0) prev = prev.next;
prev.next = new Node(v, prev.next); size++;
}
public void addAtHead(int v) { addAtIndex(0, v); }
public void addAtTail(int v) { addAtIndex(size, v); }
public void deleteAtIndex(int i) {
if (i < 0 || i >= size) return;
Node prev = head; while (i-- > 0) prev = prev.next;
prev.next = prev.next.next; size--;
}
}class MyLinkedList {
struct Node { int val; Node* next; Node(int v, Node* n): val(v), next(n) {} };
Node* head = new Node(0, nullptr);
int sz = 0;
public:
int get(int i) {
if (i < 0 || i >= sz) return -1;
Node* cur = head->next; while (i--) cur = cur->next;
return cur->val;
}
void addAtIndex(int i, int v) {
if (i < 0 || i > sz) return;
Node* prev = head; while (i--) prev = prev->next;
prev->next = new Node(v, prev->next); sz++;
}
void addAtHead(int v) { addAtIndex(0, v); }
void addAtTail(int v) { addAtIndex(sz, v); }
void deleteAtIndex(int i) {
if (i < 0 || i >= sz) return;
Node* prev = head; while (i--) prev = prev->next;
Node* d = prev->next; prev->next = d->next; delete d; sz--;
}
};Explanation
This problem asks you to build a linked list class from scratch. The single idea that makes all five operations clean is a sentinel head — a dummy node that sits in front of the real first element and never holds real data.
Why a sentinel? Without it, adding or deleting at index 0 is a special case because there is no node "before" the first one. With a dummy node in front, every position has a node before it, so the same loop handles index 0 and the middle and the tail identically.
To reach a position we just walk forward. For addAtIndex we step prev forward index times, then splice a new node in with prev.next = Node(val, prev.next). For deleteAtIndex we walk the same way and skip a node with prev.next = prev.next.next. We keep a size counter so out-of-range requests can be rejected.
Notice how addAtHead and addAtTail are tiny: they just call addAtIndex(0, val) and addAtIndex(size, val). All the logic lives in one place.
Example: starting empty, addAtHead(1) then addAtTail(3) gives [1, 3]; addAtIndex(1, 2) inserts between them for [1, 2, 3]; get(1) returns 2. Deleting index 1 leaves [1, 3], so the next get(1) returns 3.