Back
+20 XP
Concept

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} 🔄")

# 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>

Checkpoint

Why are doubly linked lists preferred over singly linked lists when implementing LRU caches? 🧠

Practice

Create `DNode` with `self.val = val; self.prev = None; self.next = None`. Connect `n1 = DNode(100)` and `n2 = DNode(200)`. Print `n2.prev.val`. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks