Python Tutorial
Linked Lists
A chain of nodes where each node points to the next — flexible insertion without shifting elements.
Nodes and Links
Unlike an array, a linked list stores elements in separate nodes scattered in memory. Each node holds a value and a reference to the next node. The list knows only its head; you follow links to reach the rest.
This makes inserting or deleting at a known position O(1) (just rewire pointers) but accessing the k-th element O(n) (you must walk the chain).
Arrays vs Linked Lists
| Operation | Array / List | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert/delete at front | O(n) | O(1) |
| Insert/delete at known node | O(n) | O(1) |
| Memory | Compact | Extra pointer per node |
A Singly Linked List
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, value): # O(1)
node = Node(value)
node.next = self.head
self.head = node
def append(self, value): # O(n)
node = Node(value)
if not self.head:
self.head = node
return
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
def __iter__(self):
cur = self.head
while cur:
yield cur.value
cur = cur.next
ll = LinkedList()
ll.append(1); ll.append(2); ll.push_front(0)
print(list(ll)) # [0, 1, 2]Searching and Deleting
def delete(self, value): # O(n)
cur = self.head
prev = None
while cur:
if cur.value == value:
if prev:
prev.next = cur.next # unlink
else:
self.head = cur.next # delete head
return True
prev, cur = cur, cur.next
return FalseDeletion is O(1) once you hold the node's predecessor — the cost is finding it.
Reversing a Linked List
Reversing in place is a classic interview problem — flip each next pointer while walking once through the list.
def reverse(head):
prev = None
cur = head
while cur:
nxt = cur.next # remember the rest
cur.next = prev # flip the link
prev = cur # advance
cur = nxt
return prev # new headVariants and the Cycle Trick
- Doubly linked list: each node also points to the previous node — O(1) deletion given only the node.
- Circular linked list: the tail points back to the head.
Floyd's fast/slow pointers detect a cycle in O(n) time, O(1) space:
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseBest Practices
- Choose a linked list when you insert/delete often and rarely index randomly.
- For most Python code, a
listordequeis faster due to cache locality. - Guard against losing references — save
nextbefore rewiring. - Use
dequeinstead of hand-rolling a doubly linked list in practice.
Try It Yourself
Exercise 1: Count the nodes in a singly linked list.
Show solution
def length(head):
n = 0
cur = head
while cur:
n += 1
cur = cur.next
return nExercise 2: Why is accessing the k-th element O(n) in a linked list but O(1) in an array?
Show solution
An array computes the element's address directly; a linked list must follow k pointers from the head.
📘 Real-World Deep Dive
Knowing <strong>DSA Linked Lists (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Linked Lists that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
class Node:
__slots__ = ("val", "next")
def __init__(self, val, nxt=None):
self.val = val; self.next = nxt
def __repr__(self):
return f"{self.val}→{repr(self.next) if self.next else '∅'}"
def from_list(xs):
head = None
for x in reversed(xs):
head = Node(x, head)
return head
print(from_list([1, 2, 3]))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Linked Lists as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.