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:

1. Dynamic memory allocation: Nodes are allocated as needed, no predefined size limit
2. Efficient insertions and deletions: When you have references to specific nodes
3. Understanding fundamental computer science concepts
4. Building block for more complex data structures (queues, stacks, graphs)

Linked List Basics

A linked list consists of nodes, where each node contains:

1. Data (the value stored)
2. A reference to the next node

The last node points to None, indicating the end of the list.

Types of Linked Lists

1. Singly Linked List: Each node points to the next node only
2. Doubly Linked List: Each node points to both next and previous nodes
3. 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:

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:

# 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:

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:

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:

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:

# 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:

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:

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:

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:

1. You need frequent insertions or deletions at the beginning of the list
2. You don't know how many items will be in the list in advance
3. You don't need random access to elements
4. 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

1. Implement a method for reversing a singly linked list
2. Add a size() method that returns the number of elements in the linked list
3. Implement a method to detect if a linked list has a cycle
4. Create a method to find the middle node of a linked list in a single pass
5. Implement a sorted insert method that keeps the linked list in ascending order

Additional Resources

• Python Data Structures and Algorithms
• Visualizing Linked Lists
• Leetcode Linked List Problems
• Pythonic Implementations of Data Structures
• Interactive Python: Linked Lists