🎓 A1Learner
🔍
0 of 112 lessons completed

DSA Doubly Linked Lists

A doubly linked list is a chain of nodes that holds values in order with links in both directions. Each node holds a value, a next link, and a prev link to the node before it.

One node, two links

A lone doubly linked node points both ways to None. Its value sits between the two links.

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

node = Node(7)
print("value:", node.value)
print("next:", node.next)
print("prev:", node.prev)

Walk both ways

Three nodes link forward with next and backward with prev. The forward walk and the backward walk visit the same values in reverse order.

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

a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.prev = a
b.next = c
c.prev = b
node = a
forward = []
while node is not None:
    forward.append(node.value)
    last = node
    node = node.next
backward = []
node = last
while node is not None:
    backward.append(node.value)
    node = node.prev
print("forward:", forward)
print("backward:", backward)

Delete a known middle node

The program holds the middle node directly, so no walk is needed. Its neighbours link to each other and skip it.

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

a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.prev = a
b.next = c
c.prev = b
a.next = c
c.prev = a
print("after a:", a.next.value)
print("before c:", c.prev.value)

Example

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


def build(values):
    head = None
    tail = None
    nodes = []
    for value in values:
        node = Node(value)
        nodes.append(node)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            node.prev = tail
            tail = node
    return head, tail, nodes


def walk(head, forward=True):
    values = []
    visits = 0
    node = head
    while node is not None:
        values.append(node.value)
        visits += 1
        node = node.next if forward else node.prev
    return values, visits


head, tail, nodes = build([10, 20, 30, 40, 50])
forward, fvisits = walk(head)
backward, bvisits = walk(tail, forward=False)
print("forward:", forward, "visits:", fvisits)
print("backward:", backward, "visits:", bvisits)
middle = nodes[2]
middle.prev.next = middle.next
middle.next.prev = middle.prev
forward, fvisits = walk(head)
backward, bvisits = walk(tail, forward=False)
print("after delete forward:", forward, "visits:", fvisits)
print("after delete backward:", backward, "visits:", bvisits)

Key points

  • A doubly linked list holds each value in a node with a next link and a prev link.
  • The prev link of the first node holds None.
  • The next link of the last node holds None.
  • A walk can move backward from the last node by following prev links.
  • Deleting a known node relinks its two neighbours to each other.
  • A known node is a node the program already holds a reference to.

In this example, build links five nodes in both directions. The forward walk and the backward walk each visit all five nodes. The middle node is then deleted by relinking its two neighbours. Both walks now visit four nodes, and the backward walk still mirrors the forward one.

Note

Each node pays for its prev link with one extra stored reference.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A program holds a reference to a middle node in a doubly linked list. What does deleting it need?