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:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None| 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 |
def prepend(self, val):
node = Node(val)
node.next = self.head
self.head = nodedef append(self, val):
node = Node(val)
if not self.head:
self.head = node
return
curr = self.head
while curr.next: # traverse to end
curr = curr.next
curr.next = nodedef delete(self, val):
if not self.head: return
if self.head.val == val:
self.head = self.head.next
return
curr = self.head
while curr.next:
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 |
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # moves 1 step
fast = fast.next.next # moves 2 steps
return slow # slow is at middle when fast reaches enddef has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # they meet inside the cycle
return True
return Falsedef reverse(head):
prev = None
curr = head
while curr:
next_node = curr.next # save next
curr.next = prev # reverse pointer
prev = curr # move prev forward
curr = next_node # move curr forward
return prev # new headLRU (Least Recently Used) cache combines a hash map + doubly linked list:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap: