Day 2: Arrays & Linked Lists
What You'll Learn Today
- How arrays work and their operation complexities
- How linked lists work and how to implement them
- Differences between singly and doubly linked lists
- When to use arrays vs. linked lists
Arrays
An array stores data in contiguous memory. You can instantly access any element using its index.
flowchart LR
subgraph Array["Array (Contiguous Memory)"]
A0["[0]\n42"]
A1["[1]\n17"]
A2["[2]\n93"]
A3["[3]\n8"]
A4["[4]\n56"]
end
style Array fill:#3b82f6,color:#fff
Basic Array Operations
const arr = [42, 17, 93, 8, 56];
// Access by index: O(1)
console.log(arr[2]); // 93
// Search for a value: O(n)
console.log(arr.indexOf(93)); // 2
// Add to end: O(1) amortized
arr.push(71);
// Add to beginning: O(n) - all elements must shift
arr.unshift(0);
// Remove from end: O(1)
arr.pop();
// Remove from beginning: O(n)
arr.shift();
// Insert at middle: O(n)
arr.splice(2, 0, 99);
Array Time Complexities
| Operation | Complexity | Reason |
|---|---|---|
| Index access | O(1) | Direct address calculation |
| Append | O(1)* | End address is known |
| Prepend | O(n) | Shift all elements |
| Insert at middle | O(n) | Shift elements after position |
| Search by value | O(n) | Compare sequentially |
| Remove last | O(1) | End address is known |
| Remove first | O(n) | Shift all elements |
*Amortized — O(n) when the array needs to be resized.
Linked Lists
A linked list is a data structure where each element (node) holds data and a pointer (reference) to the next node. Nodes don't need to be contiguous in memory.
flowchart LR
H["Head"] --> N1["42\nnext →"]
N1 --> N2["17\nnext →"]
N2 --> N3["93\nnext →"]
N3 --> N4["8\nnext →"]
N4 --> NULL["null"]
style H fill:#f59e0b,color:#fff
style N1 fill:#3b82f6,color:#fff
style N2 fill:#3b82f6,color:#fff
style N3 fill:#3b82f6,color:#fff
style N4 fill:#3b82f6,color:#fff
Singly Linked List Implementation
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Add to beginning: O(1)
prepend(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
this.size++;
}
// Add to end: O(n)
append(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
// Remove from beginning: O(1)
removeFirst() {
if (!this.head) return null;
const value = this.head.value;
this.head = this.head.next;
this.size--;
return value;
}
// Search: O(n)
find(value) {
let current = this.head;
while (current) {
if (current.value === value) return current;
current = current.next;
}
return null;
}
// Insert at position: O(n) to find, O(1) to insert
insertAt(index, value) {
if (index === 0) return this.prepend(value);
const node = new Node(value);
let current = this.head;
for (let i = 0; i < index - 1 && current; i++) {
current = current.next;
}
if (!current) return;
node.next = current.next;
current.next = node;
this.size++;
}
toArray() {
const result = [];
let current = this.head;
while (current) {
result.push(current.value);
current = current.next;
}
return result;
}
}
const list = new LinkedList();
list.prepend(3);
list.prepend(2);
list.prepend(1);
list.append(4);
console.log(list.toArray()); // [1, 2, 3, 4]
Doubly Linked Lists
In a doubly linked list, each node holds a reference to both the next and previous nodes. This enables O(1) operations from both ends.
flowchart LR
H["Head"] --> N1
N1["← 42 →"] <--> N2["← 17 →"]
N2 <--> N3["← 93 →"]
N3 --> T["Tail"]
style H fill:#f59e0b,color:#fff
style T fill:#f59e0b,color:#fff
style N1 fill:#8b5cf6,color:#fff
style N2 fill:#8b5cf6,color:#fff
style N3 fill:#8b5cf6,color:#fff
class DoublyNode {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
append(value) {
const node = new DoublyNode(value);
if (!this.tail) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.size++;
}
prepend(value) {
const node = new DoublyNode(value);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.size++;
}
removeLast() {
if (!this.tail) return null;
const value = this.tail.value;
if (this.head === this.tail) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
return value;
}
removeNode(node) {
if (node.prev) node.prev.next = node.next;
else this.head = node.next;
if (node.next) node.next.prev = node.prev;
else this.tail = node.prev;
this.size--;
return node.value;
}
}
Arrays vs. Linked Lists
flowchart TB
subgraph Compare["Which One to Choose?"]
Q1{"Need random\naccess?"}
Q2{"Frequent insert/delete\nat the head?"}
Q3{"Memory\nefficiency?"}
end
Q1 -->|Yes| Array["Array"]
Q1 -->|No| Q2
Q2 -->|Yes| LL["Linked List"]
Q2 -->|No| Q3
Q3 -->|Yes| Array
Q3 -->|No| LL
style Compare fill:#3b82f6,color:#fff
style Array fill:#22c55e,color:#fff
style LL fill:#8b5cf6,color:#fff
| Operation | Array | Linked List |
|---|---|---|
| Index access | O(1) | O(n) |
| Prepend | O(n) | O(1) |
| Append | O(1)† | O(n) / O(1)†† |
| Insert in middle | O(n) | O(n)††† |
| Search by value | O(n) | O(n) |
| Memory usage | Efficient | Pointer overhead |
| Cache performance | High | Low |
† Amortized †† With tail reference ††† O(1) if position is known
Practical Example: LRU Cache
An LRU (Least Recently Used) cache combines a hash map with a doubly linked list.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
this.list = new DoublyLinkedList();
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this.list.removeNode(node);
this.list.prepend(node.value);
this.map.set(key, this.list.head);
return node.value.val;
}
put(key, value) {
if (this.map.has(key)) {
this.list.removeNode(this.map.get(key));
}
this.list.prepend({ key, val: value });
this.map.set(key, this.list.head);
if (this.map.size > this.capacity) {
const removed = this.list.removeLast();
this.map.delete(removed.key);
}
}
}
Summary
| Concept | Description |
|---|---|
| Array | Contiguous memory, O(1) index access |
| Linked List | Nodes connected by pointers, O(1) head operations |
| Doubly Linked List | Bidirectional references, O(1) operations from both ends |
| Cache performance | Arrays benefit from CPU cache locality |
Key Takeaways
- Arrays excel at random access; linked lists excel at insertion/deletion
- JavaScript's
Arrayis a dynamic array that automatically resizes - Doubly linked lists enable efficient operations from both ends
- Real applications often combine both structures
Practice Problems
Problem 1: Basic
Implement a function that reverses a linked list.
function reverseList(head) {
// Your implementation here
}
Problem 2: Intermediate
Implement a function that returns the middle node of a linked list (hint: use two pointers).
Challenge
Merge two sorted linked lists into a single sorted linked list.
References
Next up: In Day 3, we'll explore "Stacks & Queues" — understanding LIFO (Last In, First Out) and FIFO (First In, First Out).