Linked lists are the gateway to understanding pointers, dynamic memory, and how more complex data structures like stacks and queues are built.
A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory.
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
Node head;
LinkedList() {
this.head = null;
}
}| Singly | Doubly | |
|---|---|---|
| Memory | Less (one pointer) | More (two pointers) |
| Traversal | Forward only | Both directions |
| Delete node | Need previous node | Can delete directly |
| Use case | Stacks, simple lists | Deques, LRU cache |
public void prepend(int val) {
Node node = new Node(val);
node.next = this.head;
this.head = node;
}public void append(int val) {
Node node = new Node(val);
if (this.head == null) {
this.head = node;
return;
}
Node curr = this.head;
while (curr.next != null) { // traverse to end
curr = curr.next;
}
curr.next = node;
}public void delete(int val) {
if (this.head == null) return;
if (this.head.val == val) {
this.head = this.head.next;
return;
}
Node curr = this.head;
while (curr.next != null) {
if (curr.next.val == val) {
curr.next = curr.next.next; // skip the node
return;
}
curr = curr.next;
}
}| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1) amortized | O(n) |
| Insert at middle | O(n) | O(1) if pointer known |
| Memory | Contiguous | Scattered |
| Cache performance | Excellent | Poor |
public Node findMiddle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // moves 1 step
fast = fast.next.next; // moves 2 steps
}
return slow; // slow is at middle when fast reaches end
}public boolean hasCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // they meet inside the cycle
return true;
}
}
return false;
}public Node reverse(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node nextNode = curr.next; // save next
curr.next = prev; // reverse pointer
prev = curr; // move prev forward
curr = nextNode; // move curr forward
}
return prev; // new head
}LRU (Least Recently Used) cache combines a hash map + doubly linked list:
import java.util.LinkedHashMap;
import java.util.Map;
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// true for access-order, false for insertion-order
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return (int) super.getOrDefault(key, -1);
}
public void