Exploring Linked Lists in Python: Implementation and Operations

Introduction

Linked lists are fundamental data structures used in computer science and programming to store and organize data efficiently. They consist of a series of nodes, where each node contains both data and a reference (or pointer) to the next node in the sequence. This data structure provides a flexible way to manage collections of data, especially when the size of the data is unknown or can change dynamically.

In this article, we will explore linked lists, their advantages, how to implement them in Python, and several operations related to linked lists.

Advantages of Linked Lists

1. Dynamic Size: Unlike arrays, linked lists can easily grow or shrink in size since they don’t require a fixed amount of memory. This makes them ideal for scenarios where the size of the data may change frequently.

2. Efficient Insertions and Deletions: Inserting or deleting elements in a linked list is efficient as it only involves updating the references, unlike arrays where elements may need to be shifted.

3. Memory Management: Linked lists utilize memory efficiently by allocating memory for each node separately when needed. This contrasts with arrays that often need to allocate memory for a fixed size, potentially wasting unused space.

4. Easy to Implement: Linked lists are relatively simple to implement, making them a good choice for understanding the basics of data structures.

Linked List Components

Before we dive into implementation, let’s understand the components of a linked list:

1. Node: A node is a fundamental building block of a linked list. It contains two fields:

  • Data: Holds the value or information that the node stores.
  • Next: A reference or pointer to the next node in the sequence.

2. Head: The first node in the linked list.

3. Tail: The last node in the linked list. Its “next” field typically points to None, indicating the end of the list.

A linked list with four nodes, illustrating the components of linked lists.

Implementing a Linked List in Python

We will create a simple singly linked list with the ability to add elements at the end of the list. Let’s start by defining the Node class:


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

Next, we will create the `LinkedList` class, which will handle the operations on the linked list:


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

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

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

Using the Linked List

Now that we have our implementation, let’s use our linked list:


# Create a new linked list
my_list = LinkedList()

# Add elements to the list
my_list.append(10)
my_list.append(20)
my_list.append(30)

# Display the list
my_list.display()

Output


10 -> 20 -> 30

Insert Data to a Linked List

To add data to different positions in a linked list, we need to modify our `LinkedList` class to include methods for inserting elements at the beginning, at a specific position, and at the end of the list. Let’s extend our previous implementation to include these functionalities:


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


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

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

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_position(self, position, data):
        if position <= 0:
            self.prepend(data)
        else:
            new_node = Node(data)
            current = self.head
            prev = None
            count = 0
            while current and count < position:
                prev = current
                current = current.next
                count += 1
            prev.next = new_node
            new_node.next = current

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

Using the Linked List

Now, let’s use our updated linked list and add elements to different positions:


# Create a new linked list
my_list = LinkedList()

# Append elements to the list
my_list.append(20)
my_list.append(30)
my_list.append(40)

# Display the list
print("Initial Linked List:")
my_list.display()

# Add elements at the beginning
my_list.prepend(10)
my_list.prepend(5)

# Display the updated list
print("nAfter Prepend:")
my_list.display()

# Add elements at specific positions
my_list.insert_at_position(2, 25)
my_list.insert_at_position(4, 35)

# Display the final list
print("nAfter Insertion:")
my_list.display()

Output


Initial Linked List:
20 -> 30 -> 40

After Prepend:
5 -> 10 -> 20 -> 30 -> 40

After Insertion:
5 -> 10 -> 25 -> 20 -> 35 -> 30 -> 40

Remove Data from a Linked List

To remove data from different positions in a linked list, we’ll extend our existing `LinkedList` class by adding methods to remove elements from the beginning, a specific position, and the end of the list. Let’s update our implementation accordingly:


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


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

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

    def remove_from_beginning(self):
        if not self.head:
            return
        self.head = self.head.next

    def remove_at_position(self, position):
        if not self.head:
            return
        current = self.head
        prev = None
        count = 0
        while current and count < position:
            prev = current
            current = current.next
            count += 1
        if not current:
            return
        prev.next = current.next

    def remove_from_end(self):
        if not self.head:
            return
        current = self.head
        prev = None
        while current.next:
            prev = current
            current = current.next
        if not prev:
            self.head = None
        else:
            prev.next = None

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

Using the Linked List

Let’s demonstrate how to remove elements from different positions in the linked list:


# Create a new linked list
my_list = LinkedList()

# Append elements to the list
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.append(40)
my_list.append(50)

# Display the list
print("Initial Linked List:")
my_list.display()

# Remove element from the beginning
my_list.remove_from_beginning()

# Display the updated list
print("nAfter Removing from the Beginning:")
my_list.display()

# Remove element from a specific position
my_list.remove_at_position(1)

# Display the updated list
print("nAfter Removing at Position 1:")
my_list.display()

# Remove element from the end
my_list.remove_from_end()

# Display the final list
print("nAfter Removing from the End:")
my_list.display()

Output


Initial Linked List:
10 -> 20 -> 30 -> 40 -> 50

After Removing from the Beginning:
20 -> 30 -> 40 -> 50

After Removing at Position 1:
20 -> 40 -> 50

After Removing from the End:
20 -> 40

Update a Linked List

To update data in a linked list, we need to modify the value of an existing node. We’ll extend the `LinkedList` class by adding a method to update data at a specific position in the list. Here’s the updated implementation:


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

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

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

    def update_at_position(self, position, new_data):
        if not self.head:
            return
        current = self.head
        count = 0
        while current and count < position:
            current = current.next
            count += 1
        if not current:
            return
        current.data = new_data

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

Using the Linked List

Now, let’s demonstrate how to update data at a specific position in the linked list:


# Create a new linked list
my_list = LinkedList()

# Append elements to the list
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.append(40)
my_list.append(50)

# Display the list
print("Initial Linked List:")
my_list.display()

# Update data at position 2
my_list.update_at_position(2, 35)

# Display the updated list
print("nAfter Updating at Position 2:")
my_list.display()

Output


Initial Linked List:
10 -> 20 -> 30 -> 40 -> 50

After Updating at Position 2:
10 -> 20 -> 35 -> 40 -> 50

Summary

In this tutorial, we explored the concept of linked lists and their implementation in Python. Linked lists are fundamental data structures used in computer science to efficiently store and manage data. They consist of a series of nodes, where each node contains both data and a reference to the next node in the sequence.

We began by discussing the advantages of linked lists, including their dynamic size, efficient insertions and deletions, and memory management. These advantages make linked lists suitable for scenarios where the size of data may change frequently and when efficient memory usage is essential.

Next, we delved into the implementation of a simple singly linked list in Python. The implementation involved creating a Node class that represents each element of the list, and a `LinkedList` class responsible for handling various operations on the list, such as appending, prepending, and inserting at a specific position. We demonstrated how to use the linked list to add, remove, update, and display elements effectively.

Throughout the article, we provided code examples and explanations for each operation, allowing readers to grasp the fundamental concepts behind linked lists and gain practical knowledge of their implementation.

Share your love
Subhankar Rakshit
Subhankar Rakshit

Hey there! I’m Subhankar Rakshit, the brains behind PySeek. I’m a Post Graduate in Computer Science. PySeek is where I channel my love for Python programming and share it with the world through engaging and informative blogs.

Articles: 194