Singly and Doubly Linked Lists in Python, Built From Scratch
A linked list stores each value in its own node, with the nodes connected by pointers instead of sitting in one contiguous block like a Python list. This post builds a SinglyLinkedList (each node points only forward) and a DoublyLinkedList (each node points both forward and backward), then runs insert/delete operations on each and prints the resulting order.
The code
class Node:
# Singly linked node: value + pointer to the next node (or None)
def __init__(self, value):
self.value = value
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_front(self, value):
# O(1): new node just points at the old head
node = Node(value)
node.next = self.head
self.head = node
def insert_end(self, value):
# O(n): must walk to the last node first, no tail pointer here
node = Node(value)
if self.head is None:
self.head = node
return
current = self.head
while current.next is not None:
current = current.next
current.next = node
def delete(self, value):
# O(n): find the node, relink its predecessor to its successor
if self.head is None:
return
if self.head.value == value:
self.head = self.head.next
return
current = self.head
while current.next is not None and current.next.value != value:
current = current.next
if current.next is not None:
current.next = current.next.next
def to_list(self):
result = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
class DNode:
# Doubly linked node: value + pointers to both neighbors
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_front(self, value):
node = DNode(value)
node.next = self.head
if self.head is not None:
self.head.prev = node
self.head = node
if self.tail is None:
self.tail = node
def insert_end(self, value):
# O(1): tail pointer means no walk needed, unlike the singly linked version
node = DNode(value)
node.prev = self.tail
if self.tail is not None:
self.tail.next = node
self.tail = node
if self.head is None:
self.head = node
def to_list_forward(self):
result = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
def to_list_backward(self):
result = []
current = self.tail
while current is not None:
result.append(current.value)
current = current.prev
return result
print("=== SinglyLinkedList ===")
sll = SinglyLinkedList()
sll.insert_front(3)
sll.insert_front(2)
sll.insert_front(1)
print("after insert_front(3), insert_front(2), insert_front(1):", sll.to_list())
sll.insert_end(99)
print("after insert_end(99):", sll.to_list())
sll.delete(2)
print("after delete(2):", sll.to_list())
print("\n=== DoublyLinkedList ===")
dll = DoublyLinkedList()
dll.insert_end(10)
dll.insert_end(20)
dll.insert_end(30)
print("after insert_end(10), insert_end(20), insert_end(30):", dll.to_list_forward())
dll.insert_front(1)
print("after insert_front(1):", dll.to_list_forward())
print("same list walked backward from tail:", dll.to_list_backward())SinglyLinkedList tracks only head; insert_end has to walk the whole chain to find the last node. DoublyLinkedList tracks both head and tail, so insert_end attaches directly at tail without walking, and the list can be traversed in either direction via next/prev.
Running it
Real output:
=== SinglyLinkedList ===
after insert_front(3), insert_front(2), insert_front(1): [1, 2, 3]
after insert_end(99): [1, 2, 3, 99]
after delete(2): [1, 3, 99]
=== DoublyLinkedList ===
after insert_end(10), insert_end(20), insert_end(30): [10, 20, 30]
after insert_front(1): [1, 10, 20, 30]
same list walked backward from tail: [30, 20, 10, 1]On the singly linked list, three insert_front calls with 3, 2, 1 produced [1, 2, 3] — each new value lands at the head, reversing the insertion order. insert_end(99) appended after walking to the tail, giving [1, 2, 3, 99], and delete(2) removed the middle node, leaving [1, 3, 99]. On the doubly linked list, three insert_end calls kept insertion order ([10, 20, 30]) since each attaches directly at tail; insert_front(1) put 1 at the head; and walking backward from tail via prev reproduced the same four values in reverse, [30, 20, 10, 1].
Takeaway
The run showed the structural difference in practice: the singly linked list’s insert_front reverses insertion order while insert_end requires a full walk, and the doubly linked list’s tail pointer let insert_end attach directly while prev pointers made a full reverse traversal possible.