Linked Lists
Nodes scattered in memory, joined by a single forward pointer. Cheap to insert into, but you lose the ability to jump straight to position 5, and you can only ever move one way.
- Describe a node as data plus a single pointer to the next node
- Trace insertion at the head, middle and tail
- Explain the trade-off against arrays in both directions
- State what a single forward pointer makes impossible
Finish first
Cost at a glance
- access
- O(n)
- search
- O(n)
- insertAtHead
- O(1)
- insertAtTail
- O(n)
- deleteAtHead
- O(1)
Topic contents
Lesson 1 of 3
Data plus a pointer
A linked list gives up the continuous block. Each node holds its value and the address of the next node, so nodes can sit anywhere in memory. The list is only reachable through its head, lose the head reference and the whole list is gone.
Because there is no continuous block, there is nothing to shift. Inserting means creating a node and rewiring two pointers, which is O(1) once you are standing at the right place. The catch is getting there: to reach position 5 you must walk through 0, 1, 2, 3 and 4, so access is O(n).
Singly linked list
Insert at head or tail, delete a value, and traverse, with pointer rewiring shown step by step.
Singly linked list
insert at head O(1) · access O(n)Start
Traversal starts at the head and follows next pointers until one is empty.
Lesson 2 of 3
The rewiring order
Step through an insert-at-head in the visualizer. The new node must be pointed at the current head first. Only then does the head reference move. Reverse those two steps and you have orphaned the entire remaining list, the classic linked-list bug.
Lesson 3 of 3
What one pointer costs you
Every node here knows its successor and nothing else. That single fact explains three limitations. You cannot walk backwards. Deleting a node requires the node before it, so you must walk from the head again even when you are already standing on the node to delete. And reaching the tail always costs a full traversal unless you keep a separate tail reference.
Adding a second pointer to every node removes all three limitations, at the cost of memory and an extra write on every link change. That is the doubly linked list, and it is the next topic.
Worked examples
Read the code, then change it
Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
let head = new Node(20, new Node(30));
// Point the new node at the old head BEFORE moving head.
head = new Node(10, head);
let cursor = head;
while (cursor) {
console.log(cursor.value);
cursor = cursor.next;
}Practice
Work these out yourself
No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.
0/3 attemptedAssessment
Check your understanding
Answer each question, then read the explanation. That is where the learning is.
Finished this topic?
0 of 3 lessons marked done. Marking the topic complete ticks the rest.