Skip to content
CodeMDD.io | Coding Tutorials

Effortlessly Mastering Linked List in Python

[

Linked Lists in Python: An Introduction

Linked lists are a lesser-known cousin of lists in Python. While not as popular or well-known, they can be incredibly useful in certain contexts. In this tutorial, we will explore what linked lists are, when to use them, and how to implement them in Python. We will also cover some advanced concepts like doubly linked lists and circular linked lists.

Understanding Linked Lists

Linked lists are an ordered collection of objects. What sets them apart from normal lists is how they store elements in memory. In a linked list, each element is called a node, which has two fields: data and next. The data field stores the value to be stored in the node, while the next field contains a reference to the next node in the list.

Here’s an example of what a typical node looks like:

Node
-------------
| data | next |
-------------
|      |      |
-------------

A linked list is a collection of these nodes, with the first node called the “head.” The head serves as the starting point for iterating through the list. The last node in the list has its next field set to None to indicate the end of the list.

Here’s how a linked list looks with multiple nodes:

Linked List
-----------------------------------
| head (node 1) | data | next ---|---> None
-----------------------------------
| node 2        | data | next ---|---> None
-----------------------------------
| node 3        | data | next ---|---> None
-----------------------------------

Now that we understand the basic structure of linked lists, let’s explore some practical applications.

Main Concepts

The main concept behind linked lists is the ability to store and retrieve data in a linked sequence. Each node in the list holds a piece of data and a reference to the next node. This allows for efficient insertion and deletion of elements.

Practical Applications

Linked lists have various real-world applications. Some common use cases include:

  • Implementing stacks and queues: Linked lists are often used to implement these two fundamental data structures. Stacks follow the Last In, First Out (LIFO) principle, while queues operate on the First In, First Out (FIFO) principle.
  • Dynamic memory allocation: Linked lists are essential for managing dynamically allocated memory in programming languages. They allow for efficient memory allocation and deallocation.
  • Graphs and trees: Linked lists are used to implement various graph and tree data structures. For example, linked lists can be used to represent the adjacency list of a graph or the child nodes of a tree.

Linked lists offer flexibility and efficiency in certain scenarios, making them a valuable tool to have in your programming arsenal.

Introducing collections.deque

In Python, the collections module provides a built-in class called deque that can be used to implement linked lists. The deque class is optimized for append and pop operations, making it an efficient choice for implementing stacks and queues.

How to Use collections.deque

To use deque, you need to import it from the collections module. Here’s an example of creating a new deque and adding elements to it:

from collections import deque


my_deque = deque()
my_deque.append(1)
my_deque.append(2)
my_deque.append(3)

You can also use the extend method to add multiple elements at once:

my_deque.extend([4, 5, 6])

To access elements in a deque, you can use indexing, just like with a normal list:

print(my_deque[0])  # Output: 1
print(my_deque[-1])  # Output: 6

How to Implement Queues and Stacks

Since deque is optimized for append and pop operations, it is an excellent choice for implementing queues and stacks. Here’s an example of how to use deque to implement a stack:

from collections import deque


my_stack = deque()
my_stack.append(1)
my_stack.append(2)
my_stack.append(3)


print(my_stack.pop())  # Output: 3
print(my_stack.pop())  # Output: 2
print(my_stack.pop())  # Output: 1

And here’s an example of how to use deque to implement a queue:

from collections import deque


my_queue = deque()
my_queue.append(1)
my_queue.append(2)
my_queue.append(3)


print(my_queue.popleft())  # Output: 1
print(my_queue.popleft())  # Output: 2
print(my_queue.popleft())  # Output: 3

Using deque from the collections module simplifies the implementation of linked lists in Python, especially for use cases like stacks and queues.

Implementing Your Own Linked List

While deque provides a convenient way to implement linked lists, you may still wish to implement your own custom linked list class in Python. Doing so allows for greater control and customization over the linked list’s behavior.

How to Create a Linked List

To create your own linked list, you need to define a class to represent each node and another class to handle the overall linked list.

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

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


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

In this example, the Node class represents each node in the linked list. It has two fields: data to store the value and next to reference the next node in the list. The LinkedList class serves as the overall linked list and has a single field head to mark the start of the list.

How to Traverse a Linked List

To traverse a linked list, you start at the head node and follow the next references until you reach the end of the list.

Here’s an example of how to traverse a linked list in Python:

def traverse_linked_list(linked_list):
    current_node = linked_list.head


    while current_node:
        print(current_node.data)
        current_node = current_node.next

In this example, the traverse_linked_list function takes a LinkedList object as input and iterates through the list, printing each node’s data along the way.

How to Insert a New Node

To insert a new node into a linked list, you need to modify the next references of the existing nodes.

Here’s an example of how to insert a new node at the beginning of a linked list:

def insert_at_beginning(linked_list, data):
    new_node = Node(data)
    new_node.next = linked_list.head
    linked_list.head = new_node

In this example, the insert_at_beginning function takes a LinkedList object and a new data value as input. It creates a new node with the given data and updates the next reference of the new node to point to the current head node. Finally, it updates the head reference to point to the new node.

How to Remove a Node

Removing a node from a linked list involves updating the next references of the surrounding nodes to skip over the node to be removed.

Here’s an example of how to remove a node with a given data value from a linked list:

def remove_node(linked_list, target_data):
    current_node = linked_list.head
    previous_node = None


    while current_node:
        if current_node.data == target_data:
            if previous_node:
                previous_node.next = current_node.next
            else:
                linked_list.head = current_node.next
            break


        previous_node = current_node
        current_node = current_node.next

In this example, the remove_node function takes a LinkedList object and a target data value as input. It traverses the list, searching for a node with the target data. If found, it updates the next reference of the previous node to skip over the current node. If the target node is the head, it updates the head reference accordingly.

Using Advanced Linked Lists

In addition to singly linked lists, it is also possible to use other types of linked lists that offer additional functionality.

How to Use Doubly Linked Lists

A doubly linked list is similar to a singly linked list, but each node has an additional field, previous, which references the previous node in the list.

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

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


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

In this example, each node has a previous field in addition to the next field. The DoublyLinkedList class also keeps track of both the head and tail of the list for easier traversal.

Doubly linked lists are useful when you need to traverse the list in both directions or perform operations like inserting or deleting nodes at both ends of the list.

How to Use Circular Linked Lists

In a circular linked list, the last node’s next reference does not point to None, but instead loops back to the first node, creating a circular structure.

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

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


class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None


    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.tail.next = self.head

In this example, the CircularLinkedList class has a modified append method that creates a new node and updates the next reference of the tail node to the new node. It also updates the next reference of the new tail node to the head node, effectively closing the loop.

Circular linked lists are useful in cases where you need to iterate through a list continuously or need quick access to both the first and last elements.

Conclusion

In this tutorial, we learned about linked lists and their applications in Python. We explored the basic concept of linked lists, practical use cases, and the performance comparison between lists and linked lists. We also discussed how to use the collections.deque class to implement linked lists efficiently. Finally, we covered implementing your own linked list, including creating, traversing, inserting, and removing nodes. We also introduced advanced concepts like doubly linked lists and circular linked lists.

By understanding and mastering linked lists, you have added a powerful tool to your Python toolkit that can improve the efficiency and flexibility of your code. Experiment with different linked list implementations and explore their potential applications in your projects.