Python Linked Lists
Introduction
Linked lists are fundamental data structures that provide a way to store collections of data in a linear sequence. Unlike arrays or Python lists, linked lists don't store elements in contiguous memory locations. Instead, they use nodes that contain both the data and a reference (or "link") to the next node in the sequence.
In this tutorial, we'll explore how to implement linked lists in Python, understand their characteristics, and learn when they're the right choice for your programs.
Why Use Linked Lists?
While Python provides built-in lists, understanding linked lists offers several benefits:
- Dynamic memory allocation: Nodes are allocated as needed, no predefined size limit
- Efficient insertions and deletions: When you have references to specific nodes
- Understanding fundamental computer science concepts
- Building block for more complex data structures (queues, stacks, graphs)
Linked List Basics
A linked list consists of nodes, where each node contains:
- Data (the value stored)
- A reference to the next node
The last node points to None, indicating the end of the list.
Types of Linked Lists
- Singly Linked List: Each node points to the next node only
- Doubly Linked List: Each node points to both next and previous nodes
- Circular Linked List: The last node points back to the first node
Implementing a Singly Linked List
Let's build a singly linked list from scratch:
python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def append(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
return
# Find the last node
current = self.head
while current.next:
current = current.next
# Link the new node
current.next = new_node
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
return elements
Let's use our linked list:
python
# Create a new linked list
my_list = SinglyLinkedList()
# Add elements
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.prepend(5)
# Display the list
print(my_list.display()) # Output: [5, 10, 20, 30]
Common Linked List Operations
Let's implement more operations for our linked list:
python
class SinglyLinkedList:
# ... previous code ...
def insert_after_node(self, prev_node_data, new_data):
if self.is_empty():
print("List is empty")
return
current = self.head
while current and current.data != prev_node_data:
current = current.next
if current is None:
print(f"Node with data {prev_node_data} not found")
return
new_node = Node(new_data)
new_node.next = current.next
current.next = new_node
def delete_node(self, data):
if self.is_empty():
print("List is empty")
return
# If head node holds the data to be deleted
if self.head.data == data:
self.head = self.head.next
return
# Search for the data to delete
current = self.head
while current.next and current.next.data != data:
current = current.next
if current.next is None:
print(f"Node with data {data} not found")
return
# Update the next reference to skip the node to delete
current.next = current.next.next
def search(self, data):
current = self.head
position = 0
while current:
if current.data == data:
return position
current = current.next
position += 1
return -1 # Data not found
Let's see these operations in action:
python
my_list = SinglyLinkedList()
# Add elements
my_list.append(10)
my_list.append(20)
my_list.append(30)
print(my_list.display()) # Output: [10, 20, 30]
# Insert after a node
my_list.insert_after_node(10, 15)
print(my_list.display()) # Output: [10, 15, 20, 30]
# Search for an element
position = my_list.search(20)
print(f"Element 20 found at position: {position}") # Output: Element 20 found at position: 2
# Delete a node
my_list.delete_node(15)
print(my_list.display()) # Output: [10, 20, 30]
Implementing a Doubly Linked List
A doubly linked list allows traversal in both directions:
python
class DoublyNode:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def append(self, data):
new_node = DoublyNode(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
return
# Link the new node at the end
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def prepend(self, data):
new_node = DoublyNode(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
return
# Link the new node at the beginning
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def display_forward(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
return elements
def display_backward(self):
elements = []
current = self.tail
while current:
elements.append(current.data)
current = current.prev
return elements
Here's how we can use our doubly linked list:
python
# Create a new doubly linked list
double_list = DoublyLinkedList()
# Add elements
double_list.append(10)
double_list.append(20)
double_list.append(30)
double_list.prepend(5)
# Display forward and backward
print("Forward:", double_list.display_forward()) # Output: Forward: [5, 10, 20, 30]
print("Backward:", double_list.display_backward()) # Output: Backward: [30, 20, 10, 5]
Real-World Applications
Linked lists are used in many real-world scenarios:
1. Implementation of Other Data Structures
Linked lists serve as the foundation for other data structures:
python
class Queue:
def __init__(self):
self.linked_list = SinglyLinkedList()
def enqueue(self, data):
self.linked_list.append(data)
def dequeue(self):
if self.linked_list.is_empty():
return None
value = self.linked_list.head.data
self.linked_list.delete_node(value)
return value
def peek(self):
return None if self.linked_list.is_empty() else self.linked_list.head.data
def display(self):
return self.linked_list.display()
2. Browser History Navigation
A doubly linked list can be used to implement a browser's back and forward navigation:
python
class BrowserHistory:
def __init__(self, homepage):
self.history = DoublyLinkedList()
self.history.append(homepage)
self.current = self.history.head
def visit(self, url):
# Create new node after current position
new_node = DoublyNode(url)
# If we're not at the end of history, truncate forward history
if self.current != self.history.tail:
self.current.next = new_node
new_node.prev = self.current
self.history.tail = new_node
else:
# Append to the end
self.history.append(url)
self.current = self.history.tail
def back(self):
if self.current.prev:
self.current = self.current.prev
return self.current.data
return self.current.data
def forward(self):
if self.current.next:
self.current = self.current.next
return self.current.data
return self.current.data
3. Music Playlist
A circular linked list can represent a music playlist that loops:
python
class MusicPlaylist:
def __init__(self):
self.head = None
def add_song(self, song):
new_node = Node(song)
if not self.head:
self.head = new_node
new_node.next = new_node # Points to itself to create a circle
return
# Find the last node
current = self.head
while current.next != self.head:
current = current.next
# Add the new song and maintain the circular reference
current.next = new_node
new_node.next = self.head
def play_all(self):
if not self.head:
return []
songs = []
current = self.head
while True:
songs.append(current.data)
current = current.next
if current == self.head:
break
return songs
Performance Comparison: Linked Lists vs. Python Lists
Let's compare the performance characteristics:
| Operation | Linked List | Python List |
|---|---|---|
| Access by index | O(n) | O(1) |
| Insertion at beginning | O(1) | O(n) |
| Insertion at end | O(n)* | O(1)** |
| Deletion at beginning | O(1) | O(n) |
| Deletion at end | O(n)* | O(1) |
| Memory | Higher (extra references) | Lower |
* O(1) for doubly linked lists with tail reference ** Amortized O(1) for Python lists
When to Use Linked Lists
Linked lists are ideal when:
- You need frequent insertions or deletions at the beginning of the list
- You don't know how many items will be in the list in advance
- You don't need random access to elements
- Memory management is a concern and you want to allocate memory as you go
Summary
In this tutorial, we've explored:
- The concept and structure of linked lists
- Implementing singly linked lists, doubly linked lists, and their operations
- Real-world applications of linked lists
- Performance considerations compared to Python's built-in lists
Linked lists might not be used as frequently in Python due to the versatility of built-in lists, but understanding linked lists provides crucial insight into fundamental data structures and algorithms.
Exercises
- Implement a method for reversing a singly linked list
- Add a
size()method that returns the number of elements in the linked list - Implement a method to detect if a linked list has a cycle
- Create a method to find the middle node of a linked list in a single pass
- Implement a sorted insert method that keeps the linked list in ascending order
Additional Resources
If you spot any mistakes on this website, please let me know at [email protected]. I’d greatly appreciate your feedback! :)