Linked List Overview
Master the structure of Nodes and Pointers.
What is a Linked List?
A Linked List is a linear data structure where elements are stored in nodes. Unlike arrays, nodes are not stored in contiguous memory locations; instead, each node contains a pointer (reference) to the next node in the sequence.
The Motivation: Dynamic Memory
Arrays have fixed sizes. If you need to insert an element in the middle of a large array, you have to shift all subsequent elements (O(N)). Linked Lists allow O(1) insertion and deletion at a node you already hold a reference to, and they grow one node at a time without reallocating a large block of memory.
Visualizing the Structure
Imagine a treasure hunt. Each clue (Node) has a piece of information (Data) and the location of the next clue (Pointer). You can't skip to the end; you must follow the trail from the start (Head).
When should I use a Linked List?
- Dynamic Size: When you don't know the number of elements in advance.
- Frequent Insertions/Deletions: Especially at the beginning or middle.
- Implementing Stacks/Queues: Easy to add/remove from ends.
The Intuition: Chasing Pointers
Navigating a linked list is about moving from one node to the next using current = current.next. You must always ensure you don't lose the reference to the head, and be careful not to access properties of null (the end of the list).
Interactive Visualization
5 NODES · HEAD → … → NULL
CURRENT = HEAD
head current
#0
→
#1
→
#2
→
#3
→
#4
→ NULL
current
3
Printed
0
printed
Nothing yet
current = head: the node holding 3
Next
current is not NULL — it holds 3, so keep going
Values
Legend & Complexity
current: the node being read
Already printed
The next compartment: where the pointer lives
→ a next pointer; → NULL ends the list
Traversal
O(n)
Access by index
O(n)
Space
O(1)
Walk a list the only way a linked list allows: start at head, print current.val, then follow current = current.next until current is NULL. Each node is a value and a next pointer, and the code panel lights the line that is running.
Basic Operations Template
A node definition, and the traversal loop every other linked-list technique builds on.
Linked List Overview Code
1function ListNode(val, next) {2 this.val = (val===undefined ? 0 : val)3 this.next = (next===undefined ? null : next)4}56// Traversal7let current = head;8while (current) {9 console.log(current.val);10 current = current.next;11}
Edge Cases & Common Mistakes
- Null Head: Always check if
headis null before accessing properties. - Lost Reference: If you change
headwithout saving it, you lose the whole list. - Cycles: Iterating forever if the list loops back on itself.
Summary
Linked Lists are fundamental for understanding pointers and references. They trade the speed of random access for the flexibility of dynamic insertion and deletion.