Effortlessly Using Linked Lists in Python

Linked Lists in Python: An Introduction

Linked lists are an important data structure in computer science and programming. In this tutorial, you will learn what linked lists are, how to use them in Python, and how to implement your own linked list. We will cover the following topics:

Understanding Linked Lists
- Main Concepts
- Practical Applications
- Performance Comparison: Lists vs Linked Lists
Introducing collections.deque
- How to Use collections.deque
- How to Implement Queues and Stacks
Implementing Your Own Linked List
- How to Create a Linked List
- How to Traverse a Linked List
- How to Insert a New Node
- How to Remove a Node
Using Advanced Linked Lists
- How to Use Doubly Linked Lists
- How to Use Circular Linked Lists
Conclusion

Understanding Linked Lists

Linked lists are a data structure where each element, called a node, contains data and a reference to the next node in the list. This allows for efficient insertion and deletion of elements in the list, unlike traditional lists which require shifting of elements.

Main Concepts

A linked list is made up of nodes, with each node containing two fields: data and next. The data field holds the value to be stored in the node, and the next field holds a reference to the next node in the list. The first node in the list is called the head, and the last node’s next field points to None.

Practical Applications

Linked lists are commonly used in situations where efficient insertion and deletion of elements are important. Some practical applications of linked lists include:

Implementation of stacks and queues
Implementation of graph and tree data structures
Building hash tables and hash maps
Managing dynamic memory allocation

Introducing collections.deque

Python’s built-in collections module provides a deque class, which is a generalization of linked lists with additional functionality. Deques can be used to implement queues and stacks, making them a versatile data structure in Python.

How to Use collections.deque

To use the deque class from the collections module, you need to import it first. Here’s an example of how to create a deque and perform various operations on it:

from collections import deque

# Create a deque
my_deque = deque()

# Add elements to the deque
my_deque.append(1)
my_deque.append(2)
my_deque.append(3)

# Access elements in the deque
print(my_deque[0])  # Output: 1
print(my_deque[2])  # Output: 3

# Remove elements from the deque
my_deque.pop()  # Output: 3
my_deque.popleft()  # Output: 1

How to Implement Queues and Stacks

With the deque class, you can easily implement queues and stacks in Python. Here’s an example of how to implement a queue using a deque:

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        return self.queue.popleft()

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

Implementing Your Own Linked List

To have more control over the linked list operations, you can implement your own linked list class in Python. This allows you to customize the behavior and add additional functionality if needed.

How to Create a Linked List

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

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

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

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

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next

# Create a linked list
my_list = LinkedList()

# Insert elements into the list
my_list.insert(1)
my_list.insert(2)
my_list.insert(3)

# Display the elements in the list
my_list.display()  # Output: 1 2 3

How to Traverse a Linked List

To traverse a linked list, you can start from the head node and iterate through each node, following the next references until you reach the end of the list. Here’s an example:

def traverse_linked_list(linked_list):
    current = linked_list.head
    while current:
        # Do something with the current node
        print(current.data)
        current = current.next

How to Insert a New Node

To insert a new node into a linked list, you can create a new node and update the next reference of the previous node to point to the new node. Here’s an example:

def insert_new_node(linked_list, data):
    new_node = Node(data)
    if linked_list.head is None:
        linked_list.head = new_node
    else:
        current = linked_list.head
        while current.next:
            current = current.next
        current.next = new_node

How to Remove a Node

To remove a node from a linked list, you need to update the next reference of the previous node to skip the node to be removed. Here’s an example:

def remove_node(linked_list, data):
    current = linked_list.head
    previous = None
    while current:
        if current.data == data:
            if previous:
                previous.next = current.next
            else:
                linked_list.head = current.next
            break
        previous = current
        current = current.next

Using Advanced Linked Lists

Apart from the basic linked list, there are also advanced types of linked lists, such as doubly linked lists and circular linked lists.

How to Use Doubly Linked Lists

A doubly linked list is similar to a normal linked list, but each node contains a reference to the previous node as well as the next node. This allows for more efficient traversal in both directions. Here’s an example:

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

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

    def insert(self, data):
        new_node = DoublyNode(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.previous = current

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next

How to Use Circular Linked Lists

A circular linked list is a linked list where the last node’s next reference points back to the head node, creating a circular structure. This allows for continuous traversal of the list. Here’s an example:

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

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

    def insert(self, data):
        new_node = CircularNode(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def display(self):
        current = self.head
        while current.next != self.head:
            print(current.data, end=" ")
            current = current.next
        print(current.data, end=" ")

Conclusion

Linked lists are a useful data structure for certain types of problems where efficient insertion and deletion are required. In this tutorial, you’ve learned what linked lists are, how to use the collections.deque class in Python, and how to implement your own linked list. You’ve also seen examples of advanced linked lists, such as doubly linked lists and circular linked lists. With this knowledge, you can now apply linked lists to solve more complex problems in Python. Happy coding!