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.
Table of Contents
What is a Linked List?
A linked list is a collection of nodes where each node stores:
- Data: The value that the node holds.
- 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:
- A Node class that holds the data and a reference to the next node.
- 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:
- Prev: Points to the previous node.
- 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:
- 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.
- 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.
- 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
- Implement a Linked List: Write a Python class to implement a singly linked list and perform basic operations like insertion, deletion, and traversal.
- Reverse a Linked List: Implement a method that reverses the nodes of a singly linked list.
- 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.
