Singly Linked List
DSA · Linked Lists
Theory
A linked list stores elements in nodes, where each node holds a value and a pointer to the next node. Nodes do not need to be contiguous in memory, so inserting or deleting at the head is O(1) without shifting anything. The trade-off is that reaching the kth element requires walking from the head, which is O(n), and each node uses extra memory for its pointer.
Why we use it
Linked lists make insertions and deletions cheap when you already have a reference to the position, and they grow without reallocating.
When to use it
Use them for queues and stacks, LRU caches (with a hash map), undo histories, and as building blocks in interview problems. Prefer arrays when you need fast random access.
How it works
- head -> node -> node -> None
- Each node stores data and next
- Traverse? Yes: current = head; while current: visit, current = current.next. No: -.
- Reach None: end of list
Syntax
class Node:
def __init__(self, val): self.val = val; self.next = None
Insert at head O(1)
Search / access O(n)
Delete (given previous node) O(1)Example
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, val):
node = Node(val)
node.next = self.head
self.head = node
def to_list(self):
out, cur = [], self.head
while cur:
out.append(cur.val)
cur = cur.next
return out
ll = LinkedList()
for v in [30, 20, 10]:
ll.push_front(v)
print("List:", " -> ".join(str(x) for x in ll.to_list()))Key points
- Each node points to the next
- O(1) insert/delete at the head
- O(n) to reach the kth node
- No shifting of elements needed