AI Hints
Home›DSA in Python Tutorial›Linked List Techniques
DSA in Python · Lesson 39 of 132

Doubly Linked Lists

Arrows both ways.

⏱ 2 min read▶ Video at 45:06🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

In a doubly linked list, every node points to the next node and to the previous one. It uses a little more memory, but you can walk in both directions, and remove any node you're holding in O of one.

Doubly Linked Lists
From the video: Doubly Linked Lists
  • Next and previous
  • Walk both ways
  • Remove a node in O(1)

A node with two arrows

Each node now has prev and next. To remove a node, its neighbours simply point at each other, and that takes O of one, with no searching. Here we link A, B, and C, then remove B. Run it. Walking forwards and backwards both skip B now.

doubly.pypython
class Node:
    def __init__(self, value):
        self.value, self.prev, self.next = value, None, None

a, b, c = Node("A"), Node("B"), Node("C")
a.next, b.prev, b.next, c.prev = b, a, c, b

b.prev.next = b.next
b.next.prev = b.prev

print(a.value, a.next.value)
print(c.value, c.prev.value)
Output
A C
C A

Which list when?

Here's how to choose. Python's list is best for most work, with fast indexing. Deque is best for adding and removing at both ends. A singly linked list is simple, and good for stacks and interview questions. A doubly linked list shines when you must remove items from the middle quickly, like in a least recently used cache.

StructureBest for
listindexing, most everyday work
dequefast at both ends
singly linkedsimple chains, interviews
doubly linkedO(1) removal anywhere, LRU caches

Summary

A doubly linked list has arrows both ways, so removing a node is O of one. Next, a new section. Recursion, when a function calls itself.

Key takeaways
  • prev and next
  • O(1) removal
  • Used in LRU caches
Next up: Recursion — a function that calls itself