Editor

Python Program to Implement a Doubly Linked List

Intermediate · Data structures

A doubly linked list is a linked list where every node has two links, one to the next node and one to the previous node. The extra link lets you walk the list in both directions and unlink a node without searching for the one before it. This program adds nodes, deletes them from the start and the middle, and prints the list forwards and backwards, including when it is empty.

Program

doubly_linked_list.py
class Node:
def __init__(self, data):
self.data = data
self.prev = None # link to the node before
self.next = None # link to the node after
class DoublyLinkedList:
def __init__(self):
self.head = None # first node
self.tail = None # last node
def append(self, data):
node = Node(data)
if self.head is None: # empty list: the node is both ends
self.head = self.tail = node
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
def delete(self, data):
node = self.head
while node is not None and node.data != data:
node = node.next
if node is None:
print("Cannot delete", data, "because it is not in the list")
return
if node.prev is not None:
node.prev.next = node.next # the node before skips over it
else:
self.head = node.next # it was the head
if node.next is not None:
node.next.prev = node.prev # the node after skips back over it
else:
self.tail = node.prev # it was the tail
def show(self, label):
forward, node = [], self.head
while node is not None: # head to tail with next
forward.append(str(node.data))
node = node.next
backward, node = [], self.tail
while node is not None: # tail to head with prev
backward.append(str(node.data))
node = node.prev
print(label)
print(" Forward: ", " <-> ".join(forward) or "(empty)")
print(" Backward:", " <-> ".join(backward) or "(empty)")
dll = DoublyLinkedList()
dll.show("Empty list:")
for value in [10, 20, 30, 40]:
dll.append(value)
dll.show("After adding 10, 20, 30, 40:")
dll.delete(10) # the head
dll.delete(30) # a middle node
dll.show("After deleting 10 and 30:")
dll.delete(99)
Output
Empty list:
  Forward:  (empty)
  Backward: (empty)
After adding 10, 20, 30, 40:
  Forward:  10 <-> 20 <-> 30 <-> 40
  Backward: 40 <-> 30 <-> 20 <-> 10
After deleting 10 and 30:
  Forward:  20 <-> 40
  Backward: 40 <-> 20
Cannot delete 99 because it is not in the list

How it works

  1. Each Node has a prev and a next link, and the list keeps both its first node, head, and its last node, tail, which are None while it is empty.
  2. append() links the new node after the tail in both directions, node.prev = self.tail and self.tail.next = node, and then makes it the new tail.
  3. delete() finds the node, then makes the node before it point forward past it and the node after it point back past it, so it drops out of both directions.
  4. When the deleted node has no node before or after it, it was the head or the tail, so head or tail moves instead.
  5. show() walks forward from the head with next and backward from the tail with prev, and both walks must give the same items in opposite orders, which is a good check that every link is right.

Another way to write it

Using collections.deque

Using collections.deque
from collections import deque
items = deque([20, 30])
items.appendleft(10) # add at the front
items.append(40) # add at the back
print("Forward: ", list(items))
print("Backward:", list(reversed(items)))
print("Removed from the front:", items.popleft())
print("Removed from the back:", items.pop())
print("Now:", list(items))
Output
Forward:  [10, 20, 30, 40]
Backward: [40, 30, 20, 10]
Removed from the front: 10
Removed from the back: 40
Now: [20, 30]

Python's collections.deque is built as a doubly linked list of blocks, so adding and removing at either end is fast, the main strength of a doubly linked list, and real programs use it instead of writing their own.

Try it yourself

Add a prepend(data) method that puts a new node before the head, remembering to set both links.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises