Design Linked List: Building addAtTail From head and size
Design a linked list from scratch — how head, tail, and size interact, why addAtTail walks the whole chain, JavaScript code, a walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most linked-list problems hand you a list and ask you to do something clever with it. Design Linked List flips that: you build the container. No Array.push, no language sugar — just a head pointer and the discipline to keep it consistent through every insert and delete.
The problem looks like busywork until you write addAtTail and realize you have no idea where the tail is. That single question — how do I reach the last node when I only remember the first? — is the whole lesson. It's where you feel, in your fingers, why a linked list gives up O(1) random access in exchange for O(1) splicing.
The problem
Implement a MyLinkedList class (singly linked) that supports these operations:
get(index)— return the value atindex, or-1if out of range.addAtHead(val)— prepend a node.addAtTail(val)— append a node.addAtIndex(index, val)— insert beforeindex.deleteAtIndex(index)— remove the node atindex.
The class stores only what a singly linked list actually needs: a head reference and a size counter. Everything else is derived by walking pointers. Here is a short sequence of calls and the list it produces:
new MyLinkedList() // head = null, size = 0 → (empty)
addAtTail(10) // head = null → attach → 10
addAtTail(20) // walk to 10, attach → 10 → 20
addAtTail(30) // walk to 10 → 20, attach → 10 → 20 → 30
get(1) → 20The interesting method is addAtTail, and the reason is buried in that "walk to" comment. Let's earn it.
The brute force baseline
A naive first instinct is to avoid pointers entirely and back the class with a plain array:
class MyLinkedList {
constructor() {
this.data = [];
}
addAtTail(val) {
this.data.push(val); // O(1) amortized — but this isn't a linked list
}
get(index) {
return index >= 0 && index < this.data.length ? this.data[index] : -1;
}
}This passes the tests, but it dodges the exercise. An array stores elements in one contiguous block, so push and index lookups are trivial. The point of Design Linked List is to model nodes scattered across the heap, each holding a value and a next pointer, connected only by references. Under those rules, appending is not free — because nothing tells you where the chain ends.
The key insight: only the head is free
A singly linked list remembers exactly one node: the head. Every other node is reachable only by starting at the head and following next pointers one hop at a time. There is no back door to the last node.
So addAtTail has two cases:
- The list is empty (
head === null). The new node simply becomes the head. No walk needed — O(1). - The list is non-empty. You must traverse from the head until
curr.nextis null, which identifies the current tail, then point that node'snextat your new node.
That traversal is the price of storing only a head. The classic optimization is to cache a tail pointer too, turning addAtTail into O(1) — but the base design the visualizer teaches keeps just head and size, so you see the O(n) walk happen explicitly. Understanding the slow version first is what makes the tail-pointer fix feel earned rather than memorized.
The optimal solution
This mirrors the algorithm in the Design Linked List visualizer exactly — a head/size class with a tail-walk addAtTail:
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class MyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
addAtTail(val) {
const newNode = new Node(val);
if (!this.head) { // empty list: new node is the head
this.head = newNode;
this.size++;
return;
}
let curr = this.head; // walk to the last node
while (curr.next) {
curr = curr.next;
}
curr.next = newNode; // splice the new node onto the tail
this.size++;
}
}Two lines carry the weight. while (curr.next) curr = curr.next is the O(n) tail search — it stops when curr is the node whose next is null. curr.next = newNode is the O(1) splice that actually appends. The insert is cheap; finding the insert point is the expensive part.
Walkthrough
Trace addAtTail(10), then addAtTail(20), then addAtTail(30) on a fresh list. The curr column shows which node the walk pointer sits on.
| Call | head empty? | curr walk | Pointer set | List after | hops |
|---|---|---|---|---|---|
| addAtTail(10) | yes | — | head = Node(10) | 10 | 0 |
| addAtTail(20) | no | curr = 10, curr.next null → stop | Node(10).next = Node(20) | 10 → 20 | 1 |
| addAtTail(30) | no | curr = 10 → curr.next=20 → curr=20, next null → stop | Node(20).next = Node(30) | 10 → 20 → 30 | 2 |
The hops column is the tell. The first insert costs 0 hops (empty-list shortcut), the second costs 1, the third costs 2. Append node number k and you pay k−1 hops. Summed over building an n-node list one append at a time, that's 0 + 1 + 2 + … + (n−1) = n(n−1)/2 total pointer dereferences — a triangular number, which is O(n²) work for a full build. That quadratic cost is precisely what a cached tail pointer eliminates.
Complexity
| Operation | Time | Space | Why |
|---|---|---|---|
| addAtTail (empty list) | O(1) | O(1) | new node becomes head, no walk |
| addAtTail (n nodes) | O(n) | O(1) | must traverse all n nodes to reach the tail |
| get(index) | O(index) | O(1) | walk index hops from head |
| Build n nodes via addAtTail | O(n²) | O(n) | triangular sum of tail walks; n nodes stored |
Every method's cost comes down to how far you have to walk. Only the head is a constant-time entry point; reaching anything else is linear in its distance from the head.
Common mistakes
- Forgetting the empty-list case. If
headis null and you jump straight intowhile (curr.next), you dereferencenull.nextand crash. Checkif (!this.head)first and let the new node become the head. - Walking one node too far. The loop condition is
while (curr.next), notwhile (curr). You want to stop on the last node so you can set itsnext— if the loop runs whilecurris truthy,currbecomes null andcurr.next = newNodethrows. - Not incrementing
size.get,addAtIndex, anddeleteAtIndexall bounds-check againstsize. Skip thethis.size++and every subsequent index operation silently misbehaves. - Assuming a tail pointer exists. In the base design there is none — that's the whole reason
addAtTailis O(n). Don't writethis.tail.next = newNodeunless you've also committed to updatingthis.tailin every method that changes the end of the list.
Where this pattern shows up next
The head-walk mechanic here is the foundation for every other singly-linked-list operation:
- Introduction to Linked List — the node/pointer model this class is built on.
- Adding Nodes to Linked List — addAtHead and addAtIndex, the sibling inserts.
- Deleting Nodes in Linked List — the reverse operation: walk to the node before the target and reroute its
next. - Middle of the Linked List — the fast/slow pointer trick that finds a position without knowing the length.
You can also step through the Design Linked List visualizer to watch curr hop toward the tail and the new node splice into place, one call at a time.
FAQ
Why is addAtTail O(n) instead of O(1)?
Because a singly linked list stores only a head pointer. To append, you have to find the last node, and the only way to reach it is to start at the head and follow next pointers until you hit the one whose next is null. That walk visits every existing node, so it scales linearly with list length. The exception is an empty list, where the new node becomes the head in O(1) with no walk.
How do I make addAtTail run in O(1)?
Cache a tail reference alongside head. Then appending is just this.tail.next = newNode; this.tail = newNode, with no traversal. The catch is bookkeeping: every method that can change the end of the list — addAtIndex near the end, deleteAtIndex of the last node — must also update this.tail, or it goes stale and points at a removed node. The base design skips the tail pointer specifically so the O(n) walk stays visible.
What does the size counter actually do?
size lets get, addAtIndex, and deleteAtIndex reject out-of-range indices in O(1) instead of walking the whole list to discover its length. LeetCode's get(index) must return -1 for invalid indices, and addAtIndex must ignore inserts past the end, so a maintained size is what makes those bounds checks cheap and correct.
Do I need a separate Node class?
You need something that bundles a value with a next pointer. A dedicated Node class is the clearest way, but a plain object literal like { val, next: null } works identically in JavaScript. What matters is that each node carries its own next reference — that reference chain, not any array index, is what threads the list together.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.