DSA course menu
Singly Linked Lists in Python: Build One From Scratch
Learn singly linked lists: nodes and next pointers, building a LinkedList class in Python with append, prepend, insert, delete and search, and how linked lists compare with arrays.
On this page
A linked list stores items in separate nodes. Each node holds a value and a reference (a "pointer") to the next node. The list itself only remembers the first node, the head; the last node points to None.
head
│
▼
[ 3 | •]──▶[ 7 | •]──▶[ 1 | None]Unlike an array, the nodes are not next to each other in memory, so there is no jumping to item i. In exchange, adding or removing a node only changes a pointer or two; nothing shifts.
The node#
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
# Build 3 -> 7 -> 1 by hand
head = Node(3, Node(7, Node(1)))
node = head
while node: # walk until we fall off the end
print(node.value)
node = node.next3
7
1Walking the list (traversal) follows next from node to node: O(n).
A LinkedList class#
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def prepend(self, value): # O(1)
self.head = Node(value, self.head)
self.size += 1
def append(self, value): # O(n): must find the last node
new = Node(value)
if self.head is None:
self.head = new
else:
node = self.head
while node.next:
node = node.next
node.next = new
self.size += 1
def find(self, value): # O(n)
node = self.head
while node:
if node.value == value:
return node
node = node.next
return None
def delete(self, value): # O(n) to find, O(1) to unlink
if self.head is None:
return False
if self.head.value == value:
self.head = self.head.next
self.size -= 1
return True
prev = self.head
while prev.next:
if prev.next.value == value:
prev.next = prev.next.next # skip over the node
self.size -= 1
return True
prev = prev.next
return False
def __iter__(self):
node = self.head
while node:
yield node.value
node = node.next
def __repr__(self):
return " -> ".join(str(v) for v in self) or "(empty)"
lst = LinkedList()
for v in [7, 1, 9]:
lst.append(v)
lst.prepend(3)
print(lst, "| size", lst.size)
print(lst.find(9) is not None, lst.find(42))
lst.delete(1)
lst.delete(3)
print(lst, "| size", lst.size)3 -> 7 -> 1 -> 9 | size 4
True None
7 -> 9 | size 2Deleting a node means making the node before it point past it. The removed node is no longer reachable, and Python frees it automatically.
Adding a tail pointer#
append walks the whole list to find the end. Keeping a reference to the last node (the tail) makes it O(1):
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class TailList:
def __init__(self):
self.head = self.tail = None
def append(self, value): # O(1) now
new = Node(value)
if self.tail is None:
self.head = self.tail = new
else:
self.tail.next = new
self.tail = new
t = TailList()
for v in "ABC":
t.append(v)
print(t.head.value, t.tail.value, t.head.next.value)A C BThe cost: every method that changes the end of the list must keep tail correct too.
Linked list or array?#
In everyday Python, a list (or collections.deque for fast ends) is almost always the better choice; arrays are also faster in practice because their items sit together in memory. Linked lists matter because they are the building block of stacks and queues, hash table chains, LRU caches and graphs, and because they are a favourite interview topic.
Common mistakes#
Practice#
Practice exercise
Write from_list(values) that builds a linked list from a Python list and returns its head, and to_list(head) that turns it back into a Python list. Then write insert_sorted(head, value) that inserts a value into an already sorted linked list, keeping it sorted, and returns the (possibly new) head.
Show hint
If the list is empty or the value belongs before the head, the new node becomes the head. Otherwise walk with node while node.next exists and node.next.value < value, then link the new node in after node.
Show solution
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def from_list(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.value)
head = head.next
return out
def insert_sorted(head, value):
if head is None or value <= head.value:
return Node(value, head)
node = head
while node.next and node.next.value < value:
node = node.next
node.next = Node(value, node.next)
return head
head = from_list([2, 5, 9])
for v in [1, 6, 10]:
head = insert_sorted(head, v)
print(to_list(head))[1, 2, 5, 6, 9, 10]Key takeaway#
Next: nodes that point both ways, Doubly Linked Lists.
Finished this lesson?