Linked Lists in Python

In computer science, a linked list is one of the simplest and most essential data structures. In Python, a linked list can be described as a dynamic collection of elements called nodes, where each node can store data and a link to the next node. Nodes can be inserted and deleted more efficiently than parts of the built-in list object in Python, which is a dynamic array. Whether you are learning data structures as a beginner or you are preparing for technical interviews, a solid understanding of how linked lists work in Python is important. In this article, we will discuss what a linked list is, its operations, types, time complexity, advantages, disadvantages, and applications in Python.

Table of Contents:

• What is a Linked List in Python?
• Creating a Linked List in Python
• Creating a Node Class in Python
• Insertion in a Linked List in Python
• Updating the Node of a Linked List in Python
• Deleting a Node in a Linked List
• Types of Linked Lists in Python
• Traversing a Linked List in Python
• Getting the Length of a Linked List in Python
• Time Complexity of Linked List Operations in Python
• Advantages of Linked List in Python
• Disadvantages of Linked List in Python
• Linked List vs Array in Python
• Applications of Linked Lists in Python
• Conclusion

What is a Linked List in Python?

A linked list in Python is a linear data structure that uses nodes to store the elements, and each node points to the next node in the sequence. In a linked list, each node has two parts:

• Data: The actual value that is stored.
• Pointer (or Reference): A link to the next node in the list.

This structure helps linked lists grow and shrink dynamically, since the elements are not placed in a particular spot. This also helps when inserting and deleting the nodes. The elements are accessed sequentially in a linked list; there is no direct indexing.

Creating a Linked List in Python

To create a linked list in Python, you have to define two main components:

• A Node class – It represents each element in the list.
• A LinkedList class – This class helps to manage the list, starting from the head node.

The class has the following methods:

Here are the steps to create a linked list in Python.

Step 1: Create a Node Class

First, we have to create a node class that carries 2 pieces of information: data and next.

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

Step 2: Create the LinkedList Class

Next, we will create the LinkedList class, which helps to control the entire list and simply starts as an empty list.

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

Step 3: Add Nodes to the Linked List

We can now add the nodes wherever we want, at the start, middle, or end.

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        # Traverse to the end of the list
        current = self.head
        while current.next:
            current = current.next

        current.next = new_node

Step 4: Add a Function to Print the List

At this point, we will add a function to print the list. This is a simple way to visualize the linked list, showing each node.

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

Step 5: Create and Utilize the Linked List

Now, you can use the LinkedList class to build and manipulate the list.

ll = LinkedList()
ll.insertAtEnd(10)
ll.insertAtEnd(20)
ll.insertAtEnd(30)
ll.printLL()

Creating a Node Class in Python

A node class is a simple object that contains data and a next pointer to the list. 

Here, 

• Data: The actual value that is stored.
• Next Pointer: A pointer to the next node in the list.

Now we are going to create a Node class where we will use the __init__ method to initialize the nodes by creating the data and the next pointer.

Here’s how you can define a basic Node class in Python:

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

Explanation: 

• The __init __ method is a constructor, which runs when a new object is created from the class.
• self.data stores the value that you want to store.
• self.next is initially set to None because the new node does not point to anything yet.

Example:

Output:

In this program, the node class is created and initialized using __init__method to initialize a data value and a reference to the next node. Also, two nodes are created and linked in this example, which form a basic two-element linked list.

Insertion in a Linked List in Python

Insertion in a linked list is the process of adding a new node at a particular position. There are three types of insertion in a linked list in Python.

1. Insertion at the Beginning of a Linked List

To insert a node at the beginning of a linked list in Python, follow these steps:

• Create a new node with the data you would like to insert.
• Now, set the next pointer of the new node to point to the head of the linked list.
• Next, update the head of the linked list to point to the new node.
• The new node is now the first node in the linked list.

Example:

Output:

The code shows how the new nodes are added at the beginning of the linked list. At first, a new node is created using insertAtBegin(), then it is linked to the current head, and the head is updated to point to the new node. By this, the elements are added at the start of the list, and then printLL() is used to traverse and print the linked list.

2. Insertion at the End of a Linked List

To insert a new node at the end of a linked list in Python, follow these steps:

• First, create a new node from the data you want to insert. 
• Now, check to see if the linked list is empty. 
• If the linked list is empty, make the new node the head of the linked list.
• If the linked list is not empty, then traverse to the last node, which is marked by the node’s next as None.
• Now set the next of the last node to be the new node and link to the end.

Example:

Output:

The code shows how the new nodes are inserted at the end of the list. In this example, the insertAtEnd() method checks that if the list is empty or not, then proceeds to add the new node. The printLL() method then prints all node values in order from head to tail.

3. Insertion at a Specific Index in a Linked List

To insert a new node at a specific index in a linked list in Python, follow these steps.

• Create a new node using the data you want to insert.
• If the index is 0, call the method to insert at the start.
• Then traverse the list just before the index you’re given.
• If the index is beyond the length of the list, indicate an error or move on without adding the node.
• Set the new node’s next point to the current node’s next.
• The previous node’s next should be set to the new node.

Example:

Output:

The code shows how the new nodes are inserted at a specific index in a linked list. 10 is inserted at index 0 (beginning), 20 is inserted at index 1 (end), 15 is inserted at index 1(between 10 and 20), and then the list is printed using printLL().

Updating the Node of a Linked List in Python

Updating the node in a linked list is the process of changing the value of a node at a particular position or when a certain condition is met.

Below are a few steps that you must follow to update a linked list in Python.

• Start from the head of the linked list.
• Then, traverse the list while keeping track of the current node and index.
• And, if you have reached to the target index, then update the data field with the new value.
• If the target node is not found, then print an error.
  

Example:

Output:

The code shows how the node of a linked list is updated through the updateAtIndex method, which traverses the list to the specified index. When the node is reached at the target or specified index, the data in the node is updated, and the updated list will show the new specified value.

Master Python in Just 2 Months.

Enroll now!

Explore Program

Deleting a Node in a Linked List

Deleting a node in a linked list is a process of removing a node from the list that matches a given value or at a particular position, and then re-linking the nodes to maintain the structure of the list.

1. Deleting the First Node from a Linked List

Deleting the first node or head of a linked list is very easy, as you have to simply delete the head, and then point the head back to the head.next. 

To delete the first node from a linked list in Python, follow these steps:

• First, check if the linked list is empty or not.
• If the head is not empty, then set the head to point to the head.next node to remove (delete) the first node. 
• Once the old head is not pointed to by any node, it will be deleted from the list.

Example:

Output:

The code shows how the first node of a linked list is deleted by checking if the list is empty or not, using the removeFirstNode() method. If the list is not empty, then update the head to point to the second node. Thus, the original first node (10) is no longer referenced and is deleted.

2. Deleting the Last Node from a Linked List

To remove the last node from a linked list, we have to traverse to the second last node and delete it by making its next pointer equal to None.

To delete the last node from a linked list in Python, follow the steps below:

• First, we will check if the linked list is empty.
• If the linked list only contains one node, then set the head to None.
• If the linked list has nodes in it, traverse to the second last node (the node whose node.next.next is None).
• Then delete the last node of the linked list and set the second_last.next equal to None.

Example:

Output:

The code shows how the last node is deleted from the linked list using the removeLastNode(), which traverses the second-last node and sets its next to None, and at last deletes the last node from the list.

3. Deleting a Linked List Node at a Given Position

A node in a linked list can be deleted at a given position by traversing and updating the links to skip over the node to be deleted.

To delete a node in a linked list in Python at a given position, follow these steps:

• Check if the list is empty (head is None).
• If the position is 0, then assign the head to head.next.
• If not, then traverse to the position-1 node (the node before the position).
• If the position is out of bounds, print an error message.
• At last, update the next pointer of the previous node to skip the next node at the position.

Example:

Output:

The above code shows how the node of a linked list is deleted using the deleteAtPosition() method, which removes the node at a given index by traversing to the preceding node, and updating the pointers to skip (i.e., delete) the node at the position.

Types of Linked Lists in Python

Linked lists have 4 different types, based on how nodes are connected and accessed. Here is a brief description of the types with examples in Python.

1. Singly Linked List

A singly linked list is a type of linked list in Python in which each node points to the next node in the sequence. 

• It is a linked list that can only be traversed in one direction, from the head to the end.
• In a singly linked list, each node has two parts, the data and the next, and the last node’s next points to None. 
• Any node can be efficiently inserted and deleted at the start of the list. 
• A singly linked list is simple, easy to use and uses less memory.

Example:

Output:

The code shows how a linked list is created, where each node points to the next node. The nodes are added at the end of the linked list by using insertAtEnd(), and the printList() function is used in traversing the list and displaying the value of the nodes.

2. Doubly Linked List

A doubly linked list is a type of linked list in Python in which each node has a link to both the next node and the previous node in the list. 

• It can be traversed in both directions, forward and backwards, which means from head to end and from end to head. 
• In a doubly linked list, each node has three parts: data that stores the value, next that points to the next node, and prev that points to the previous node. 
• It supports efficient insertion and deletion from both ends, and uses more memory due to the additional prev pointer. 

Example:

Output:

The code shows how a doubly linked list is created, where each node links to both the next and previous nodes. The nodes are added at the end by using insertAtEnd(), and printForward() is used to show the list from head to tail.

3. Circular Linked List

A circular linked list is another version of a singly linked list in Python in which the last node points back to the first node and forms a continuous loop. 

• In the circular linked list, each node points to the next node, and the last node’s next points back to the head. 
• The traversal of the circular linked list is done in a loop indefinitely, and can only be stopped intentionally. 
• This linked list is efficient for circular data management, such as round-robin scheduling. 

Example:

Output:

The code shows how a circular linked list is created in which the last node links back to the head, which forms a loop. The nodes are added at the end of the linked list, and then the printList() function is used to print the list until it cycles back to the head.

4. Circular Doubly Linked List

A circular doubly linked list is a type of doubly linked list in Python where the last node points back to the first node and the first node points to the last node. 

• Like a regular doubly linked list, it can be traversed in both directions, and, because it is circular, we can also cycle around through the linked list. 
• In a circular doubly linked list, each node consists of three parts: data, which is where the value is held, next, which is the pointer to the next node, and prev, which is the pointer to the previous node. 
• The next pointer of the last node points to the head, and the prev pointer of the head points to the last node.

Example:

Output:

The code shows how the circular doubly linked list is created, in which each node is connected in both forward and backward directions, and the last node links back to the head. 

Traversing a Linked List in Python

Traversing a linked list is the process of accessing each of the linked list’s nodes from head to end and getting to the data.

To traverse a linked list in Python, you just follow these steps:

• Start with the head node.
• Use a while loop to traverse from node to node, following the next pointer in the linked list.
• Continue traversing to a node until the current becomes None, which means that you have arrived at the end of the linked list.
• Within the loop, at each iteration, you do the operations that you want to do(i.e., print the data).

Example:

Output:

The code shows how the traversal of a linked list is done by iterating through each node, using the next reference until it reaches the end of the list, and then the visited nodes are printed to the console.

Getting the Length of a Linked List in Python

The length of a linked list is determined by the number of nodes from starting at the head node (where it begins, the first node) to the last node in the linked list.

To determine the length of a linked list in Python, you need to follow these steps:

• Start at the head node.
• Move through each node, incrementing a counter on each visit (initially set to 0).
• Once the traversal is finished (when node is None), return the counter as the linked list length.

Example:

Output:

The code shows how to determine the length of a linked list by calling the getLength() method which goes to the head of the list and traverses from that point, counting the nodes until the end of the list, and returns the total count of nodes, which is 3 in the linked list.

Time Complexity of Linked List Operations in Python

Note:

• The variable n is the number of nodes in the linked list.
• For a doubly linked list, it may be possible to optimize the insertion and deletion at the end to O(1).
• A circular linked list has no endpoint, because you can keep traversing all of the nodes unless you manually stop it.

Free Python Certification Course - Learn Anytime, Anywhere!

Enroll now!

Explore Program

Advantages of Linked List in Python

• Dynamic Size: The size of the linked list can be changed while it is running, and it doesn’t need an initial size. 
• Efficient Insertion & Deletion: Nodes can be inserted or deleted more efficiently than an array, because the elements do not need to be shifted in position within the same index. 
• No Waste of Memory: A linked list will only take up memory if it has nodes, and it will not if it doesn’t have a node (doesn’t waste memory). 
• Flexibility: A linked list is flexible and easy to implement. 
• Easier Reordering: Data can be reordered without copying or shifting other data.

Disadvantages of Linked List in Python

• Memory Overhead: Each individual node in a linked list requires more memory for the pointer, in addition to the data it stores.
• No Random Access: Linked lists do not allow random access. Accessing some element requires traversing node by node, starting from the head to the tail.
• Longer Look-up Time: If you are trying to find the element, the worst case will be O(n) to find the element, thus the it has a high look-up time.
• More Complex: Inserting and deleting in linked lists can also get very complicated with large data sets.
• Cache Performance: Linked lists give worse performance in CPU cache than arrays. Linked lists do not use contiguous memory.

Linked List vs Array in Python

Applications of Linked Lists in Python

• Linked lists are used to implement queues and stacks, so inserting and deleting items is performed in constant time from either end. 
• Linked lists can manage dynamic memory allocation, where continuous insertions and deletions can be done without reallocating memory. 
• Linked lists are suitable for representing graphs as adjacency lists, particularly for sparse graphs.
• Linked lists are ideal for processing real-time data streams, for purposes such as sliding window computations or buffering.
• Links in text editors or similar applications for undo & redo functionality can be made using doubly linked lists.
• In polynomial computations, polynomial terms can be inserted and managed more easily and efficiently using linked lists, providing flexibility.
• Media players, or systems that navigate through playlists, can use circular or doubly linked lists, enabling easier or more efficient forward and backwards movement through the list.

Conclusion

Python linked lists efficiently manage data dynamically, and they offer more flexibility than arrays for certain tasks, such as adding and removing elements. As a language, Python has so many advantages, in particular, being flexible, minimal, and easy to create linked lists among other things, and also, there are some disadvantages. Even though Python has very powerful built-in lists and capabilities, being able to understand linked lists is important to learn data structures for beginners, for good coding skills.

Linked Lists in Python – FAQs