Linked List Python: Deep Dive!

A linked list is a linear data structure where each element, called a node, contains two parts: the data and a reference (or link) to the next node in the sequence.

Unlike Python’s built-in list data structure, which stores elements in contiguous memory locations, linked lists store elements in separate memory blocks, making them more flexible for certain operations, such as inserting and deleting elements.

By the end of this guide you’ll have a clear understanding of everything linked list Python.

What is a Linked List?

A linked list is a collection of nodes where each node stores:

1. Data: The value that the node holds.
2. Next: A reference (or pointer) to the next node in the sequence.

The first node is referred to as the head, and the last node points to None, indicating the end of the list. This allows linked lists to grow and shrink dynamically.

Key Characteristics of Linked Lists:

• Dynamic Size: Linked lists can grow and shrink during runtime as elements are added or removed.
• Efficient Insertions/Deletions: Inserting or deleting nodes from the list is more efficient (O(1)) compared to arrays or Python lists, especially for operations at the beginning or middle of the list.
• No Random Access: Unlike Python’s built-in list, you cannot access elements by their index directly. You must traverse the list to find a specific element.

Types of Linked Lists

1. Singly Linked List

A singly linked list is a linked list where each node points to the next node in the sequence. Traversal is only possible in one direction (from the head to the end).

Example of Singly Linked List:

[Data | Next] -> [Data | Next] -> [Data | Next] -> None

2. Doubly Linked List

A doubly linked list is a linked list where each node contains a reference to both the next and the previous nodes. This allows traversal in both directions (forward and backward).

Example of Doubly Linked List:

None <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> None

In this guide, we will first focus on implementing a singly linked list in Python and then briefly cover the doubly linked list.

Implementing a Singly Linked List in Python

To implement a singly linked list in Python, we need two components:

1. A Node class that holds the data and a reference to the next node.
2. A LinkedList class that manages the list, including methods for inserting, deleting, and traversing nodes.

Step 1: Creating the Node Class

Each node in the linked list contains the data and a pointer to the next node. Here’s how to define the Node class in Python:

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

• data: Holds the value of the node.
• next: Points to the next node in the linked list.

Step 2: Creating the LinkedList Class

The LinkedList class will manage the list by providing methods to insert, delete, and traverse the list.

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

    # Method to insert a new node at the end of the 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

    # Method to display the list elements
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Example of Adding and Displaying Elements:

# Create an instance of LinkedList
ll = LinkedList()

# Append elements to the linked list
ll.append(1)
ll.append(2)
ll.append(3)

# Display the linked list
ll.display()

Output:

1 -> 2 -> 3 -> None

Common Operations on Linked Lists

1. Inserting Nodes

a. Insertion at the End (Append)

The append() method above inserts new nodes at the end of the list. It traverses the list until the last node is found and then updates its next pointer to point to the new node.

b. Insertion at the Beginning

Inserting at the beginning involves pointing the new node to the current head and updating the head to the new node.

Example:

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

Example Usage:

ll.prepend(0)
ll.display()  # Output: 0 -> 1 -> 2 -> 3 -> None

2. Deleting Nodes

To delete a node, we need to search for the node and adjust the pointers of the adjacent nodes to bypass the deleted node.

Example of Deleting a Node:

def delete(self, key):
    current = self.head
    if current and current.data == key:
        self.head = current.next  # If head needs to be deleted
        return
    previous = None
    while current and current.data != key:
        previous = current
        current = current.next
    if current is None:
        return  # The key is not present in the list
    previous.next = current.next

Example Usage:

ll.delete(2)
ll.display()  # Output: 0 -> 1 -> 3 -> None

3. Searching for an Element

To search for an element, we traverse the list and check if the node’s data matches the key.

Example:

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

Example Usage:

print(ll.search(3))  # Output: True
print(ll.search(4))  # Output: False

Implementing a Doubly Linked List in Python

In a doubly linked list, each node has two pointers:

1. Prev: Points to the previous node.
2. Next: Points to the next node.

Node Class for a Doubly Linked List:

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.prev = None  # Points to the previous node
        self.next = None  # Points to the next node

Doubly Linked List Class:

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

    # Method to append at the end
    def append(self, data):
        new_node = DoublyNode(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    # Method to display the list
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

Example Usage:

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Output: 1 <-> 2 <-> 3 <-> None

When to Use Linked Lists in Python

Linked lists are most useful in situations where:

1. Frequent Insertions/Deletions: Linked lists provide efficient insertion and deletion operations, especially when working with large data sets or when you need to frequently manipulate the beginning or middle of the list.
2. Memory Management: Linked lists are dynamically allocated and don’t require continuous blocks of memory like arrays or Python’s built-in lists. This makes them more flexible for managing memory in certain scenarios.
3. Low Random Access Requirements: Since linked lists do not support direct access by index, they are less suited for cases where frequent random access is needed.

For most applications, Python’s built-in list (which is essentially a dynamic array) will be sufficient. However, linked lists shine in specific use cases where their dynamic nature and efficient insertions/deletions are needed.

Conclusion

In this guide, we explored how to implement and use a linked list in Python. We covered the basics of singly and doubly linked lists, how to perform common operations like insertion, deletion, and traversal, and when linked lists are

preferable to Python’s built-in list data structure.

Key Takeaways:

• Linked lists are dynamic data structures that provide efficient insertion and deletion operations.
• Singly linked lists only allow forward traversal, while doubly linked lists allow both forward and backward traversal.
• Linked lists are less suited for random access, as they require traversal from the head to reach a specific element.

Exercises

1. Implement a Linked List: Write a Python class to implement a singly linked list and perform basic operations like insertion, deletion, and traversal.
2. Reverse a Linked List: Implement a method that reverses the nodes of a singly linked list.
3. Doubly Linked List: Implement a doubly linked list in Python and write methods to insert, delete, and traverse the list in both directions.

Check out our FREE Learn Python Programming Masterclass to hone your skills or learn from scratch.

The course covers everything from first principles to Graphical User Interfaces and Machine Learning

Don’t forget you can check everything with the official Python documentation.

FAQ

Q1: Why should I use a linked list when Python already has a built-in list data structure?

A1: While Python’s built-in list is highly optimized for most use cases, linked lists are more efficient for specific operations such as frequent insertions or deletions, especially when modifying elements at the beginning or middle of the list. Python’s list is essentially a dynamic array, so inserting or removing elements from anywhere other than the end can be slow because the list needs to shift elements to maintain order. Linked lists allow you to insert or remove nodes in constant time (O(1)) at the beginning or middle of the list.

Q2: How can I find the length of a linked list in Python?

A2: Since linked lists don’t have a built-in method for retrieving their length, you must manually traverse the list and count the nodes. You can write a method that starts at the head of the list and iterates through each node, incrementing a counter until it reaches the end.

Example:

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

Q3: Can I index a linked list like a Python list?

A3: No, linked lists do not support random access like Python’s built-in lists. To access an element in a linked list, you need to traverse the list starting from the head until you reach the desired node. This process has a time complexity of O(n), where n is the position of the element in the list.

Q4: What happens if I try to delete a node from an empty linked list?

A4: If you attempt to delete a node from an empty linked list, the method should handle this gracefully by checking if the head is None (indicating the list is empty) before proceeding with deletion. If the list is empty, the method should either return early or raise an exception, depending on your design.

Example:

def delete(self, key):
    if self.head is None:
        print("List is empty. Nothing to delete.")
        return
    # Continue with deletion logic...

Q5: How can I reverse a singly linked list in Python?

A5: To reverse a singly linked list, you need to change the direction of the next pointers for each node. This can be done iteratively by maintaining three pointers: prev, current, and next, and then reversing the next pointer at each step.

Example of Reversing a Singly Linked List:

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

Q6: What is the time complexity for inserting and deleting nodes in a linked list?

A6:

• Insertion at the Beginning: O(1) since you only need to change the head pointer and point it to the new node.
• Insertion at the End: O(n) because you must traverse the list to find the last node, except in a doubly linked list with a tail pointer (which allows O(1) insertion).
• Deletion: O(n) since you may need to traverse the list to find the node to delete and update the pointers accordingly.

Q7: Can a linked list have circular references?

A7: Yes, a linked list can form a circular linked list, where the last node points back to the head, creating a loop. Circular linked lists are useful for implementing certain data structures like round-robin scheduling. However, for general use, be cautious with circular references as they can lead to infinite loops during traversal if not handled properly.

Q8: How can I detect a cycle in a linked list?

A8: To detect if a linked list has a cycle (loop), you can use Floyd’s Cycle Detection Algorithm (also known as the tortoise and hare algorithm). In this algorithm, two pointers (slow and fast) traverse the list at different speeds. If there’s a cycle, the fast pointer will eventually meet the slow pointer.

Example:

def has_cycle(self):
    slow = self.head
    fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Q9: How do I handle memory management with linked lists in Python?

A9: Python’s garbage collector automatically manages memory, so you don’t need to manually free up memory when deleting nodes from a linked list. Once a node is no longer referenced, Python’s garbage collector will reclaim the memory. However, if you’re working in a low-level language (like C), you would need to manually manage memory by freeing up nodes after deletion.

Q10: How do I insert a node at a specific position in a linked list?

A10: To insert a node at a specific position, you need to traverse the list to that position, adjust the pointers, and insert the new node. Here’s a method to insert at any given position (0-indexed):

Example:

def insert_at_position(self, data, position):
    new_node = Node(data)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
        return
    current = self.head
    count = 0
    while current and count < position - 1:
        current = current.next
        count += 1
    if current is None:
        print("Position out of bounds")
        return
    new_node.next = current.next
    current.next = new_node

Q11: How can I merge two linked lists in Python?

A11: To merge two linked lists, you can traverse both lists, compare their nodes, and merge them into a new linked list in sorted order. This operation is often used when working with linked lists in problems like merging sorted linked lists.

Example (Merging Two Sorted Linked Lists):

def merge_sorted(list1, list2):
    dummy = Node(0)
    tail = dummy
    while list1 and list2:
        if list1.data < list2.data:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    if list1:
        tail.next = list1
    elif list2:
        tail.next = list2
    return dummy.next

Q12: What is the difference between a linked list and a dynamic array?

A12:

• Memory Allocation: Linked lists use dynamic memory allocation, storing elements in separate blocks, while dynamic arrays (like Python lists) store elements in contiguous memory locations.
• Insertion/Deletion: Linked lists allow efficient insertions and deletions (O(1)) at the beginning and middle of the list, whereas dynamic arrays may require shifting elements (O(n)) for the same operations.
• Random Access: Linked lists don’t support direct access by index, so traversing the list to find an element takes O(n) time, whereas arrays support O(1) random access.