Skip to content
CodeMDD.io | Coding Tutorials

Easily Implement a Linked List in Python

[

Linked Lists using Python

Understanding Linked Lists

Linked lists are an ordered collection of objects that store elements in a different way compared to normal lists. While lists use a contiguous memory block to store references to their data, linked lists store references as part of their own elements. Each element in a linked list is called a node, which consists of two fields: data and next.

Main Concepts

  • Data: Contains the value to be stored in the node.
  • Next: Contains a reference to the next node on the list.

Here’s an example node of a linked list:

A linked list is a collection of these nodes. The first node, known as the head, serves as the starting point for any iteration through the list. The last node’s next reference points to None to determine the end of the list.

Here’s the structure of a linked list:

Practical Applications

Linked lists have a variety of practical applications:

  • Data Structures: Linked lists are useful for implementing data structures like queues and stacks.
  • Graphs and Trees: Linked lists can be used to represent vertices or edges in graph and tree data structures.
  • File Systems: Linked lists can be used to represent the file system’s directory structure.
  • Dynamic Memory Allocation: Linked lists are used in memory allocation techniques like dynamic memory allocation.

Linked lists provide flexibility and efficient memory usage in scenarios where data needs to be dynamically added or removed.

Performance Comparison: Lists vs Linked Lists

When comparing the performance of lists and linked lists, there are some key differences to consider:

  • Accessing Elements: Lists provide constant time access to elements, while linked lists require traversing the list to find the desired element, resulting in linear time access.
  • Insertion and Deletion: Lists require shifting elements to make room for new elements or to fill gaps after deletion, resulting in potentially costly operations. Linked lists, on the other hand, can efficiently insert or delete elements by updating the references of the adjacent nodes.
  • Memory Usage: Linked lists only use memory for the elements they contain and their reference fields, while lists use additional memory for maintaining the contiguous block of references.

The choice between lists and linked lists depends on the specific requirements of the problem at hand. If fast access to elements is crucial, lists may be more suitable. However, if efficient insertion and deletion operations are required, linked lists offer a better alternative.

Introducing collections.deque

In Python, the collections module provides a data structure called deque that can be used as a linked list. The deque implements a double-ended queue, allowing efficient insertion and deletion from both ends.

How to Use collections.deque

Here’s an example of how to use collections.deque as a linked list:

from collections import deque


# Create a deque instance
linked_list = deque()


# Append elements to the linked list
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)


# Iterate through the linked list
for element in linked_list:
    print(element)

Output:

10
20
30

The deque provides methods like append, appendleft, pop, and popleft to add or remove elements from the linked list at either end.

Implementing Your Own Linked List

While the deque from collections is a convenient way to use linked lists in Python, you can also implement your own linked list data structure. Here’s a step-by-step guide on how to create and operate on a linked list:

How to Create a Linked List

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


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

To create a linked list, define a Node class that contains the data and next fields. The LinkedList class represents the overall linked list structure and contains a head attribute that points to the first node.

How to Traverse a Linked List

class LinkedList:
    # ...


    def traverse(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

To traverse a linked list, initialize a current variable to the head node and iterate through the list by moving the current variable to the next node until it reaches the end.

How to Insert a New Node

class LinkedList:
    # ...


    def insert(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

To insert a new node at the end of the linked list, create a new node with the given data and check if the head is empty. If it is, assign the new node as the head. Otherwise, traverse the list to the last node and update its next reference to the new node.

How to Remove a Node

class LinkedList:
    # ...


    def remove(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
        else:
            current = self.head
            while current.next:
                if current.next.data == data:
                    current.next = current.next.next
                    break
                current = current.next

To remove a node with a specific data value from the linked list, check if the head is empty. If it is, return. If the head’s data matches the given data, update the head to the next node. Otherwise, traverse the list and remove the node by updating the appropriate references.

Using Advanced Linked Lists

In addition to the basic linked list, Python supports advanced linked list variations. Two commonly used variations are doubly linked lists and circular linked lists.

How to Use Doubly Linked Lists

Doubly linked lists extend the functionality of a standard linked list by including a previous field in each node. This allows for efficient traversal in both directions. The implementation of a doubly linked list is similar to a standard linked list, with some additional fields and methods.

How to Use Circular Linked Lists

Circular linked lists have their last node’s next reference pointing back to the head, creating a circular structure. This allows for seamless iteration from the last node to the first node. To implement a circular linked list, ensure the last node’s next reference points to the head.

Conclusion

Linked lists provide a flexible and efficient approach to storing and manipulating data in specific scenarios. Whether you’re working on data structures, graphs, or dynamic memory allocation, linked lists can be a valuable tool in your Python programming arsenal.