Mastering Linked Lists In Python From Zero To Hero

Linked Lists in Python

In the world of programming, data structures play a crucial role in organizing and managing data efficiently. One such fundamental data structure is the Linked List in python.While arrays and lists are common, linked lists provide a unique way to store data, especially when the size of the data is unpredictable or when frequent insertions and deletions are required. In this article, we’ll explore what a linked list is, how it works in Python, and how to implement and manipulate it using Python code.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are stored in a sequence. Unlike arrays, where elements are stored in contiguous memory locations, linked lists store each element in a separate object called a node. Each node contains two parts:

Data: The value or data stored in the node.
Reference (or Pointer): A reference to the next node in the sequence.

The last node in the list points to None, indicating the end of the list. This structure allows linked lists to grow or shrink dynamically, making them more flexible than arrays.

Types of Linked Lists

Linked Lists in Python come in various forms, each with different characteristics:

Singly Linked List: In this type, each node points to the next node in the sequence. The last node points to None.
Doubly Linked List: Each node in a doubly linked list has two pointers, one to the next node and one to the previous node. This allows traversal in both directions.
Circular Linked List: In a circular linked list, the last node points back to the first node, creating a circular structure.

For this article, we’ll focus on implementing a singly linked list in Python.

Implementing a Singly Linked List in Python

To implement a linked list in Python, we’ll start by defining a class for the nodes and then a class for the linked list itself.

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

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

    def is_empty(self):
        return self.head is 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 prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_after_node(self, prev_node, data):
        if not prev_node:
            print("Previous node is not in the list")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    def delete_node(self, key):
        current_node = self.head

        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return

        prev = None
        while current_node and current_node.data != key:
            prev = current_node
            current_node = current_node.next

        if current_node is None:
            return

        prev.next = current_node.next
        current_node = None

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

Breakdown of the Implementation

Node Class: The Node class is the building block of theLinked Lists in Python. It initializes with data and a next pointer that initially points to None.
LinkedList Class: The LinkedList class manages the nodes and provides methods to manipulate the list:
- __init__: Initializes an empty list with head pointing to None.
- is_empty: Checks if the list is empty.
- append: Adds a node with the given data at the end of the list.
- prepend: Adds a node at the beginning of the list.
- insert_after_node: Inserts a node after a given node.
- delete_node: Deletes the first node with the given data.
- print_list: Prints the entire list in a readable format.

Example Usage of the Linked List

Let’s see how we can use our Linked Lists in Python class to create and manipulate a linked list.

# Create a linked list
linked_list = LinkedList()

# Append nodes
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")
linked_list.print_list()  # Output: A -> B -> C -> None

# Prepend a node
linked_list.prepend("D")
linked_list.print_list()  # Output: D -> A -> B -> C -> None

# Insert after a specific node
linked_list.insert_after_node(linked_list.head.next, "E")
linked_list.print_list()  # Output: D -> A -> E -> B -> C -> None

# Delete a node
linked_list.delete_node("B")
linked_list.print_list()  # Output: D -> A -> E -> C -> None

Advantages and Disadvantages of Linked Lists

Advantages:

Dynamic Size: Unlike arrays, Linked Lists in Python can grow and shrink in size dynamically without requiring memory reallocation.
Ease of Insertion/Deletion: Inserting or deleting elements in a linked list is easier compared to arrays, especially when working with large datasets.

Disadvantages:

Memory Overhead: Each node requires extra memory for storing the reference to the next node.
Sequential Access: Linked lists do not allow random access to elements like arrays. To access an element, you need to traverse the list from the beginning.

Common Operations on Linked Lists

Let’s delve into some common operations you might need to perform on a Linked Lists in Python:

Reversing a Linked List: Reversing a linked list is a common problem. Let’s see how to do this:

def reverse_list(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

Finding the Middle of a Linked List: You can find the middle of a linked list using a slow and fast pointer technique.

def find_middle(self):
    slow = self.head
    fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data

Detecting a Loop in a Linked List: A linked list might have a cycle, where a node points back to a previous node. You can detect this using Floyd’s cycle-finding algorithm.

def has_cycle(self):
    slow = self.head
    fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Real-World Applications of Linked Lists

Linked lists are used in various real-world applications where dynamic data storage and efficient insertion/deletion are required:

Implementing Stacks and Queues: Linked lists are often used to implement stack and queue data structures due to their efficient insertion and deletion operations.
Memory Management: Linked lists are used in operating systems for dynamic memory allocation, where blocks of memory are allocated and deallocated frequently.
Graph Representation: Adjacency lists in graph theory are implemented using linked lists, where each vertex has a linked list of its adjacent vertices.
Browser History: Linked lists can be used to implement a web browser’s history feature, allowing users to move back and forth between visited pages.

Conclusion

Linked lists are a fundamental data structure that provides flexibility in data management. Their dynamic nature allows for efficient insertion and deletion, making them ideal for certain applications. However, they also come with challenges, such as higher memory overhead and sequential access. Understanding linked lists and their operations is crucial for any programmer, as they form the basis for more complex data structures and algorithms.

By implementing linked lists in Python, as demonstrated in this article, you can gain hands-on experience with this essential data structure, enhancing your problem-solving skills and preparing you for more advanced topics in computer science.

FAQS

What is the difference between a linked list and an array in Python?

An array stores elements in contiguous memory locations, allowing for constant-time access to elements using an index. In contrast, a linked list stores elements in separate nodes, with each node pointing to the next. This means accessing an element in a linked list requires traversal from the head of the list, making access time linear. However, linked lists are more flexible in terms of size, allowing for efficient insertions and deletions without the need for memory reallocation.

When should I use a linked list over a Python list?

You should consider using a linked list when you need a dynamic data structure that can grow and shrink efficiently with frequent insertions and deletions, especially at the beginning or middle of the list. Linked lists are also useful when memory allocation is a concern, as they do not require contiguous memory like Python lists. However, if you need fast access to elements via indexing, a Python list (which is essentially a dynamic array) may be more suitable.

How do I detect and remove a loop in a linked list?

To detect a loop in a linked list, you can use Floyd’s Cycle-Finding Algorithm, which employs two pointers (slow and fast). If the slow pointer and fast pointer meet at some point, a loop exists. To remove the loop, once a loop is detected, reset one pointer to the head and move both pointers one step at a time until they meet again at the start of the loop. The node just before this meeting point is where you should remove the loop by setting its next pointer to None.

Can I use built-in Python data types to create a linked list?

While Python’s built-in list type can perform many of the operations of a linked list, such as appending and removing elements, it is implemented as a dynamic array, not a linked list. If you specifically need a linked list, you would need to implement it yourself using classes, as shown in the article. This custom implementation allows you to have full control over the structure and behavior, such as handling nodes and pointers explicitly, which is not possible with Python’s built-in list.

NOTE: you can also read these articles

Mastering Linked Lists in Python From zero to hero

Table of Contents