Editor

Python Program to Implement a Linked List

Intermediate · Data structures

A linked list stores items in nodes, where each node holds a value and a link to the next node, and the last node links to nothing (None). Unlike a Python list, the items are not kept side by side, so adding or removing a node only changes a link. This program builds a singly linked list and shows adding, deleting, traversing and the empty list.

Program

linked_list.py
class Node:
def __init__(self, data):
self.data = data
self.next = None # link to the next node; None means the end
class LinkedList:
def __init__(self):
self.head = None # the first node; None means the list is empty
def append(self, data): # add a node at the end
if self.head is None:
self.head = Node(data)
return
last = self.head
while last.next is not None: # walk to the last node
last = last.next
last.next = Node(data)
def delete(self, data):
previous, current = None, self.head
while current is not None and current.data != data:
previous, current = current, current.next
if current is None:
print("Cannot delete", data, "because it is not in the list")
elif previous is None:
self.head = current.next # deleting the first node
else:
previous.next = current.next # link around the deleted node
def show(self, label): # traverse from the head to the end
values, current = [], self.head
while current is not None:
values.append(str(current.data))
current = current.next
print(label, " -> ".join(values + ["None"]))
items = LinkedList()
items.show("Empty list:")
for value in [10, 20, 30, 40]:
items.append(value)
items.show("After adding 10, 20, 30, 40:")
items.delete(10) # the head
items.delete(30) # a middle node
items.show("After deleting 10 and 30:")
items.delete(99)
Output
Empty list: None
After adding 10, 20, 30, 40: 10 -> 20 -> 30 -> 40 -> None
After deleting 10 and 30: 20 -> 40 -> None
Cannot delete 99 because it is not in the list

How it works

  1. Each Node holds its data and a next link, and the list itself only remembers its first node, head, which is None while the list is empty.
  2. append() walks from the head along the next links until it reaches the last node, then links the new node after it.
  3. delete() walks the list while remembering the node before the current one, and removes a node by linking that previous node straight to the node after it.
  4. Deleting the head is a special case with no previous node, so the head simply moves on to the second node.
  5. show() traverses the list from the head to the end, which is why an empty list prints just None, and deleting a missing value prints a message instead of crashing.

Another way to write it

Insert at the front and search

Insert at the front and search
class Node:
def __init__(self, data, link=None):
self.data = data
self.next = link
head = None # start with an empty list
for value in [30, 20, 10]:
head = Node(value, head) # the new node links to the old head
def search(head, target):
position, current = 0, head
while current is not None:
if current.data == target:
return position
position, current = position + 1, current.next
return -1
print("Position of 20:", search(head, 20))
print("Position of 99:", search(head, 99), "(not found)")
Output
Position of 20: 1
Position of 99: -1 (not found)

Adding at the front is the quickest insert, because the new node just points at the old first node and becomes the head, while a search has to follow the links one by one from the head.

Try it yourself

Add a length() method that walks the list and returns how many nodes it has.

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