Linked lists give O(1) prepend — use over arrays when frequent insertions at head are needed.
Linked Lists
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self): self.head = None
def prepend(self, data): # O(1)
node = Node(data)
node.next = self.head
self.head = node
def append(self, data): # O(n)
node = Node(data)
if not self.head: self.head = node; return
cur = self.head
while cur.next: cur = cur.next
cur.next = node
def delete(self, data): # O(n)
if not self.head: return
if self.head.data == data:
self.head = self.head.next; return
cur = self.head
while cur.next and cur.next.data != data:
cur = cur.next
if cur.next: cur.next = cur.next.next
# Reverse linked list (classic interview)
def reverse(head):
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev