🧱 1. What is a Linked List?
A Linked List is a linear data structure where elements are stored in nodes, and each node points to the next.
[value | next] → [value | next] → [value | null]
👉 Last node always points to null
🔧 2. Node Structure
function Node(value) {
this.data = value;
this.next = null;
}
🏗️ 3. Linked List Class
var MyLinkedList = function () {
this.head = null;
this.len = 0; // MUST be 0
};
⚠️ IMPORTANT RULES (DO NOT IGNORE)
- Always use 0-based indexing
- Always update
len - Never break pointer chain
- Always check invalid index
📌 4. Add At Head
🖼️ Visualization
💡 Idea
New node becomes the first node.
🪜 Steps
- Create new node
- Point it to current head
- Move head to new node
✅ Code
MyLinkedList.prototype.addAtHead = function (val) {
const node = new Node(val);
node.next = this.head;
this.head = node;
this.len++;
};
⏱ Complexity
- O(1)
📌 5. Add At Tail
🖼️ Visualization
💡 Idea
Go to last node → attach new node
🪜 Steps
- If empty → head = node
- Else → traverse to last
- Connect last.next = node
✅ Code
MyLinkedList.prototype.addAtTail = function (val) {
const node = new Node(val);
if (!this.head) {
this.head = node;
this.len++;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
this.len++;
};
⏱ Complexity
- O(n)
📌 6. Get Value at Index
🖼️ Visualization
💡 Idea
Traverse from head to index
🪜 Steps
- Check bounds
- Move step-by-step
- Return value
✅ Code
MyLinkedList.prototype.get = function (index) {
if (index < 0 || index >= this.len) return -1;
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current.data;
};
⏱ Complexity
- O(n)
📌 7. Add At Index
🖼️ Visualization
💡 Idea
Reach index - 1, then insert
🪜 Steps
- If index invalid → return
- If index = 0 → head
- If index = len → tail
- Else:
- go to index - 1
- insert node
✅ Code
MyLinkedList.prototype.addAtIndex = function (index, val) {
if (index < 0 || index > this.len) return;
if (index === 0) {
this.addAtHead(val);
return;
}
if (index === this.len) {
this.addAtTail(val);
return;
}
let prev = this.head;
for (let i = 0; i < index - 1; i++) {
prev = prev.next;
}
const node = new Node(val);
node.next = prev.next;
prev.next = node;
this.len++;
};
⏱ Complexity
- O(n)
📌 8. Delete At Index
🖼️ Visualization
💡 Idea
Skip the node (bypass)
🪜 Steps
- Validate index
- If index = 0 → move head
- Else:
- go to index - 1
- bypass node
✅ Code
MyLinkedList.prototype.deleteAtIndex = function (index) {
if (index < 0 || index >= this.len) return;
if (index === 0) {
this.head = this.head.next;
this.len--;
return;
}
let prev = this.head;
for (let i = 0; i < index - 1; i++) {
prev = prev.next;
}
let toDelete = prev.next;
prev.next = toDelete.next;
toDelete.next = null; // cleanup
this.len--;
};
⏱ Complexity
- O(n)
🔥 FULL WORKING EXAMPLE
var obj = new MyLinkedList();
obj.addAtHead(10);
obj.addAtHead(20);
obj.addAtTail(30);
obj.addAtIndex(1, 99);
console.log(obj.get(1)); // 99
obj.deleteAtIndex(1);
console.log(obj.get(1)); // 10
🧠 MONSTER LEVEL UNDERSTANDING
🔑 Core Pattern
👉 Always work with previous node
prev.next = prev.next.next;
🔑 Golden Rule
Linked List = Pointer manipulation, not value shifting
🔑 Why Array vs Linked List
| Feature | Array | Linked List |
|---|---|---|
| Insert | O(n) | O(1) (if pointer known) |
| Delete | O(n) | O(1) |
| Access | O(1) | O(n) |
🔑 Most Important Interview Insight
You NEVER delete node directly
You only change links