Doubly Linked Lists & Bi-Directional Traversal
Doubly linked lists maintain both `next` and `prev` pointers per node. This enables $O(1)$ deletions and bi-directional traversal at the cost of one extra pointer in RAM 🔄.
class DNode:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
first = DNode("A")
second = DNode("B")
first.next = second
second.prev = first
print(f"Forward: {first.val} -> {first.next.val}")
print(f"Backward: {second.val} -> {second.prev.val} 🔄")
# 2. Doubly Linked Lists & Bi-Directional Traversal Doubly linked lists maintain both `next` and `prev` pointers per node. This enables $O(1)$ deletions and bi-directional traversal at the cost of one extra pointer in RAM 🔄. ```python class DNode: def __init__(self, val): self.val = val self.prev = None self.next = None first = DNode("A") second = DNode("B") first.next = second second.prev = first print(f"Forward: {first.val} -> {first.next.val}") print(f"Backward: {second.val} -> {second.prev.val} 🔄") ``` Because every node knows who precedes it, you can delete a node in $O(1)$ time by pointing `node.prev.next = node.next` without looping through previous nodes! 🔄 --- ### Question Why are doubly linked lists preferred over singly linked lists when implementing LRU caches? 🧠- [ ] a. Any node can unlink and delete itself in $O(1)$ time without traversing from the head 🔄 - [ ] b. They consume 50% less memory than singly linked lists - [ ] c. They bypass Python's garbage collector automatically - [ ] d. They automatically sort inserted items in ascending order --- ### Challenge Create `DNode` with `self.val = val; self.prev = None; self.next = None`. Connect `n1 = DNode(100)` and `n2 = DNode(200)`. Print `n2.prev.val`. 🎯 <details> <summary>Solution</summary> ```python class DNode: def __init__(self, val): self.val = val self.prev = None self.next = None n1 = DNode(100) n2 = DNode(200) n1.next = n2 n2.prev = n1 print(n2.prev.val) ``` </details>