Python Linked Lists | A Comprehensive Guide (With Code Examples)

27 mins read

Arrays are often the first tools/ data structures we use when managing data collections. But what if you need something more flexible, where elements can be inserted or removed without shifting half the array around? The answer is Python’s linked lists, a dynamic alternative to arrays. Think of a linked list as a train, where each compartment (node) is connected to the next via a link (pointer), and you can add or remove compartments without disturbing the rest of the train.

In this article, we will discuss linked lists in Python, from the basic concepts to implementation and practical applications. By the end, you’ll know how to create, traverse, manipulate, and apply linked lists effectively.

What Is A Linked List In Python?

A linked list is a linear data structure where elements, called nodes, are stored in separate memory locations and connected via pointers. Each node contains two parts:

1. Data: The actual value of the node.
2. Pointer: A reference to the next node in the sequence (or None if it’s the last node).

Unlike arrays, linked lists do not require contiguous memory, making them more efficient for frequent insertions and deletions. However, they lack the direct indexing feature of arrays, meaning traversal is often required to access specific elements.

All in all, linked lists are rarely used in applications due to the built-in versatility of Python lists, but understanding them builds a solid foundation for data structure concepts.

Types Of Linked Lists In Python

Linked lists come in different flavors, each with its own unique characteristics. Here’s a breakdown of the three most common types:

1. Singly Linked List In Python

In a singly linked list, each node contains two parts:

• Data: The value the node holds.
• Next Pointer: A reference to the next node in the sequence.

The last node in a singly linked list points to None, signaling the end of the list.

2. Doubly Linked List In Python

A doubly linked list enhances the singly linked list by adding an additional pointer:

• Data: The value the node holds.
• Next Pointer: A reference to the next node.
• Previous Pointer: A reference to the previous node.

This allows traversal in both directions: forward and backward.

3. Circular Linked List In Python

In a circular linked list, the last node’s next pointer points back to the first node, creating a circular structure. It can be either singly or doubly linked, but the key difference is the circular nature of the last pointer.

• Singly Circular Linked List: The last node's next points to the first node.
• Doubly Circular Linked List: The first node's prev points to the last node, and the last node's next points back to the first node.

Also read: Python List | Everything You Need To Know (With Detailed Examples)

How To Create A Linked List In Python

Creating a linked list in Python requires us to define the structure of a node and the linked list itself. Here’s how you can build a basic singly linked list from scratch:

1. Initializing a Node

The first step is to create a class for a node. Each node will hold two parts:

• Data: The value it stores.
• Next: A pointer to the next node in the list (initially set to None).

Copy Snippet:

class Node:
    def __init__(self, data):
        self.data = data  # The value the node holds
        self.next = None  # Pointer to the next node (default is None)

2. Create a Linked List Class

Next, we need a class to represent the entire linked list. This class will include methods for inserting, traversing, and managing the list. It will contain a head pointer that points to the first node of the list.

Code Snippet:

class LinkedList:
    def __init__(self):
        self.head = None  # Initially, the list is empty, so head is None

3. Adding Methods To The Linked List Class

Now, we add methods to our linked list class for operations like inserting at the beginning, displaying the list, and traversing through the nodes. For example, to insert a new node at the beginning, we’ll create a method that:

• Creates a new node.
• Points the new node's next to the current head.
• Sets the new node as the new head of the list.

Copy Example:

class LinkedList:
    def __init__(self):
        self.head = None
    def insert_at_beginning(self, data):
        new_node = Node(data)  # Create a new node
        new_node.next = self.head  # Point it to the current head
        self.head = new_node  # Update the head to be the new node

Let’s look at a basic Python program example that illustrates how to create a linked list and initialize it manually.

Code Example:

class Node: #defining the node class for the linked list
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList: #defining the linked list class
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Initialize the nodes manually and link them directly
ll = LinkedList()

# Creating nodes directly
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

# Manually link the nodes
ll.head = node1 # Set the first node as the head
node1.next = node2 # Link node1 to node2
node2.next = node3 # Link node2 to node3

# Traverse the linked list and print the data of each node
ll.traverse()

Expected Output:

10 → 20 → 30 → None

Code Explanation:

In the basic Python code example,

1. We begin by creating a Node class to represent the basic building block of the linked list — the node. 
2. The Node class contains an __init__ method, which initializes the two attributes of each node:
• data: This is the value stored in the node.
• next: This is a pointer (reference) to the next node in the list, which is initially set to None.
3. Next, we define another class, LinkedList, which will manage the entire linked list. The LinkedList class contains a single attribute:
• head: This is a pointer to the first node in the list. It is initialized to None, indicating that the list is empty when it is first created.
4. The __init__ method in the LinkedList class is responsible for initializing this head attribute, essentially setting up an empty linked list.
5. We also define a traverse() method in LinkedList class designed to iterate through all the nodes in the linked list and print their values. Inside:
• We create a pointer current and set it to the head node, which is the first note in the list.
• Then, we use a while loop to visit each node one by one, starting from the head.
• The while loop continues as long as current is not None. In other words, it keeps iterating through the nodes until it reaches the end of the list (when current becomes None).
• Inside the loop, we use the print() function to display the data of the current node, followed by an arrow (→) to indicate that there is a next node.
• After this, the current pointer is moved to the next node in the list (using the next attribute of the current node).
6. The loop terminates once we reach the end of the list (where current is None) and use print to display "None" to indicate the end of the list.
7. After this, we create a linked list called ll, using the LinkedList() constructor.
8. Then, we define three nodes (node1, node2, node3) and initialize them with data values 10, 20, and 30, respectively.
9. Next, we manually link the nodes using the Node class.
• ll.head = node1: The first node (node1) is set as the head of the linked list, which is the starting point of the list.
• node1.next = node2: The next pointer of node1 is set to node2, meaning that when we traverse the list starting from node1, we will move to node2 next.
• node2.next = node3: Similarly, node2's next pointer is set to node3, linking them in sequence.
10. Then, we call the traverse() method from the LinkedList class on the ll linked list. It prints the data of each node in the list in the order they are linked.

Check out this amazing course to become the best version of the Python programmer you can be.

How To Traverse A Linked List In Python & Retrieve Elements

Traversal is the process of visiting each node in a linked list, starting from the head node and moving through the list until the end is reached. During traversal, you can retrieve elements stored in the nodes, print them, and perform other operations on them. In this section, we will discuss how to traverse a linked list in Python programming and retrieve elements.

In a singly linked list, the traversal happens from one node to the next via the next pointer.

• To traverse a linked list, we can iterate through the nodes starting from the head. 
• At each step, we will access the data of the current node and then move to the next node by following the next pointer. 
• This continues until the last node (None) is reached.

Retrieval refers to accessing specific data from a node during traversal, which can be used for operations like searching for a specific value. The simple Python program example below illustrates both these processes.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    # Traverse the linked list and print the data of each node
    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

    # Retrieve a specific value by traversing
    def find(self, data):
        current = self.head # Start from the head node
        while current:
            if current.data == data: # If the data matches, return it
                return current.data
            current = current.next # Move to the next node
        return None # Return None if the value is not found

# Create the linked list
ll = LinkedList()

# Manually create some nodes for simplicity
ll.head = Node(10)
second = Node(20)
third = Node(30)

# Link the nodes
ll.head.next = second
second.next = third

# Traverse the linked list and print the data of each node
ll.traverse()

# Retrieve a specific value (search for 20)
result = ll.find(20) # Looking for '20' in the list
if result:
    print(f"Value found: {result}")
else:
  print("Value not found.")

Expected Output:

10 → 20 → 30 → None
Value found: 20 

Code Explanation:

In the simple Python code example, we continue using the linked list from the previous section.

1. We create the Node class with the __intit__() method to initialize the two attributes, data and next.
2. Then, we create a LinkedList class, which has the same attribute head that points to the first node. 
3. Just like the previous example, the __intit__() method initializes the attribute and the traverse() method traverses the linked list and prints the data of each node. 
4. In addition, the class also contains a find() method used to search for a specific value in the linked list. 
• It starts at the head node and iterates through each node. 
• If it finds a node where the data matches the search value, it returns the value. 
• If no match is found, it returns None.
5. Next, we create a linked list ll and manually add three nodes (10, 20, and 30). These nodes are linked together using the next pointers.
6. Then, we call the traverse() method to print the values of all nodes in the list.
7. After that, we call the find() method, passing value 20 as an argument, to search for the value 20. Since the value is found in the list, the result is printed to the console.

Inserting Elements In A Linked List In Python

Inserting elements into a linked list is crucial for dynamically managing the data. There are three common ways to insert elements into a linked list: at the beginning, at the end, and a specific position. In this section, we will discuss all three approaches with examples.

Inserting Element At The Beginning Node Of A Linked List In Python

Inserting an element at the beginning of a linked list involves creating a new node and making it the new head of the list. This operation is typically done by updating the head pointer to point to the new node, and the new node's next pointer is set to the current head. 

This approach ensures that the new node is always the first element in the list. We have illustrated this in the Python program example below.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

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

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Creating a linked list and inserting at the beginning
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

# Traversing the list
ll.traverse()

Expected Output:

10 → 20 → 30 → None

Code Explanation:

In the Python code example,

1. We define a Node class to represent each element in the list.
2. Then, we define the LinkedList class, which contains a head attribute, the __intit__() method, and a traverse method.
3. We also define another function, insert_at_beginning(), to insert a node at the beginning of the linked list.
• Inside the function, a new node is created with the given data, and its next pointer is set to the current head node. 
• Then, the head pointer of the list is updated to point to the new node.
4. After that, we define a linked list called ll using the LinkedList() constructor.
5. Next, we call the insert_at_beginning() method three times to insert three nodes 30, 20, and 10, respectively. 
6. Then, we call the traverse() method to print the entire linked list, confirming that the new nodes were successfully added at the beginning.

Inserting Element At End Node Of The Linked List In Python

To insert an element at the end of a linked list, we need to traverse the entire list until we reach the last node (whose next pointer is None). Once the last node is reached, we create a new node, set the next pointer of the last node to this new node, and mark the new node as the new last element of the list.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    # Inserting a new node at the end of the list
    def insert_at_end(self, data):
        new_node = Node(data) # Create a new node with the given data
        if self.head is None: # If the list is empty, set the new node as head
            self.head = new_node
            return
        last_node = self.head
        while last_node.next: # Traverse to the last node
            last_node = last_node.next
        last_node.next = new_node # Add the new node after the last node

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Creating a linked list and inserting at the end
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)

# Traversing the list
ll.traverse()

Expected Output:

10 → 20 → 30 → None

Code Explanation:

In the example Python program,

1. We define the Node class with data and next attributes and LinkedList class with the head attribute and the traverse() method.
2. In addition, we also define an insert_at_end() method in the LinkedList class to add a node to the end of the linked list. Inside:
• We first create a new node, new_node, with the data. 
• Then, we use an if statement to check if the list is empty. If it is, we set the new node as the head and return the same.
• If the list is not empty, we use a while loop to traverse to the last node (where next is None) and then add the new node after it.
3. After this, we create a linked list called ll and initialize its nodes using the insert_at_end() method.
4. We call the insert_at_end() method three times with values 10, 20, and 30, respectively (in order).
5. Then, we call the traverse() method to print the list, with the output confirming that the new node has been added at the end.

Inserting Element At Specific Node Position In Linked List In Python

Inserting an element at a specific position involves navigating to the node before the desired position. After reaching the correct node, we create a new node and adjust the next pointers of the surrounding nodes to include the new node in the correct place. This allows us to insert the new element anywhere in the list.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    def insert_at_beginning(self, data):
        new_node = Node(data) # Create a new node
        new_node.next = self.head # Point it to the current head
        self.head = new_node # Update the head to be the new node

    def insert_at_position(self, data, position):
        if position <= 0:
            self.insert_at_beginning(data) # Insert at the beginning if position is invalid
            return
        current = self.head
        new_node = Node(data) # Create a new node
        for _ in range(position - 1):
            if current is None: # If we've reached the end of the list before reaching the position
                print("Position out of range")
                return
            current = current.next
        new_node.next = current.next # Set the next of the new node to the current node's next
        current.next = new_node # Set the current node's next to the new node

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Example usage:
ll = LinkedList()

# Inserting nodes at the beginning
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

# Inserting at a specific position (2nd position)
ll.insert_at_position(25, 2) # Insert 25 at position 2

# Traverse and print the list
ll.traverse()

Expected Output:

10 → 20 → 25 → 30 → None

Code Explanation: 

In the example Python code,

1. We have the same Node (with attributes data and next) and LinkedList classes (with head attribute, traverse() and insert_at_beginning() methods).
2. We introduce a new method, insert_at_position(), which allows us to insert a node at any given position in the list. Inside the function:
• First, we use the relational operator in the if-statement condition to check if the position is less than or equal to 0.
• If the condition is true, the if-block calls the insert_at_beginning() to insert the new node at the start of the list, as this is an invalid position for insertion elsewhere.
• If the condition is false, i.e., the position is valid, we start from the head node and traverse through the list using a for loop.
• We move node by node until we reach the node just before the specified position (position - 1).
• Then, we use a for loop to traverse the list until we reach the desired position (one position before where the new node should be inserted).
• At the desired position, the new node's next pointer is set to the current node’s next (the node at the target position). 
• Then, the current node's next pointer is updated to point to the new node, effectively inserting the new node at the specified position.
3. Outside the class, we create a linked list (ll), insert nodes 30, 20, and 10 using insert_at_beginning(), and then insert the value 25 at position 2 with insert_at_position(). 
4. Finally, we call the traverse() method to print the linked list and confirm the node insertion.

Deleting Elements From A Linked List In Python

Deleting elements from a linked list is a common operation when we need to remove data dynamically. There are three common ways to delete elements: from the beginning node, end node, and a specified node by value. 

Deleting The Beginning Node Of Linked List In Python

Deleting the beginning node involves removing the head of the linked list. The new head becomes the next node, and the old head is no longer referenced.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    #Inserting at the beginning of the linked list
    def insert_at_beginning(self, data):
        new_node = Node(data) # Create a new node with the given data
        new_node.next = self.head # Point new node's next to the current head
        self.head = new_node # Update the head to be the new node

    # Deleting the node at the beginning of the list
    def delete_at_beginning(self):
        if self.head is None: # If the list is empty
            print("The list is empty.")
            return
        self.head = self.head.next # Move the head pointer to the next node

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Creating a linked list and deleting the beginning node
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

ll.traverse() # Before deletion
ll.delete_at_beginning() # Deleting the first node
ll.traverse() # After deletion

Expected Output:

10 → 20 → 30 → None
20 → 30 → None

Code Explanation:

In the sample Python program,

1. The delete_at_beginning() method removes the first node in the list.
2. If the list is empty (i.e., head is None), a message is printed.
3. Otherwise, the head pointer is updated to point to the next node in the list, effectively removing the current head node.
4. The traverse() method is used to display the list before and after the deletion.

Deleting The End Node Of Linked List In Python

Deleting the last node involves traversing the list until the second-to-last node is found. The next pointer of this node is set to None, effectively removing the last node.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    #Inserting at the beginning of the linked list
    def insert_at_beginning(self, data):
        new_node = Node(data) # Create a new node with the given data
        new_node.next = self.head # Point new node's next to the current head
        self.head = new_node # Update the head to be the new node

    # Deleting the node at the end of the list
    def delete_at_end(self):
        if self.head is None: # If the list is empty
            print("The list is empty.")
            return
        if self.head.next is None: # If there is only one node
            self.head = None
            return
        current = self.head
        while current.next and current.next.next: # Traverse to the second-to-last node
            current = current.next
        current.next = None # Remove the last node

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Creating a linked list and deleting the last node
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

ll.traverse() # Before deletion
ll.delete_at_end() # Deleting the last node
ll.traverse() # After deletion

Expected Output:

10 → 20 → 30 → None
10 → 20 → None

Code Explanation:

In the sample Python code,

1. The delete_at_end() method removes the last node in the list.
2. If the list is empty, a message is printed. If there is only one node, the head is set to None.
3. Otherwise, the list is traversed to find the second-to-last node. The next pointer of this node is set to None, effectively removing the last node.
4. The traverse() method displays the list before and after the deletion.

Deleting A Specific Node In Python Linked List By Value

Deleting a specific node by its value involves traversing the list and checking each node’s data. When the node with the desired value is found, its previous node’s next pointer is updated to point to the node after the node to be deleted.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None
    
    #Inserting at the beginning of the linked list
    def insert_at_beginning(self, data):
        new_node = Node(data) # Create a new node with the given data
        new_node.next = self.head # Point new node's next to the current head
        self.head = new_node # Update the head to be the new node

    # Deleting a node by value
    def delete_by_value(self, data):
        if self.head is None: # If the list is empty
            print("The list is empty.")
            return
        if self.head.data == data: # If the head node is the node to be deleted
            self.head = self.head.next
            return
        current = self.head
        while current.next: # Traverse the list
            if current.next.data == data: # If the node with the value is found
                current.next = current.next.next # Skip the node to be deleted
                return
            current = current.next
        print("Value not found.")

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

# Creating a linked list and deleting a specific node
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

ll.traverse() # Before deletion
ll.delete_by_value(20) # Deleting node with value 20
ll.traverse() # After deletion

Expected Output:

10 → 20 → 30 → None
10 → 30 → None

Code Explanation:

In the Python program sample,

1. The delete_by_value() method removes a node with the specified data.
2. If the list is empty, a message is printed. If the head node contains the value, it is removed by updating the head pointer.
3. If the value is in a node other than the head, the list is traversed to find the node with the matching value. The previous node’s next pointer is updated to skip over the node to be deleted.
4. The traverse() method displays the list before and after the deletion.

Level up your coding skills with the 100-Day Coding Sprint at Unstop and get the bragging rights now!

Update A Node Of Linked List In Python

Like retrieval and insertion, updating nodes involves traversing the list to find the node we want to modify and then changing its data attribute. Here is how this works:

1. Traverse the linked list to locate the node we want to update.
2. Once the node is found, we update its data attribute with the new value.
3. If the node isn't found, we handle the case accordingly (e.g., by returning a message or taking no action).

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

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

    def update_node(self, old_data, new_data):
        current = self.head
        while current: # Traverse the list
            if current.data == old_data: # If the node with old_data is found
                current.data = new_data # Update the node's data
                return # Exit after the update is done
            current = current.next
        print("Node with data", old_data, "not found.") # If the node is not found

# Create a linked list and insert elements
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

# Traverse the list before updating
print("Linked List before update:")
ll.traverse()

# Update a node's data (change 20 to 25)
ll.update_node(20, 25)
# Traverse the list after updating
print("Linked List after update:")
ll.traverse()

Expected Output:

Linked List before update:
10 → 20 → 30 → None
Linked List after update:
10 → 25 → 30 → None

Code Explanation:

In this Python code sample:

• We have the same Node class with the data and next attributes.
• The LinkedList class contains the same head attribute, along with methods for traversing the list (traverse()) and inserting nodes at the beginning (insert_at_beginning()).
• We define an additional method, update_node(), to update a node’s data in the linked list. Inside this method:
• We start by traversing the linked list from the head node.
• For each node, we check if its data matches the old_data parameter.
• If the node is found, we update its data with the new value (new_data) and exit the function.
• If the node with old_data is not found, we print a message indicating the node was not found in the list.
• After initializing a linked list and inserting nodes with values 10, 20, and 30, we call the traverse() method to display the list.
• Then, we call the update_node() method to change the value 20 to 25 in the list.
• Finally, we call traverse() again to verify that the update has been successfully made, showing that 25 has replaced 20 in the list.

Reversing A Linked List In Python

In this section, we will explore how to reverse the order of nodes in a linked list, turning the last node into the first one, the second last into the second, and so on, until the entire list is reversed. This operation is important when we need to change the direction of traversal or when working with certain algorithms that require reverse processing.

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

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

    # Reversing the linked list
    def reverse(self):
        previous = None
        current = self.head
        while current:
            next_node = current.next # Store the next node
            current.next = previous # Reverse the current node’s pointer
            previous = current # Move the previous pointer to current node
            current = next_node # Move to the next node in the list
        self.head = previous # Update head to the last node (previous)

# Create a linked list and insert nodes at the beginning
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)

# Print the original list
print("Original list:")
ll.traverse()

# Reverse the linked list
ll.reverse()
# Print the reversed list
print("Reversed list:")
ll.traverse()

Expected Output:

Original list:
10 → 20 → 30 → None
Reversed list:
30 → 20 → 10 → None

Code Explanation:

In the Python code example:

1. We first create the Node and LinkedList classes, with the usual methods for inserting nodes and traversing the list.
2. We introduce a new method in the LinkedList class, reverse(), which reverses the linked list in place. Inside the reverse() method:
• We start by initializing two pointers: previous (set to None) and current (set to the head of the list).
• We then enter a while loop that continues until we reach the end of the list (current becomes None).
• At each iteration, we temporarily store the next pointer of the current node (to avoid losing the rest of the list).
• Then, we reverse the direction of the next pointer of the current node by pointing it to the previous node.
• Next, we move the previous and current pointers one step forward to continue processing the list.
• Once the loop completes, we update the head of the list to the previous pointer, which now points to the new head (the last node in the original list).
3. We then create a linked list and insert three nodes (30, 20, and 10) at the beginning.
4. Finally, we call the reverse() method to reverse the linked list and print both the original and reversed lists using the traverse() method.

Calculating Length Of A Linked List In Python

In this section, we focus on calculating the length of a linked list, which refers to counting the number of nodes in the list. The length of a linked list is useful in many scenarios, such as verifying if the list is empty, determining the position of a node, or performing certain operations only if the list contains enough nodes.

We will define a method that iterates through the linked list to count the nodes until the end of the list (when the next pointer is None).

Code Example:

class Node:
    def __init__(self, data):
        self.data = data # The value the node holds
        self.next = None # Pointer to the next node (default is None)

class LinkedList:
    def __init__(self):
        self.head = None # Initially, the list is empty, so head is None

    def traverse(self):
        current = self.head # Start from the head node
        while current:
            print(current.data, end=" → ") # Print the data of the current node
            current = current.next # Move to the next node
        print("None") # End of the list

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

    # Method to calculate the length of the linked list
    def length(self):
        count = 0
        current = self.head
        while current:
            count += 1 # Increment the count for each node
            current = current.next # Move to the next node
        return count

# Creating a LinkedList and inserting nodes
ll = LinkedList()
ll.insert_at_beginning(10)
ll.insert_at_beginning(20)
ll.insert_at_beginning(30)

# Traverse the linked list
ll.traverse()

# Calculate the length of the linked list
print("Length of the linked list:", ll.length())

Expected Output:

30 → 20 → 10 → None
Length of the linked list: 3

Code Explanation:

In this Python example, we use the LinkedList class to calculate the length of the list, building upon previous methods like insert_at_beginning() and traverse().

1. The length() method calculates the total number of nodes in the linked list. 
• It starts by setting count to zero, then iterates through the list. 
• For each node visited, it increments count by 1 until it reaches the end of the list (when current becomes None).
2. We then create a linked list ll, insert three nodes (10, 20, and 30) at the beginning using insert_at_beginning(), and then print the list with traverse().
3. Finally, we calculate and print the length of the linked list using the length() method, which returns the number of nodes in the list (in this case, 3).

Looking for guidance? Find the perfect mentor from select experienced coding & software development experts here.

Comparing Arrays And Linked Lists In Python

In this section, we’ll highlight the key differences between Linked Lists and Arrays to help you understand their use cases and when one might be preferable over the other.

Key Differences Between Linked Lists and Arrays

Advantages & Disadvantages Of Linked List In Python

Like any data structure, linked lists come with their own set of strengths and limitations. Let’s take a quick look at both.

When To Use Linked Lists Over Other Data Structures

Linked lists may not always be the first choice when designing data structures for a problem, especially with Python's built-in capabilities like lists and dictionaries. However, they shine in certain scenarios where their unique properties offer advantages over arrays and other linear data structures.

Here’s a breakdown of situations where linked lists might be the preferred choice:

1. Frequent Insertions and Deletions: If your application requires frequent additions or removals of elements at arbitrary positions, linked lists excel. Unlike arrays, where shifting elements is required after insertion or deletion, linked lists can perform these operations in O(1)O(1)O(1) time (given a reference to the target node).
2. Unknown or Dynamically Changing Size: Arrays have a fixed size when initialized and may require resizing (a computationally expensive operation). Linked lists, in contrast, grow dynamically, avoiding the overhead of reallocating memory.
3. Memory Management: Linked lists allocate memory as needed for new nodes. If memory is fragmented or limited, linked lists can better utilize available memory compared to arrays, which require contiguous memory allocation.
4. Non-contiguous Storage Requirements: When dealing with data structures that cannot rely on contiguous memory blocks, linked lists offer flexibility, as each node is stored independently and connected via pointers.
5. Efficient Data Reordering: In applications where elements need to be frequently moved around (e.g., priority queues or playlist manipulation), the pointer-based structure of linked lists minimizes overhead compared to array-based implementations.
6. Real-World Applications: Linked lists are often used in:
• Undo operations in text editors
• Browser history navigation
• Implementation of stacks and queues

When Not To Use Python Linked Lists

While linked lists have their strengths, they’re not ideal for all situations:

• Random Access is Slow: If you need frequent access to elements at arbitrary indices, arrays are a better choice, as linked lists require linear traversal.
• Memory Overhead: Each node requires additional memory for the pointer/reference, which can be significant for large datasets.

In conclusion, linked lists are best suited for scenarios emphasizing flexibility and dynamic changes, where their structure offers clear advantages over static or fixed-size data structures like arrays. Understanding their limitations ensures you make an informed decision when designing data solutions.

Practical Applications Of Linked Lists In Python

Linked lists are versatile data structures with various real-world applications, particularly when dynamic memory allocation is required. They are commonly used in situations where elements need to be added or removed frequently. Below, we explore some practical applications of linked lists in Python:

1. Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. In a queue, the first element inserted is the first one to be removed. Linked lists are ideal for implementing queues because they allow efficient insertion and deletion at both ends.

• Why use linked lists for queues? In a typical array-based queue, resizing is needed when the queue grows beyond its capacity, leading to overhead. In contrast, linked lists provide dynamic resizing without this overhead, as new nodes can be added or removed without having to shift elements.
• Implementation: The linked list's head points to the front of the queue (dequeue operation), and the tail points to the back of the queue (enqueue operation).

2. Stacks

A stack follows the Last In, First Out (LIFO) principle, where the most recently added element is the first one to be removed. Stacks can be implemented efficiently using linked lists.

• Why use linked lists for stacks? In a stack, operations are only performed at the top. Linked lists naturally align with this behavior, as the head node of the list can be treated as the top of the stack. Elements can be pushed or popped efficiently from the front of the list, ensuring constant time complexity O(1) for both operations.
• Implementation: The head of the linked list represents the top of the stack. The push operation inserts an element at the beginning of the list, and pop() removes the first node from the list.

3. Graph Representations

Graphs are often used to represent networks, relationships, and connections. Linked lists can be used to represent graphs, especially in adjacency list representation.

• Why use linked lists for graphs? In graphs, nodes represent vertices, and edges represent connections between them. Using a linked list allows efficient memory usage, especially for sparse graphs, where most of the nodes are not connected to every other node. Each vertex (node) in the graph can maintain a linked list of adjacent vertices (connected nodes).
• Implementation: For a graph, each node (vertex) can have a linked list of other vertices that it is connected to. This adjacency list representation is efficient in terms of space, as it only stores the edges that actually exist.

Conclusion

A linked list in Python are a versatile and useful data structure, particularly useful for scenarios where dynamic memory allocation and efficient insertion or deletion of elements are required. 

• You can create a linked list by defining a Node class and linking individual nodes together, starting with a head node and then adding elements using various methods like inserting at the beginning, end, or specific positions.
• We can perform multiple operations like traversing the list to retrieve data, updating node values, deleting nodes, and even reversing the list. 
• These operations provide flexibility and control over how data is structured and manipulated in memory.
• The advantages of linked lists include dynamic memory allocation, easy insertion and deletion, and efficient use of memory, especially for growing datasets. 
• However, they come with disadvantages such as the need for additional memory to store pointers and the slower access time compared to arrays.

Overall, understanding when and how to use linked lists helps you make informed decisions about which data structure is best suited for your application. 

Frequently Asked Questions

Q1. What is a linked list in Python? 

A linked list in Python is a linear data structure made up of nodes, where each node contains data and a reference (or pointer) to the next node in the sequence. This structure allows efficient insertion and deletion of elements at various positions without needing to shift other elements.

Q2. How do linked lists differ from arrays in Python? 

Linked lists differ from arrays in that they don’t store elements in contiguous memory locations. While arrays offer fast access times for elements using indices, linked lists allow for faster insertion and deletion but require traversal from the head node for access to elements. Arrays are more memory-efficient for fixed-size collections, whereas linked lists are better for dynamic sizes and frequent insertions or deletions.

Q3. When should I use a linked list over other data structures? 

Linked lists are most useful when you need frequent insertion and deletion of elements in a collection, particularly at the beginning or middle of the list. They are preferable when memory usage needs to be dynamic, and when you don’t know the size of the dataset upfront. However, they may not be ideal when fast random access to elements is required, as this would require traversing the list.

Q4. What are some practical applications of linked lists in Python? 

Linked lists have various applications in real-world programming, such as implementing queues, stacks, and even graph representations. They are also used in memory management systems and in scenarios where a dynamic data structure with efficient memory usage is needed.

Q5. How do linked lists handle memory allocation compared to arrays? 

Linked lists dynamically allocate memory for each node, meaning each element can be stored separately, and the memory grows or shrinks as needed. Arrays, on the other hand, have a fixed size and allocate memory contiguously, which can lead to wasted space or overflow issues when resizing is necessary.

Q6. Can linked lists be used in Python's built-in data structures? 

Yes, Python provides built-in data structures like collections.deque, which implement a double-ended queue, that can be thought of as a linked list with more efficient operations for both ends of the structure. This can often serve as an alternative to a traditional linked list in Python, depending on the requirements.

🔗 Linked List Logic: Can You Ace This Quiz?

Do check the following out:

1. Nested List In Python | Initialize, Manipulate & Flatten (+Examples)
2. Python List sort() | All Use Cases Explained (+Code Examples)
3. Fix Indexerror (List Index Out Of Range) In Python +Code Examples
4. Remove Duplicates From Python List | 12 Ways With Code Examples
5. Python List index() Method | Use Cases Explained (+Code Examples)
6. How To Convert Python List To String? 8 Ways Explained (+Examples)