Singly Linked Lists from Scratch
A linked list chains heap nodes together via pointers. Each `Node` holds a value and a pointer (`next`) to the subsequent node, allowing $O(1)$ head insertions 🔗.
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
# Chain nodes: 1 -> 2 -> 3
head = Node(1, Node(2, Node(3)))
# Traverse:
curr = head
while curr:
print(f"Node({curr.val}) 🔗")
curr = curr.next
# 1. Singly Linked Lists from Scratch A linked list chains heap nodes together via pointers. Each `Node` holds a value and a pointer (`next`) to the subsequent node, allowing $O(1)$ head insertions 🔗. ```python class Node: def __init__(self, val, nxt=None): self.val = val self.next = nxt # Chain nodes: 1 -> 2 -> 3 head = Node(1, Node(2, Node(3))) # Traverse: curr = head while curr: print(f"Node({curr.val}) 🔗") curr = curr.next ``` Unlike Python lists which are contiguous memory arrays requiring $O(n)$ shifts on `insert(0, x)`, a linked list prepends in $O(1)$ time by rewiring a single reference! 🔗 --- ### Question What is the time complexity of prepending a new node to the front of a singly linked list? 🧠- [ ] a. $O(1)$ constant time by updating the head pointer 🔗 - [ ] b. $O(n)$ linear time because all nodes must be reallocated - [ ] c. $O(n^2)$ quadratic time - [ ] d. $O(\log n)$ logarithmic time --- ### Challenge Create class `Node: def __init__(self, val, nxt=None): self.val = val; self.next = nxt`. Chain `Node(10, Node(20))`. Traverse and collect values into list `res`. Print `res`. 🎯 <details> <summary>Solution</summary> ```python class Node: def __init__(self, val, nxt=None): self.val = val self.next = nxt head = Node(10, Node(20)) res = [] curr = head while curr: res.append(curr.val) curr = curr.next print(res) ``` </details>