Python Program For Linked List (Append, Remove, Search, Traverse)

In this tutorial, you will learn about the python program for linked list.

In this article, we will explore the concept of linked lists and how to implement them in Python.

A linked list is a data structure that consists of a sequence of nodes, where each node contains data and a reference to the next node in the sequence.

Unlike arrays, linked lists do not require contiguous memory allocation.

This flexibility makes linked lists suitable for dynamic data structures where the size can change during program execution.

Let’s dive into the details of implementing a Python program for a linked list and explore its various operations.

A linked list is a data structure where elements are stored in separate objects called nodes.

Each node contains both the data and a reference to the next node in the sequence.

The last node in the list points to None, indicating the end of the list.

The first node in the list is called the head.

To implement a linked list in Python, we need to create two classes: Node and LinkedList.

The Node class represents a single node in the list.

While the LinkedList class manages the overall list.

Python Program For Linked List

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

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

Let’s break down the implementation into various operations.

Creating a Linked List

To create an empty linked list, we initialize the head as None.

linked_list = LinkedList()

Adding Elements to the Linked List

To add elements to the linked list, we need to create new nodes.

After creating the new node, we have to update the references accordingly.

Python Program For Linked List

def append(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

Searching an Element in the Linked List

To search for an element in the linked list, we traverse through the nodes until we find a match or reach the end of the list.

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

Removing an Element: Python Program For Linked List

To remove an element from the linked list, we need to update the references of the previous and next nodes accordingly.

def remove(self, data):
    current = self.head
    previous = None
    while current:
        if current.data == data:
            if previous:
                previous.next = current.next
            else:
                self.head = current.next
            return
        previous = current
        current = current.next

Traversing: Python Program For Linked List

To print the linked list, first we have to traverse it.

Traversal means to access the each node of the linked list.

Accessing each node help us to print the data that is stored in that node.

Here is the implementation of the traversal.

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

Let’s consider an example to illustrate the usage of a linked list in Python.

We will create a linked list and perform various operations on it.

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 self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

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

    def remove(self, data):
        current = self.head
        previous = None
        while current:
            if current.data == data:
                if previous:
                    previous.next = current.next
                else:
                    self.head = current.next
                return
            previous = current
            current = current.next

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

# Example usage
linked_list = LinkedList()
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)
linked_list.append(40)

linked_list.traverse()  # Output: 10 20 30 40

print(linked_list.search(20))  # Output: True

linked_list.remove(30)

print(linked_list.search(30))  # Output: False

linked_list.traverse()  # Output: 10 20 40

You can run this code on our free Online Python Compiler.

Q1: How is a linked list different from an array?

A linked list differs from an array in several ways.

Unlike arrays, linked lists do not require contiguous memory allocation.

Linked lists also allow efficient insertion and deletion operations at any position.

However, arrays provide faster access to elements based on index, while linked lists require traversing the list from the beginning to access an element.

Q2: What is the time complexity of various linked list operations?

The time complexity of various linked list operations depends on the specific operation. Here are the time complexities of some common operations:

• Accessing an element by index: O(n)
• Insertion at the beginning: O(1)
• Insertion at the end: O(n)
• Deletion at the beginning: O(1)
• Deletion at the end: O(n)

Q3: Can a linked list contain duplicate elements?

Yes, a linked list can contain duplicate elements. Each node in the linked list can hold any data, including duplicate values.

Q4: Can a linked list be empty?

Yes, a linked list can be empty. An empty linked list has its head attribute set to None.

Q5: Is it possible to convert a linked list into an array in Python?

Yes, it is possible to convert a linked list into an array in Python.

You can traverse through the linked list and append each element to a Python list using a loop.

Q6: Are linked lists used in real-world applications?

Linked lists find applications in various real-world scenarios.

They are often used in memory management systems, file systems, and implementations of other data structures like stacks and queues.

In this article, we explored the concept of linked lists and implemented a Python program for a linked list.

We discussed the basic operations like adding elements, searching, and removing elements from the linked list.

Linked lists are a powerful data structure that offers flexibility and efficient dynamic memory allocation.

By understanding the implementation and operations of a linked list, you can leverage this data structure to solve a wide range of problems efficiently.