Python Linked Lists: Explanation & Examples

The boring section

What are linked lists?

A linked list is a type of data structure that stores a sequence of data elements, but unlike an array or a list, the elements are not stored in a contiguous block of memory. Instead, each element has a pointer or a link to the next element in the sequence, forming a chain of nodes. A linked list looks as follows:

Head -> Node1 -> Node2 -> Node3 -> None

In this representation, Head points to the first node in the linked list, and each node points to the next node in the sequence until the last node (Node3) that points to None, indicating the end of the linked list.

It’s okay if you don’t want to learn about linked lists

You might have heard a lot about linked lists in data structure classes or online courses. However, to be honest, you don’t have to know about them, and you might never use them in real-world projects nowadays.

Linked lists are NOT built-in in Python. You have to implement them yourself using classes or use a module like collections.deque that provides a linked list-like data structure (this work will be complicated and quite laborious). One possible reason why Python does not have a built-in linked list data structure is that it already provides a lot of flexibility and functionality with its list type, which can be used as a stack, a queue, or a general-purpose collection. Another possible reason is that Python is designed to be a high-level and expressive language, which abstracts away the low-level details of memory management and data structures.

That being said, learning linked lists still has certain benefits, such as giving you more control and efficiency over your data manipulation, especially when you need to insert or remove elements from both ends of the list.

Linked lists vs normal lists in Python

A linked list has some advantages and disadvantages compared to a regular list.

Advantages:

• You can easily add or remove data from anywhere in the list without shifting the other elements.
• You don’t need to specify the size of the list in advance, as it can grow or shrink dynamically.
• You can use linked lists to implement other data structures, such as queues, stacks, or graphs.

Disadvantages:

• You need more memory to store the links between the nodes, as well as the nodes themselves.
• You cannot access a specific element in the list by its index, as you have to traverse the list from the beginning until you find it.
• You have to be careful not to lose or break the links between the nodes, as this can cause errors or data loss.

The boring part with text and concepts should end here. It’s time to practice.

Examples

Working with linked lists requires writing a lot of code (way more than normal lists). That’s why I guess you don’t like them much. Anyway, it’s good to see some code examples.

Creating a linked list and appending some data

In this example, we’ll create a simple linked list by defining a custom Node class and a LinkedList class to manage the nodes:

# SlingAcademy.com
# This code uses Python 3.11.4

# Define a node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Define a linked list class
class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Create a linked list and append some data
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

# Print the linked list
linked_list.print_list()

Output:

1 -> 2 -> 3 -> None

Doubly linked list

A doubly linked list is a type of linked list in which each node consists of three attributes: data, next, and previous. The data attribute is used to store the data in the node. The next attribute is used to refer to the next node in the linked list. And, the previous attribute is used to refer to the previous node in the linked list.

To implement a doubly linked list in Python, we can define a Node class and a DoublyLinkedList class. The Node class will have three attributes: data, next, and prev. The DoublyLinkedList class will have a head attribute that points to the first node of the list. It will also have methods to insert, delete, and traverse the nodes of the list.

Example:

# SlingAcademy.com
# This code uses Python 3.11.4

# Define a Node class
class Node:
    def __init__(self, data):
        self.data = data # Assign data
        self.next = None # Initialize next as None
        self.prev = None # Initialize prev as None

# Define a DoublyLinkedList class
class DoublyLinkedList:
    def __init__(self):
        self.head = None # Initialize head as None

    # Method to insert a new node at the beginning of the list
    def push(self, new_data):
        # Create a new node with the given data
        new_node = Node(new_data)
        # Make the new node's next point to the current head
        new_node.next = self.head
        # Make the current head's prev point to the new node
        if self.head is not None:
            self.head.prev = new_node
        # Make the new node's prev point to None
        new_node.prev = None
        # Make the new node as the new head
        self.head = new_node

    # Method to delete a node from the list
    def delete(self, key):
        # Find the node with the given key
        curr = self.head
        while curr is not None and curr.data != key:
            curr = curr.next
        # If the node is not found, return
        if curr is None:
            return
        # If the node is the head, make the next node as the new head
        if curr == self.head:
            self.head = curr.next
        # If the node is not the last node, make its next node's prev point to its prev node
        if curr.next is not None:
            curr.next.prev = curr.prev
        # If the node is not the first node, make its prev node's next point to its next node
        if curr.prev is not None:
            curr.prev.next = curr.next

    # Method to print the nodes of the list from head to tail
    def print_list(self):
        temp = self.head # Start from the head
        while temp: # Loop until temp is None
            print(temp.data) # Print the data of the current node
            temp = temp.next # Move to the next node

# Create an empty doubly linked list
dllist = DoublyLinkedList()
# Insert some nodes at the beginning of the list
dllist.push(15)
dllist.push(10)
dllist.push(5)
# Print the list
dllist.print_list()
# Output: 5 10 15

# Delete a node from the list
dllist.delete(10)
# Print the list again
dllist.print_list()
# Output: 5 15

Sorting a linked list with merge sort

Sorting a linked list means rearranging the nodes in the list so that their data values are in ascending or descending order. There are different ways to sort a linked list, but we’ll only focus on merge sort in the example to come.

Merge sort is a divide-and-conquer algorithm that recursively splits the list into smaller sublists until each sublist contains only one node, and then merges the sublists in sorted order until the original list is sorted. The main steps of merge sort are:

1. Split the list into two halves by finding the middle node and breaking the links between the two halves.
2. Recursively sort the left and right halves using merge sort.
3. Merge the sorted left and right halves by creating a new head node and comparing the data values of the left and right nodes, and appending the smaller one to the new head node until one of the halves is empty. Then append the remaining nodes of the other half to the new head node.
4. Return the new head node to the sorted list.

This is an example of how to implement merge sort on a linked list in Python:

# SlingAcademy.com
# This code uses Python 3.11.4


# Define a Node class
class Node:
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None  # Initialize next as None


# Define a LinkedList class
class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

    # Method to insert a new node at the end of the list
    def append(self, new_data):
        # Create a new node with the given data
        new_node = Node(new_data)
        # If the list is empty, make the new node as the head
        if self.head is None:
            self.head = new_node
            return
        # Otherwise, traverse to the last node
        last = self.head
        while last.next:
            last = last.next
        # Make the last node's next point to the new node
        last.next = new_node

    # Method to print the nodes of the list
    def print_list(self):
        temp = self.head  # Start from the head
        while temp:  # Loop until temp is None
            print(temp.data, end=" ")  # Print the data of the current node
            temp = temp.next  # Move to the next node
        print()  # Print a newline

    # Method to split a list into two halves by finding the middle node
    def split_list(self, head):
        # If the list is empty or has only one node, return it as it is
        if head is None or head.next is None:
            return head, None
        # Otherwise, use two pointers: slow and fast
        slow = head  # Move one step at a time
        fast = head.next  # Move two steps at a time
        while (
            fast and fast.next
        ):  # Loop until fast reaches the end or one before the end
            slow = slow.next  # Move slow one step forward
            fast = fast.next.next  # Move fast two steps forward
        # Now slow is at the middle node, so break the link between slow and slow.next
        mid = slow.next
        slow.next = None
        # Return the two halves: head to slow, and mid to fast
        return head, mid

    # Method to merge two sorted lists by creating a new head node
    def merge_lists(self, left, right):
        # If either of the lists is empty, return the other one as it is
        if left is None:
            return right
        if right is None:
            return left
        # Otherwise, create a new head node with a dummy value
        head = Node(0)
        # Use a pointer to keep track of the current node of the new list
        curr = head
        while left and right:  # Loop until either of the lists is empty
            if (
                left.data <= right.data
            ):  # If left's data is smaller or equal to right's data
                curr.next = left  # Append left to curr's next
                left = left.next  # Move left one step forward
            else:  # If right's data is smaller than left's data
                curr.next = right  # Append right to curr's next
                right = right.next  # Move right one step forward
            curr = curr.next  # Move curr one step forward
        # If there are any remaining nodes in left or right, append them to curr's next
        if left:
            curr.next = left
        if right:
            curr.next = right
        # Return the next of the head node, which is the actual head of the merged list
        return head.next

    # Method to sort a list using merge sort
    def merge_sort(self, head):
        # If the list is empty or has only one node, return it as it is
        if head is None or head.next is None:
            return head
        # Otherwise, split the list into two halves
        left, right = self.split_list(head)
        # Recursively sort the left and right halves using merge sort
        left = self.merge_sort(left)
        right = self.merge_sort(right)
        # Merge the sorted left and right halves
        head = self.merge_lists(left, right)
        # Return the sorted head node
        return head


# Create an unsorted linked list
llist = LinkedList()
llist.append(15)
llist.append(10)
llist.append(5)
llist.append(20)
llist.append(3)
llist.append(2)

# Print the unsorted list
print("Unsorted list:")
llist.print_list()

# Sort the list using merge sort
llist.head = llist.merge_sort(llist.head)

# Print the sorted list
print("Sorted list:")
llist.print_list()

Output:

Unsorted list:
15 10 5 20 3 2 
Sorted list:
2 3 5 10 15 20 

Afterword

You’ve learned the fundamentals and walked through some practical examples of using linked lists in Python. What are your thoughts on linked lists? Tedious and overcomplicated or interesting and worth knowing about? Please let me know by leaving a comment.