Table of contents
1.
Introduction
2.
What is a Linked List in Python?
3.
Creating a Linked List in Python
4.
Creating a Node Class
5.
Insertion in a Linked List
5.1.
Insertion at Beginning in a Linked List
5.2.
Insert a Node at a Specific Position in a Linked List
5.3.
Insertion in a Linked List at End
6.
Update the Node of a Linked List
7.
Delete Node in a Linked List
7.1.
Remove First Node from Linked List
7.2.
Remove Last Node from Linked List
7.3.
Delete a Linked List Node at a Given Position
7.4.
Delete a Linked List Node of a Given Data
8.
Linked List Traversal in Python
8.1.
Get Length of a Linked List in Python
9.
Example of a Linked List in Python
9.1.
Python
10.
Frequently Asked Questions
10.1.
What is the time complexity of accessing an element in a linked list?
10.2.
Can linked lists contain different data types in Python?
10.3.
Why would you use a linked list over an array?
11.
Conclusion
Last Updated: Jun 2, 2024
Easy

Linked List in Python

Author Pallavi singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Linked lists are an essential data structure used widely in computer programming to manage collections of elements. Unlike traditional arrays, linked lists are dynamic, allowing for efficient insertions and deletions. In Python, implementing linked lists can be particularly straightforward due to the language's built-in features that support dynamic data types and memory management. In this article we will learn the concept of linked lists, discuss their advantages over other data structures, and show how to implement them in Python. 

Linked List in Python

We'll cover everything from creating a basic linked list to performing complex operations such as inserting and deleting nodes. 

What is a Linked List in Python?

A linked list is a sequence of data elements, which are connected together via links. Each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library. However, they can be built from scratch using custom classes. The simplest form of a linked list can be visualized as a chain of nodes, where each node contains data and a reference (or link) to the next node in the sequence. 

Representation of Linked Lists

This structure allows for efficient insertion and removal of elements without reorganizing the entire data structure, which is a common drawback in sequential data structures like arrays.

Creating a Linked List in Python

To create a linked list in Python, you start by defining a Node class. This class will represent the individual elements of the linked list. Each node object will have two attributes: data, which stores the value of the node, and next, which will point to the next node in the list.

Here's a simple example of how to define this Node class:

class Node:
    def __init__(self, data):
        self.data = data  # Assign the data to this node
        self.next = None  # Initialize the next pointer to None


With the Node class defined, you can now create the LinkedList class that will handle the operations of the linked list, such as adding nodes and displaying the list. Here’s a basic structure for the LinkedList class:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize the head of the list to None

    def append(self, data):
        new_node = Node(data)  # Create a new node with the provided data
        if self.head is None:
            self.head = new_node  # If the list is empty, set the new node as the head
        else:
            last_node = self.head
            while last_node.next:
                last_node = last_node.next  # Traverse to the last node
            last_node.next = new_node  # Point the last node's next to the new node

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


This LinkedList class starts with an empty head and grows as new nodes are appended. The append method adds a new node at the end of the list, and print_list provides a way to display the contents of the entire list.

Creating a Node Class

The foundation of a linked list in Python is the Node class. This class is designed to store the individual elements of the list, each encapsulating the data and a reference to the next node. Here’s how you can create a basic Node class in Python:

class Node:
    def __init__(self, data):
        self.data = data  # Store the data passed to the node
        self.next = None  # Initialize the next pointer to None, indicating the end of the list here


In this implementation:

  • The __init__ method initializes a new instance of a Node. It takes data as a parameter, which represents the data stored in the node.
     
  • self.data is used to hold the data within the node.
     
  • self.next is a pointer that will eventually point to the next node in the linked list. Initially, it is set to None, which is useful for the end of the list or when the node is the only element in the list.

Insertion in a Linked List

Inserting a new node into a linked list can be done in several ways, depending on where you want to place the new node: at the beginning, at a specific position, or at the end of the list. Each method has its own procedure:

Insertion at Beginning in a Linked List

Inserting a node at the beginning of a linked list is one of the simplest and fastest operations. This operation changes the head of the list to the new node and links it to the previous head. 

Here’s how you can implement this in Python:

def insert_at_beginning(self, data):
    new_node = Node(data)  # Create a new node with the given data
    new_node.next = self.head  # Link the new node's next to the current head
    self.head = new_node  # Update the head to be the new node


This method works as follows:

  • Create a New Node: A new node is created with the data provided.
     
  • Set Next of New Node: The next attribute of the new node is set to the current head of the linked list, effectively pointing to all the existing nodes.
     
  • Update Head: The head of the linked list is updated to this new node, making it the first node in the list.
     

Note -: By using this method, the new node becomes the first node of the linked list, and the operation is completed in constant time, O(1), since it involves a few assignments and does not depend on the size of the linked list.

Insert a Node at a Specific Position in a Linked List

To insert a node at a specific position within a linked list, you must handle several steps carefully to maintain the integrity of the list. Let’s see how to perform this operation in Python:

def insert_at_position(self, data, position):
    if position == 0:
        self.insert_at_beginning(data)  # Handle the special case of inserting at the beginning
        return
    new_node = Node(data)  # Create a new node
    current = self.head
    # Traverse the list to find the node before the desired position
    for i in range(position - 1):
        if current is None:
            raise Exception("Position out of bounds")  # If the position is greater than the number of nodes
        current = current.next
    new_node.next = current.next  # Link the new node to the next node of the current node
    current.next = new_node  # Insert the new node after the current node


This method allows you to insert a node anywhere in the list, not just at the beginning or end. 

Here are the steps broken down:

  • Special Case for Beginning: If the specified position is 0, the node is inserted at the beginning using the previously defined method.
     
  • Node Creation: A new node containing the data is created.
     
  • Traversal: The list is traversed until the node just before the desired position is reached.
     
  • Insertion: The next attribute of the new node is linked to the next node of the current node, and then the current node's next is updated to the new node.


Note : This approach ensures that the new node is correctly positioned, and all links are appropriately established to keep the list's structure intact.

Insertion in a Linked List at End

Adding a node to the end of a linked list involves appending the new node after the last node in the list. This operation ensures that the new node becomes the new tail of the list. Here’s how you can implement this functionality in Python:

def append(self, data):
    new_node = Node(data)  # Create a new node with the given data
    if self.head is None:
        self.head = new_node  # If the list is empty, this new node becomes the head
        return
    last = self.head
    while last.next:
        last = last.next  # Traverse to the last node of the list
    last.next = new_node  # Make the last node's next point to the new node


This method works as follows:

  • Node Creation: A new node is created and initialized with the provided data.
     
  • Check for Empty List: If the list does not have any nodes (i.e., head is None), the new node is set as the head of the list.
     
  • Traversal to the End: The method traverses from the head to the last node of the list (the node that has None as its next).
     
  • Linking to the Last Node: The last node’s next pointer is updated to point to the new node, thereby adding it to the end of the list.
     

Note : Appending a node in this manner ensures that the linked list maintains a continuous chain from the head to the tail, with the operation typically running in O(n) time due to the traversal of the list.

Update the Node of a Linked List

Updating a node in a linked list involves changing the data of one of the nodes in the list. This operation can be useful when you need to modify the content of the list without altering the overall structure. Let’s see the implementation of node updating in a linked list using Python:

def update_node(self, position, new_data):
    if position < 0:
        raise ValueError("Position must be a non-negative integer")
    current = self.head
    # Traverse to the desired position
    for i in range(position):
        if current is None:
            raise IndexError("Position out of bounds")  # Position exceeds the length of the list
        current = current.next
    if current is None:
        raise IndexError("Position out of bounds")
    current.data = new_data  # Update the node's data with new data


In this method:

  • Input Validation: It first checks if the provided position is non-negative.
     
  • Traversal: The method traverses the list to reach the node at the specified position.
     
  • Data Update: If the node exists, its data is updated with the new data provided.
     

Note : This approach ensures that the data of a specific node is modified correctly while keeping the links between nodes intact, maintaining the integrity of the list's structure.

Delete Node in a Linked List

Deleting a node from a linked list is a key operation that involves removing a node from the list and ensuring that the remaining nodes are still properly connected. Here’s how you can implement node deletion in a Python linked list:

def delete_node(self, key):
    current = self.head
    previous = None
    # If the node to be deleted is the head node
    if current is not None and current.data == key:
        self.head = current.next  # Move the head to the next node
        return
    # Search for the node to be deleted, keep track of the previous node
    while current is not None and current.data != key:
        previous = current
        current = current.next
    # If the node was not found
    if current is None:
        return "The data is not present in the list."
    # Unlink the node from the linked list
    previous.next = current.next


In this method:

  • Head Check: It first checks if the node to be deleted is at the head of the list.
     
  • Traversal: The list is traversed while keeping track of the node to be deleted (current) and the node just before it (previous).
     
  • Deletion: Once the node is found, it is unlinked from the list by setting the next of the previous node to the next of the current node.
     
  • Handling Absence: If no node contains the key, a message is returned indicating that the data is not present in the list.


Note : This deletion process ensures that the linked list remains intact except for the removed node, and the structural links between remaining nodes are properly maintained.

Remove First Node from Linked List

Removing the first node from a linked list, also known as the head of the list, is a straightforward process. This operation is typically used when you need to process or remove the front element of the list. Here’s how you can implement the removal of the first node in a Python linked list:

def remove_first(self):
    if self.head is None:
        return "The list is empty, nothing to remove."
    # Move the head pointer to the next node, effectively removing the first node
    self.head = self.head.next


This method:

  • Check for Empty List: First checks if the list is empty. If it is, it returns a message stating that there is nothing to remove.
     
  • Update Head: If the list is not empty, the head of the list is updated to the next node in the list, thereby removing the current head.


Note : Removing the first node is an O(1) operation, meaning it can be done in constant time regardless of the size of the list

Remove Last Node from Linked List

Removing the last node from a linked list requires a bit more effort compared to removing the first node, mainly because you have to traverse the entire list to reach the end. Let’s see how to remove the last node from a linked list in Python:

def remove_last(self):
    if self.head is None:
        return "The list is empty, nothing to remove."
    if self.head.next is None:
        self.head = None  # If there is only one node, make head None
        return
    second_last = self.head
    while second_last.next.next:
        second_last = second_last.next  # Move to the second last node

    second_last.next = None  # Remove the last node by setting the second last node's next to None


This method:

  • Check for Empty List: Starts by checking if the list is empty. If it is, it informs that there is nothing to remove.
     
  • Single Node Check: Checks if the list has only one node. If so, it simply sets the head to None.
     
  • Traverse to Second Last Node: If the list has more than one node, it traverses to the second last node.
     
  • Remove Last Node: The next of the second last node is set to None, effectively removing the last node from the list.


Note : Removing the last node involves traversing almost the entire list, making it an O(n) operation, where n is the number of nodes in the list. This is necessary to maintain the integrity of the linked list.

Delete a Linked List Node at a Given Position

To delete a node from a specific position in a linked list, you must correctly identify and unlink the node at that position. Here’s how to perform this operation in Python:

def delete_at_position(self, position):
    if self.head is None:
        return "The list is empty, nothing to delete."
    if position == 0:
        self.head = self.head.next  # Remove the head if the position is 0
        return
    previous = None
    current = self.head
    count = 0
    # Traverse to the desired position or the end of the list
    while current is not None and count < position:
        previous = current
        current = current.next
        count += 1

    if current is None:
        return "Position out of bounds."

    # Unlink the node from the list by setting the previous node's next to current node's next
    previous.next = current.next


This method involves:

  • Empty List Check: Checking if the list is empty, in which case there is nothing to delete.
     
  • Head Removal: Removing the head directly if the position to delete is 0.
     
  • Traversal: Traversing the list to find the node just before the position to ensure the node at that position can be removed.
     
  • Position Check: Ensuring that the position is not out of the bounds of the list.
     
  • Unlinking the Node: If the node is found, it is unlinked by adjusting the next pointer of the previous node.
     

Note : Deleting a node at a specific position requires careful handling to maintain the integrity of the linked list, especially in terms of not leaving any node disconnected.

Delete a Linked List Node of a Given Data

Removing a node based on its data involves searching through the linked list to find a node that contains the specified data and then deleting that node from the list. Let’s see how we can implement this in Python:

def delete_node_by_data(self, data):
    current = self.head
    previous = None
    # Check if the list is empty
    if current is None:
        return "The list is empty, nothing to delete."
    # If the node to be deleted is the head node
    if current.data == data:
        self.head = current.next  # Move the head to the next node
        return
    # Traverse the list looking for the node with the specified data
    while current is not None and current.data != data:
        previous = current
        current = current.next
    # If the node was not found
    if current is None:
        return "No node with the specified data found."
    # Unlink the node from the linked list
    previous.next = current.next


This method includes:

  • Empty List Check: Initial check to determine if the list is empty.
     
  • Head Node Check: Special handling if the node to be deleted is the head.
     
  • Traversal and Search: Looping through the list to find the node with the matching data.
     
  • Deletion: Once the node is found, it is unlinked from the list by setting the next attribute of the previous node to the next node of the current node.
     
  • Not Found Case: Handling the scenario where no node with the specified data exists.
     

Note : This approach ensures that any node with the specified data is effectively removed from the linked list, maintaining the list's structure and integrity.

Linked List Traversal in Python

Traversing a linked list involves sequentially accessing each node in the list from the beginning to the end. This is crucial for many operations, such as displaying the list’s content, performing searches, or applying transformations. Here's how you can implement linked list traversal in Python:

def traverse(self):
    current = self.head
    # Check if the list is empty
    if current is None:
        print("The list is empty.")
        return
    # Loop through each node until you reach the end of the list
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")  # This represents the end of the list


In this method:

  • Empty List Check: It first checks whether the list is empty, in which case it informs the user.
     
  • Traversal: The method then loops through each node in the list, starting from the head.
     
  • Displaying Data: As it traverses, it prints the data contained in each node, followed by an arrow (->) pointing to the next node, indicating the link between nodes.
     
  • End of List: Once all nodes are accessed, it prints "None" to signify the end of the list.
     

Note : This traversal technique is not only useful for displaying the contents of the list but also forms the basis for many other linked list operations, such as insertion, deletion, and searching, by providing a mechanism to access each node systematically.

Get Length of a Linked List in Python

Determining the length of a linked list involves counting the number of nodes from the beginning to the end of the list. This is an essential operation for various purposes, such as validating indices for insertion or deletion. Let’s see a method to calculate the length of a linked list in Python:

def get_length(self):
    count = 0  # Initialize a counter to zero
    current = self.head  # Start with the head of the list
    while current:
        count += 1  # Increment the counter for each node encountered
        current = current.next  # Move to the next node
    return count  # Return the total number of nodes


This method works by:

  • Initialization: Starting the count at zero and setting the current node to the head of the list.
     
  • Traversal: Iteratively moving through each node in the list, increasing the count by one for each node passed.
     
  • Completion: When no more nodes are left (current becomes None), the method returns the count.
     

Note : Calculating the length of the list is an O(n) operation, where n is the number of nodes in the list, as it requires a full traversal from the head to the end.

Example of a Linked List in Python

To consolidate our understanding of linked lists and their operations in Python, let's construct a complete example that demonstrates creating a linked list, adding nodes, and performing various operations like insertion, deletion, and traversal. Here's a comprehensive example:

  • Python

Python

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
last = self.head
while last.next:
last = last.next
last.next = new_node

def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next # Corrected here
print("None")

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

def insert_at_position(self, data, position):
if position == 0:
self.insert_at_beginning(data)
return
new_node = Node(data)
temp = self.head
for i in range(position - 1):
if not temp:
raise Exception("Position out of bounds")
temp = temp.next
new_node.next = temp.next
temp.next = new_node

def delete_node(self, key):
current = self.head
previous = None
while current and current.data != key:
previous = current
current = current.next
if previous is None:
self.head = current.next
elif current:
previous.next = current.next

def get_length(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count

# Usage
llist = LinkedList()
llist.append(3)
llist.append(5)
llist.append(7)
llist.insert_at_beginning(2)
llist.insert_at_position(4, 2)
llist.delete_node(5)
llist.print_list()
print("Length of list:", llist.get_length())
You can also try this code with Online Python Compiler
Run Code

Output

2 -> 3 -> 4 -> 7 -> None
Length of list: 4

Frequently Asked Questions

What is the time complexity of accessing an element in a linked list?

The time complexity of accessing an element in a linked list is O(n), as it requires traversal from the head to the specified position in the worst case.

Can linked lists contain different data types in Python?

Yes, linked lists in Python can contain different data types because Python is a dynamically typed language, allowing nodes to store data of any type.

Why would you use a linked list over an array?

Linked lists are preferable when you need dynamic data allocation, frequent insertion and deletion of nodes at arbitrary positions, and when memory size is a concern, as they don't require memory to be allocated in advance.

Conclusion

In this article, we have learned about all the operations of linked lists in Python. We covered how to create and manipulate nodes within a linked list, including operations such as appending nodes, inserting nodes at specific positions, deleting nodes, and traversing the list to display its contents or determine its length. These concepts are very important to learn as these are the basics of other complex algorithms and concepts of programming. So, practice them properly and try to master them.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.

Live masterclass