Python Linked Lists: An Introduction
Linked lists are fundamental data structures in computer science, critical for understanding more complex structures. In Python, a linked list is a collection of nodes where each node contains a value and a pointer to the next node in the sequence.
Unlike arrays or Python lists, linked lists do not provide direct access to their elements via indexing. This characteristic makes certain operations more efficient and others less so, which is described by the Big O notation that expresses the worst-case scenario in terms of time or space complexity.
Creating a Linked List Class in Python
Here’s how you can implement a simple linked list in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def print_list(self):
cur_node = self.head
while cur_node:
print(cur_node.data)
cur_node = cur_node.next
Big O Efficiency of Linked List Operations
Appending a new node (O(1)), removing a node from the beginning (O(1)), and finding a node by value or index (O(n)) are key operations in a linked list, each with different Big O efficiencies. For example, appending is always O(1) because it does not matter how long the list is, the steps to perform it remain the same.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Append a node to the end of the list. Time complexity: O(1)."""
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def remove_from_beginning(self):
"""Remove a node from the beginning of the list. Time complexity: O(1)."""
if self.head:
self.head = self.head.next
def find_by_value(self, value):
"""Find a node by its value. Time complexity: O(n)."""
current_node = self.head
while current_node:
if current_node.data == value:
return current_node
current_node = current_node.next
return None
def find_by_index(self, index):
"""Find a node by its index. Time complexity: O(n)."""
current_node = self.head
current_index = 0
while current_node:
if current_index == index:
return current_node
current_node = current_node.next
current_index += 1
return None
def print_list(self):
"""Print all nodes in the list."""
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("None")
# Example Usage
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.print_list() # Output: 1 -> 2 -> 3 -> None
# Remove the first node (head of the list)
linked_list.remove_from_beginning()
linked_list.print_list() # Output: 2 -> 3 -> None
# Find a node by value
found_node = linked_list.find_by_value(3)
print(found_node.data if found_node else "Not found") # Output: 3
# Find a node by index
found_node = linked_list.find_by_index(1)
print(found_node.data if found_node else "Not found") # Output: 3
Conversely, removal from the end is O(n) as it requires iterating through the entire list to find the second-to-last node and update its pointer. Below is the sample Python code for a linked list that includes the method to remove the last element, which is an O(n) operation:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Append a node with the given data to the end of the list."""
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def remove_last(self):
"""Remove the last node from the list. This is an O(n) operation
since it requires iterating through the entire list to find the
second-to-last node."""
if not self.head:
return # List is empty, nothing to remove
if self.head.next is None:
self.head = None # List only has one node, remove it
return
# Start from the head node and find the second-to-last node
second_last = self.head
while second_last.next.next:
second_last = second_last.next
# Remove the last node by setting the next of the second-to-last node to None
second_last.next = None
def print_list(self):
"""Print all the elements of the list."""
cur_node = self.head
while cur_node:
print(cur_node.data, end=" ")
cur_node = cur_node.next
print() # For a new line at the end of the list
# Example usage:
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print("Original List:")
linked_list.print_list()
# Remove the last element
linked_list.remove_last()
print("After removing the last element:")
linked_list.print_list()
Original List:
1
2
3
After removing the last element:
1
2
Running the above python code will output the list before and after removing the last element, showcasing how the remove_last method iterates through the list to find the second-to-last node and updates its pointer to None.
Comparing Linked Lists to Python Lists
While Python’s list data type offers indexing capabilities, making operations like pop and retrieval by index O(1), linked lists have the advantage when it comes to prepending elements, which is also O(1). This makes them particularly useful for stacks and queues.
Conclusion
Linked lists are a versatile and efficient alternative to Python lists for certain operations. Understanding their structure and efficiency is crucial for any programmer looking to deepen their knowledge of data structures.
