Sabbha

Posted on Aug 14

Introduction to Linked Lists in Python: A Comprehensive Guide 🔗

#linkedlist #dsa #datastructures #python

What is a Linked List?

A linked list is a fundamental data structure that consists of a sequence of elements, where each element points to the next one. Unlike arrays, linked lists do not require contiguous memory locations, making them dynamic and flexible in nature. They are widely used in scenarios where frequent insertions and deletions are required.

In this article, we'll explore the concept of linked lists, understand their structure, and implement a simple linked list in Python. By the end, you'll have a solid understanding of how linked lists work and how to use them in your projects.

The Structure of a Linked List

A linked list is composed of nodes. Each node contains:

Data: The actual value or information the node holds.
Next: A reference (or pointer) to the next node in the sequence.

The first node of a linked list is called the head. The last node has a next reference that points to None, indicating the end of the list.

[Data|Next] -> [Data|Next] -> [Data|Next] -> None

Why Use Linked Lists?

Linked lists offer several advantages:

Dynamic Size: They can grow or shrink dynamically, without requiring memory reallocation.
Efficient Insertions/Deletions: Adding or removing elements is more efficient than in arrays, especially when dealing with large datasets.

However, linked lists also come with some drawbacks:

Sequential Access: Accessing an element requires traversing the list from the head, making it slower than arrays for random access.
Memory Overhead: Each element requires extra memory for storing the reference to the next node.

Here's a basic implementation of a singly linked list in Python, along with an explanation of how it works:

Linked List Implementation

Step 1: Creating the Node Class

The first step is to create a Node class. Each Node object will store the data and a reference to the next node.

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

Here, data holds the value of the node, and next is a pointer to the next node in the list.

Step 2: Creating the LinkedList Class

Next, we'll create a LinkedList class to manage the nodes. This class will include methods to add nodes, display the list, and perform various operations.

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

The head attribute represents the starting point of the linked list.

Step 3: Adding Nodes to the Linked List

We can create a method called append to add nodes at the end of the list.

def append(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        return
    last = self.head
    while last.next:
        last = last.next
    last.next = new_node

This method creates a new node and adds it to the end of the list. If the list is empty, the new node becomes the head.

Step 4: Displaying the Linked List

To visualize the linked list, we can create a display method that prints the elements in sequence.

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

This method traverses the list from the head to the last node and prints the data of each node.

Step 5: Finding a Node in the Linked List

We can create a find method to search for a specific value in the list.

def find(self, key):
    current = self.head
    while current:
        if current.data == key:
            return True
        current = current.next
    return False

This method traverses the list and returns True if the value is found, otherwise it returns False.

Step 6: Deleting a Node from the Linked List

We can create a delete method to remove a node with a specific value from the list.

def delete(self, key):
    current = self.head
    prev = None

    # If the node to be deleted is the head
    if current and current.data == key:
        self.head = current.next
        current = None
        return

    # Search for the node to be deleted
    while current and current.data != key:
        prev = current
        current = current.next

    # If the node was not found
    if not current:
        return

    # Unlink the node from the linked list
    prev.next = current.next
    current = None

This method searches for the node with the specified value and removes it from the list. If the node is not found, no action is taken.

Step 7: Inserting Nodes at Specific Positions

Sometimes, you may need to insert a node at a specific position. We can implement an insert method for this purpose.

def insert(self, position, data):
    new_node = Node(data)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
        return

    current = self.head
    prev = None
    current_position = 0

    while current and current_position < position:
        prev = current
        current = current.next
        current_position += 1

    new_node.next = current
    if prev:
        prev.next = new_node

This method allows you to insert a node at any specified position in the list. If the position is 0, the new node becomes the head.

Example Usage

Let's see how these methods work together in a simple example:

# Creating a linked list and appending elements
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(3)
linked_list.append(4)

# Displaying the original list
print("Original List:")
linked_list.display()  # Output: 1 -> 3 -> 4 -> None

# Inserting a node at position 1
linked_list.insert(1, 2)
print("After Inserting 2 at position 1:")
linked_list.display()  # Output: 1 -> 2 -> 3 -> 4 -> None

# Inserting a node at the head
linked_list.insert(0, 0)
print("After Inserting 0 at position 0 (head):")
linked_list.display()  # Output: 0 -> 1 -> 2 -> 3 -> 4 -> None

# Inserting a node at the end
linked_list.insert(5, 5)
print("After Inserting 5 at the end:")
linked_list.display()  # Output: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> None

# Finding a node in the list
print("Finding 3 in the list:")
print(linked_list.find(3))  # Output: True

print("Finding 6 in the list:")
print(linked_list.find(6))  # Output: False

# Deleting a node from the list
linked_list.delete(3)
print("After Deleting 3:")
linked_list.display()  # Output: 0 -> 1 -> 2 -> 4 -> 5 -> None

# Deleting the head node
linked_list.delete(0)
print("After Deleting the head (0):")
linked_list.display()  # Output: 1 -> 2 -> 4 -> 5 -> None

Conclusion

Linked lists are a powerful and flexible data structure, providing efficient operations for insertion, deletion, and searching. While they may not be as fast as arrays for random access, their dynamic nature makes them ideal for scenarios where the size of the data structure is unknown or changes frequently.
In this article, we covered the basics of linked lists, including their structure, benefits, and how to implement them in Python. We also explored essential operations like appending nodes, displaying the list, finding nodes, and deleting nodes.
By practicing with linked lists, you'll gain a deeper understanding of how data structures work, which is essential for writing efficient algorithms and solving complex problems. Whether you're preparing for coding interviews or just looking to improve your programming skills, mastering linked lists is a key step in becoming a proficient developer.