What Is a Linked List in Python?
A linked list is an ordered collection of nodes. Each node holds two things:
- Data – the value stored at that position
- Next – a reference (pointer) to the next node in the sequence
The list begins at a node called the head. Traversal continues node by node until a node’s next value is None, which marks the end of the list. There is no index-based random access like Python lists provide. You always start at the head and walk forward.
This structure makes linked lists exceptionally efficient for insertions and deletions near the beginning of a collection. In a standard Python list, inserting at position zero forces every element to shift one slot, an O(n) operation. In a linked list, you rewire a single pointer – O(1).
How to Create a Linked List in Python
Learning how to implement a linked list in Python starts with two classes: one for the individual node, and one for the list container.
The Node Class
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return str(self.data)
The LinkedList Class
python
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(str(node.data))
node = node.next
nodes.append("None")
return " -> ".join(nodes)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
With these two classes, you have a working linked list program in Python that supports initialization and traversal. Creating a sample list looks like this:
python
llist = LinkedList(["a", "b", "c", "d", "e"])
print(llist) # a -> b -> c -> d -> e -> None
Inserting Nodes into a Linked List
There are three main insertion patterns in a linked list implementation in Python: at the beginning, at the end, and between existing nodes.
Insert at the Beginning
python
def add_first(self, node):
node.next = self.head
self.head = node
No traversal needed. You update the head reference and the operation completes in O(1).
Insert at the End
python
def add_last(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
This requires traversing the entire list to reach the tail – O(n).
Insert After a Specific Node
python
def add_after(self, target_data, new_node):
for node in self:
if node.data == target_data:
new_node.next = node.next
node.next = new_node
return
raise Exception(f"Node '{target_data}' not found")
Insert Before a Specific Node
python
def add_before(self, target_data, new_node):
if self.head is None:
raise Exception("List is empty")
if self.head.data == target_data:
return self.add_first(new_node)
prev_node = self.head
for node in self:
if node.data == target_data:
prev_node.next = new_node
new_node.next = node
return
prev_node = node
raise Exception(f"Node '{target_data}' not found")
How to Delete a Node in a Linked List in Python
Deleting a node means finding the target, then relinking the node before it to point directly to the node after it, effectively removing the target from the chain.
python
def remove_node(self, target_data):
if self.head is None:
raise Exception("List is empty")
if self.head.data == target_data:
self.head = self.head.next
return
previous_node = self.head
for node in self:
if node.data == target_data:
previous_node.next = node.next
return
previous_node = node
raise Exception(f"Node '{target_data}' not found")
The essential technique for delete node in linked list Python is maintaining the previous_node reference throughout traversal. Without it, once you find and remove the target, you cannot re-link the surrounding nodes.
Singly Linked List in Python
Everything covered so far describes a singly linked list in Python, the most basic form. Each node points only forward. Traversal is one-directional, from head to tail.
Best suited for:
- FIFO queues where elements enter at the rear and leave from the front
- Stacks where elements are pushed and popped from the same end
- Simple sequential processing where backward traversal is never needed
Doubly Linked List in Python
A doubly linked list in Python extends each node with a previous pointer in addition to next. This bidirectional structure enables traversal in both directions and makes tail operations constant time.
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.previous = None
Python’s collections.deque is built on this structure internally, which is precisely why it delivers O(1) performance when appending or popping from both ends. If you have used deque for queue or stack implementations, you were already benefiting from a doubly linked list.
Best suited for:
- Browser history (forward and backward navigation)
- Undo/redo functionality in text editors
- Any system where you need to move in both directions through a sequence
Circular Linked List in Python
A circular linked list in Python differs from a singly linked list in one critical way: the last node points back to the head instead of None. The chain has no end, it loops continuously.
python
class CircularLinkedList:
def __init__(self):
self.head = None
def traverse(self, starting_point=None):
if starting_point is None:
starting_point = self.head
node = starting_point
while node is not None and (node.next != starting_point):
yield node
node = node.next
yield node
def print_list(self, starting_point=None):
nodes = []
for node in self.traverse(starting_point):
nodes.append(str(node))
print(" -> ".join(nodes))
One critical implementation detail: because there is no None terminator, you must stop traversal when the current node’s next equals your starting point – not when it equals None. Missing this causes an infinite loop.
Real-world applications:
- Turn-based multiplayer games (cycling through players indefinitely)
- Operating system round-robin CPU scheduling
- Media players with “repeat all” enabled
- Fibonacci heap implementation
How to Reverse a Linked List in Python
Reversing a linked list is one of the most common technical interview problems involving this data structure. The iterative solution is clean, runs in O(n) time, and requires only O(1) extra space.
python
def reverse(self):
prev = None
current = self.head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev
Step-by-step walkthrough:
- Initialize prev = None and current = self.head
- Save current.next into next_node before overwriting it
- Flip current.next to point backward toward prev
- Advance prev to current, and current to next_node
- Repeat until current is None – at that point prev is the new head
The most common mistake here is forgetting step 2. If you overwrite current.next without saving it first, you lose the rest of the list permanently.
Performance Comparison: Python List vs Linked List
Operation | Python List | Singly Linked List | Doubly Linked List |
Insert at beginning | O(n) | O(1) | O(1) |
Insert at end | O(1) | O(n) | O(1) |
Delete at beginning | O(n) | O(1) | O(1) |
Delete at end | O(n) | O(n) | O(1) |
Access by index | O(1) | O(n) | O(n) |
Search by value | O(n) | O(n) | O(n) |
The takeaway is clear. When your application frequently inserts or removes elements near the front of a collection — as in a queue — a linked list significantly outperforms a standard Python list. For index-based random access, Python’s built-in list wins decisively.
Creating a Playlist with Linked Lists in Python
One of the most intuitive real-world applications of a linked list program in Python is a music playlist manager. Songs can be added at any position, removed by name, shuffled, and loaded from external files, all without the element-shifting overhead that a regular Python list would impose.
This project uses three standard Python modules alongside the linked list structure:
- time: introduces playback delays to simulate song duration
- random: enables shuffle functionality
- csv: allows importing a song library from an external file
Song and Node Classes
python
import time
import random
import csv
class Song:
def __init__(self, song_id, song_name, song_length):
self.song_id = song_id
self.song_name = song_name
self.song_length = song_length
def __str__(self):
return str({
'song_id': self.song_id,
'song_name': self.song_name,
'song_length': self.song_length
})
class ListNode:
def __init__(self, song: Song):
self.song = song
self.next = None
def __str__(self):
return str(self.song)
The Playlist LinkedList Class
python
class LinkedList:
def __init__(self):
self.head_node = None
self.count = 0
def traversal(self):
if self.head_node is None:
return
temp_node = self.head_node
while temp_node is not None:
print(temp_node.song)
time.sleep(2)
temp_node = temp_node.next
def insert_at_start(self, node):
if self.head_node is None:
self.head_node = node
self.count += 1
return True
node.next = self.head_node
self.head_node = node
return True
def insert_after(self, song_name, node):
temp_node = self.head_node
while temp_node and temp_node.song.song_name != song_name:
temp_node = temp_node.next
if temp_node is None:
return False
if temp_node.next is None:
temp_node.next = node
else:
node.next = temp_node.next
temp_node.next = node
return True
def insert_before(self, song_name, node):
temp_node = self.head_node
prev_node = None
while temp_node and temp_node.song.song_name != song_name:
prev_node = temp_node
temp_node = temp_node.next
if temp_node is None:
return False
if prev_node is None:
node.next = self.head_node
self.head_node = node
return True
prev_node.next = node
node.next = temp_node
return True
def delete_song(self, song_name):
curr = self.head_node
if curr.song.song_name == song_name:
self.head_node = curr.next
del curr
return
while curr is not None:
if curr.next and curr.next.song.song_name == song_name:
break
curr = curr.next
if curr is None:
raise Exception("Song not found in playlist")
temp = curr.next
curr.next = curr.next.next
del temp
Loading Songs from a CSV File
python
def create_linked_list(filepath):
with open(filepath, newline='') as csvfile:
reader = csv.DictReader(csvfile)
linked_list = LinkedList()
for row in reader:
song = Song(row['Song ID'], row['Song Name'], row['Song Length'])
listnode = ListNode(song)
linked_list.insert_at_start(listnode)
return linked_list
Why a Linked List Makes Sense for a Playlist
A standard Python list requires shifting every subsequent element each time a song is inserted at an arbitrary position. With a linked list, inserting a song between two existing tracks is just a pointer update – O(1) for the rewiring once the target position is found. For a dynamic playlist that changes frequently, tracks added mid-queue, songs skipped, the order rearranged on the fly, a linked list provides both clean logic and efficient performance.
Common Mistakes When Working with Linked Lists in Python
Even experienced developers make avoidable errors when working with linked list examples in Python. These are the patterns to watch:
Not checking for an empty list. Every method that modifies the list should verify that self.head is not None before attempting pointer operations.
Losing the previous node reference during deletion. You must track the predecessor at every step. Losing it means you cannot re-link after removing the target node.
Infinite loops in circular linked lists. Always check whether node.next == starting_point, not whether node.next is None. There is no tail in a circular structure.
Overwriting next before saving it during reversal. This permanently severs access to the rest of the list. Always store current.next in a temporary variable first.
When to Use a Linked List vs Python’s Built-in List
Use a linked list when:
- You need O(1) insertions or deletions at the beginning of a collection
- You are implementing a FIFO queue and performance at both ends matters
- You are building features like undo stacks, browser history, or turn-based game logic
- You need bidirectional traversal (choose a doubly linked list)
Stick with Python’s list when:
- You need fast O(1) random access by index
- The collection is mostly read-heavy with rare structural changes
- Simplicity and built-in method support outweigh performance edge cases
Conclusion
A linked list in Python is more than a data structures textbook topic. It is a practical tool with real applications in queues, stacks, graph adjacency representations, operating system process management, and dynamic media applications like playlist managers.
Understanding how to implement a linked list in Python, and knowing when to choose between singly, doubly, and circular variants, sharpens your thinking about performance trade-offs and memory design. Practice building these from scratch, apply them to a real project like the playlist example above, and the concepts will solidify quickly. Once you have that foundation, you will start recognizing scenarios in your own work where a linked list is exactly the right structure for the job.
