Saurabh Rai

for SWIRL

Posted on Nov 10, 2023

[Python 🐍 Mastery] Overview of Linked List in Python & Essential Linked List Operations 🛠️

#python #tutorial #beginners #programming

In the last article, we learned about Object Oriented Programming and had a mountain overview of Python's Magic/Dunder methods.

Object-Oriented Programming (OOP) in Python: This paradigm in Python revolves around creating reusable code. It involves using classes as blueprints for objects. These objects can have attributes (data) and methods (functions) that define their behavior and interactions.

Python's Magic/Dunder Methods: Magic or Dunder (double underscore) methods in Python are special methods with names that start and end with double underscores (e.g., __init__, __str__, __repr__).

You'll be able to read about it here. 👇

[Python 🐍 Mastery] Python's Object-Oriented Programming Overview and Fundamentals ⭐️

Saurabh Rai for SWIRL ・ Oct 27 '23

#beginners #python #programming #tutorial

Today, we will expand upon it and use the knowledge of Object Oriented Programming to understand and create Linked Lists in Python. And will perform some operation on it.

Open Source Python Project: Swirl

If you're interested in Python, you will 💖 Swirl. Swirl is an open-source search platform which will give you knowledge of the following:

Python
Artificial Intelligence
Integrating Large Language Models in any product
Learn how to develop a search platform.

Check our GitHub Repository:
Swirl on GitHub

We'll be delighted if you could:

Give ⭐ to Swirl

Linked List

Linked lists are an ordered collection of objects. It's a data structure designed to hold data in a non-contiguous memory block.

Unlike arrays or traditional lists that use contiguous memory blocks, linked lists are stored in non-contiguous memory locations. This design allows for efficient insertions and deletions without rearranging the entire data structure.

This design allows for efficient insertions and deletions without the need to rearrange the entire data structure.

Basic Linked List

A basic linked list is a linear data structure where each element, known as a node, contains two parts: data and a reference to the next node in the list. This structure allows for efficient insertion and deletion of elements, as it does not require shifting elements, unlike in an array.

A typical node design:
Data: This contains the data, which can be numeric, address, text, etc.
Next: This points to the next data node or holds the address for the next data node.

The first node is called the head of the list, and the last node, which points to None (in Python) (or Null in other Languages), is known as the tail.

When you collect a lot of nodes together, it becomes a linked list.

Benefits of Linked Lists & Time Complexity of Operations

Linked lists offer several benefits, particularly in dynamic data manipulation scenarios. Here are some key advantages:

Dynamic Size: Unlike arrays, linked lists can grow or shrink in size dynamically, which is efficient for memory usage.
Ease of Insertion/Deletion: Inserting or deleting nodes is relatively simple, as it generally only involves changing a few references without shifting elements as in an array.
Flexibility: They can implement other data structures like stacks, queues, and graph adjacency lists.

Operation	Time Complexity
Access	O(n)
Search	O(n)
Insertion	O(1)
Deletion	O(1)

Note: We're taking into account a singly linked list.

Implementing a Linked List in Python.

This is the code that will create a Node in Python. Please note, if you are confused about the __repr__ method. Please check the previous article in this series.

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

    def __repr__(self):
        return f"Node({self.data})"

Code for the Linked List Class. This utilizes the Node class cleared about to create data and link the all together.

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

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

    def __repr__(self):
        nodes = []
        current = self.head
        while current:
            nodes.append(repr(current))
            current = current.next
        return "->".join(nodes)

This code does two things:

Append: Append a node at the end of the linked list.
__repr__ : This method traverses the linked list and prints it in a Pythonic Way.
1. This can also be done using a method called traverse.

This is the output of print(llist) which called `repr_` method:

Traversing a Linked List.

Traversing a linked list is the process of going through each node and printing it.

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


llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)

print("Traversing the linked list:")
traverse(llist)

Reversing a Linked List

The idea is to iterate through the linked list and, for each node, switch its next pointer to point to the previous node instead of the next one. This will help us reverse the linked list.

def reverse_linked_list(head):
    previous = None
    current = head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    return previous

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
print("Original List:", llist)

new_head = reverse_linked_list(llist.head)
llist.head = new_head
print("Reversed List:", llist)

Inserting Values in a Linked List

We already have an append function that adds a value to the end of the linked list. But what if we want to have a method that adds at a specific location, and if that location is not present then append the value at the end.

class LinkedList:

    def insert_after_value(self, data_after, data_to_insert):
        if self.head is None:
            return

        current = self.head
        while current:
            if current.data == data_after:
                new_node = Node(data_to_insert)
                new_node.next = current.next
                current.next = new_node
                return
            current = current.next

        self.append(data_to_insert)

Deleting a Node in a Linked List

To delete a node from a linked list, create a function that takes the head of the list and the node's data to be deleted as arguments. And traverse the list till the data is found, and then delete it.

class LinkedList:

    def delete_node(self, data):
        current = self.head

        if current is None or current.data == data:
            self.head = current.next if current else None
            return

        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next