Python Tutorial: How to reverse a linked list in Python

Introduction

Linked lists are one of the most fundamental data structures in computer science. They consist of a sequence of nodes, each containing a value and a pointer to the next node in the list. Unlike arrays, linked lists do not have a fixed size and can be easily modified by adding or removing nodes.

In this tutorial, we will learn how to reverse a linked list in Python. Reversing a linked list means that we need to change the direction of the pointers so that the last node becomes the first node, the second-to-last node becomes the second node, and so on.

Before diving into the implementation, let’s first understand some basic concepts about linked lists and their operations.

What is a linked list?

A linked list is a type of data structure commonly used in computer programming. It consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. The first node is called the head, while the last node is called the tail.

Unlike arrays, linked lists do not have a fixed size and can be easily resized during runtime. This makes them more flexible and efficient when dealing with large amounts of data.

Linked lists are commonly used to implement other data structures such as stacks, queues, and hash tables. They can also be used for tasks such as reversing the order of elements or searching for specific values.

In Python, linked lists can be implemented using classes and objects. Each node in the list can be represented by an object that contains two attributes: the value of the node and a reference to the next node in the sequence.

Here’s an example implementation of a singly linked list in Python:


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

In this example, we define two classes: `Node` and `LinkedList`. The `Node` class represents each node in the linked list, while the `LinkedList` class represents the list itself.

The `Node` class has two attributes: `value`, which stores the value of the current node, and `next`, which stores a reference to the next node in the sequence. The `LinkedList` class has only one attribute: `head`, which stores a reference to the first node in the list (or `None` if the list is empty).

Now that we have covered what a linked list is and how it can be implemented in Python using classes and objects, we can move on to how to reverse a linked list in Python.

Why reverse a linked list?

Linked lists are a fundamental data structure in computer science and are used extensively in many programming applications. A linked list is a collection of elements, known as nodes, that are connected through pointers. Each node contains a value and a pointer to the next node in the list.

There are several situations where reversing a linked list can be useful. For example, if you want to display the elements of a linked list in reverse order, or if you want to implement a stack or queue using a linked list, reversing the list can simplify the implementation.

In addition, reversing a linked list is a common interview question for software engineering positions. It tests your understanding of data structures and algorithms and your ability to write efficient and effective code.

In this tutorial, we will cover how to reverse a linked list in Python using different approaches. We will start with the iterative approach, which involves traversing the list and modifying the pointers to reverse the order of the nodes. We will then discuss the recursive approach, which uses recursive function calls to reverse the list. Finally, we will compare the performance of these two approaches and discuss their advantages and disadvantages.

How to reverse a linked list in Python

Linked lists are a data structure commonly used in programming. They consist of nodes that are linked together in a sequence, where each node contains a value and a reference to the next node in the sequence. In this tutorial, we will learn how to reverse a linked list in Python.

Create a linked list

Before we can reverse a linked list, we first need to create one. We can create a linked list in Python by defining a Node class and then linking instances of this class together.


class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next is not None:
                current_node = current_node.next
            current_node.next = new_node
            
    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.value)
            current_node = current_node.next

In the above code block, we define a Node class with two attributes: `value` which holds the value of the node, and `next` which holds a reference to the next node in the sequence. We also define a LinkedList class which has an attribute `head` that holds the first node in the sequence. The `insert` method allows us to add nodes to the end of the linked list. Finally, we define a `print_list` method which prints out all values in the linked list.

With this code, we can create a linked list as follows:


linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.print_list()

This will output:


1
2
3

Iterative method

The iterative method for reversing a linked list involves iterating through the list and changing the next pointer of each node to point to the previous node. We also need to keep track of the previous and current nodes as we iterate through the list.


def reverse_iterative(head):
    prev_node = None
    current_node = head
    while current_node is not None:
        next_node = current_node.next
        current_node.next = prev_node
        prev_node = current_node
        current_node = next_node
    return prev_node

In the above code block, we define a function `reverse_iterative` which takes the head of a linked list as an argument. We initialize `prev_node` to `None` and `current_node` to `head`. We then iterate through the linked list, setting `next_node` to the next node in the sequence, setting the `next` attribute of `current_node` to point to `prev_node`, and updating `prev_node` and `current_node`. Finally, we return `prev_node`, which is now the new head of the reversed linked list.

We can use this function with our example linked list as follows:


reversed_head = reverse_iterative(linked_list.head)
reversed_list = LinkedList()
reversed_list.head = reversed_head
reversed_list.print_list()

This will output:


3
2
1

Recursive method

The recursive method for reversing a linked list involves recursively calling a function on each node in the sequence. The base case for this recursion is when we reach the last node in the sequence, at which point we set its `next` attribute to point to its previous node.


def reverse_recursive(node):
    if node is None or node.next is None:
        return node
    reversed_head = reverse_recursive(node.next)
    node.next.next = node
    node.next = None
    return reversed_head

In the above code block, we define a function `reverse_recursive` which takes a node as an argument. We check if the node is `None` or if it is the last node in the sequence (i.e., its `next` attribute is `None`). If either of these conditions are true, we simply return the current node. Otherwise, we recursively call `reverse_recursive` on the next node in the sequence and store the returned value as `reversed_head`. We then set the `next` attribute of the next node to point to the current node, set the `next` attribute of the current node to `None`, and return `reversed_head`.

We can use this function with our example linked list as follows:


reversed_head = reverse_recursive(linked_list.head)
reversed_list = LinkedList()
reversed_list.head = reversed_head
reversed_list.print_list()

This will output:


3
2
1

In conclusion, reversing a linked list in Python can be achieved through iterative or recursive methods. By understanding these concepts, you can apply them to other data structures and algorithms in your programming journey.

Conclusion

In this tutorial, we have learned how to reverse a linked list in Python. We started by defining a Node class that represents a single node in the linked list. We then created a LinkedList class that provides methods for inserting nodes at the beginning and printing the linked list. Finally, we implemented the reverse_linked_list() method that uses three pointers to reverse the linked list.

Reversing a linked list is a common problem in computer science interviews and is also useful in real-world applications. It is important to understand the concept of linked lists and how they can be manipulated using Python.

By following this tutorial, you now have a good understanding of how to reverse a linked list in Python. Keep practicing and experimenting with different implementations to further solidify your understanding.
Interested in learning more? Check out our Introduction to Python course!

Pierian Training
Pierian Training
Pierian Training is a leading provider of high-quality technology training, with a focus on data science and cloud computing. Pierian Training offers live instructor-led training, self-paced online video courses, and private group and cohort training programs to support enterprises looking to upskill their employees.

You May Also Like

Data Science, Tutorials

Guide to NLTK – Natural Language Toolkit for Python

Introduction Natural Language Processing (NLP) lies at the heart of countless applications we use every day, from voice assistants to spam filters and machine translation. It allows machines to understand, interpret, and generate human language, bridging the gap between humans and computers. Within the vast landscape of NLP tools and techniques, the Natural Language Toolkit […]

Machine Learning, Tutorials

GridSearchCV with Scikit-Learn and Python

Introduction In the world of machine learning, finding the optimal set of hyperparameters for a model can significantly impact its performance and accuracy. However, searching through all possible combinations manually can be an incredibly time-consuming and error-prone process. This is where GridSearchCV, a powerful tool provided by Scikit-Learn library in Python, comes to the rescue. […]

Python Basics, Tutorials

Plotting Time Series in Python: A Complete Guide

Introduction Time series data is a type of data that is collected over time at regular intervals. It can be used to analyze trends, patterns, and behaviors over time. In order to effectively analyze time series data, it is important to visualize it in a way that is easy to understand. This is where plotting […]