Linked lists are fundamental data structures in computer science, offering dynamic memory allocation and efficient insertion and deletion operations. While Python doesn't have a built-in linked list type, we can implement them using classes. This article will explore the implementation of various types of linked lists in Python, along with their operations and underlying principles.
1. Singly Linked List
A singly linked list consists of nodes where each node contains data and a reference (or link) to the next node in the sequence.
1.1 Basic Implementation
Let's start with a basic implementation of a singly linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def append(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")1.2 Advanced Operations
Now, let's implement some more advanced operations:
class SinglyLinkedList:
# ... (previous methods)
def insert_after(self, key, data):
current = self.head
while current:
if current.data == key:
new_node = Node(data)
new_node.next = current.next
current.next = new_node
return
current = current.next
print(f"Key {key} not found in the list.")
def delete(self, key):
if self.is_empty():
return
if self.head.data == key:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == key:
current.next = current.next.next
return
current = current.next
print(f"Key {key} not found in the list.")
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
def reverse(self):
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev1.3 Time and Space Complexity Analysis
Insertion at the beginning (prepend): O(1) time
Insertion at the end (append): O(n) time
Deletion: O(n) time in the worst case
Search: O(n) time in the worst case
Space complexity: O(n) for n elements
2. Doubly Linked List
A doubly linked list contains nodes with links to both the next and previous nodes, allowing for bi-directional traversal.
2.1 Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def prepend(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def append(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def delete(self, key):
current = self.head
while current:
if current.data == key:
if current.prev:
current.prev.next = current.next
else:
self.head = current.next
if current.next:
current.next.prev = current.prev
else:
self.tail = current.prev
return
current = current.next
print(f"Key {key} not found in the list.")
def display_forward(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
def display_backward(self):
current = self.tail
while current:
print(current.data, end=" <-> ")
current = current.prev
print("None")2.2 Time and Space Complexity Analysis
Insertion at the beginning or end: O(1) time
Deletion: O(n) time in the worst case, but O(1) if given the node to delete
Search: O(n) time in the worst case
Space complexity: O(n) for n elements
3. Circular Linked List
A circular linked list is a variation where the last node points back to the first node, creating a circle.
3.1 Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def append(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
new_node.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def delete(self, key):
if self.is_empty():
return
if self.head.data == key:
if self.head.next == self.head:
self.head = None
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
return
current = self.head
prev = None
while current.next != self.head:
if current.data == key:
prev.next = current.next
return
prev = current
current = current.next
if current.data == key:
prev.next = self.head
def display(self):
if self.is_empty():
print("The list is empty.")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print(" (back to head)")3.2 Time and Space Complexity Analysis
Insertion: O(n) time in the worst case
Deletion: O(n) time in the worst case
Search: O(n) time in the worst case
Space complexity: O(n) for n elements
4. Comparison and Use Cases
Singly Linked List:
Pros: Simple implementation, less memory usage
Cons: Can only traverse forward
Use cases: Implementing stacks, simple list operations
Doubly Linked List:
Pros: Can traverse both forward and backward, efficient deletion if given the node
Cons: More complex implementation, more memory usage
Use cases: Implementing deques, navigation systems (forward/back)
Circular Linked List:
Pros: Can traverse the entire list starting from any point
Cons: More complex termination condition in traversal
Use cases: Round-robin scheduling, circular buffers
5. Advanced Techniques
5.1 Floyd's Cycle-Finding Algorithm
Also known as the "tortoise and hare" algorithm, this technique can be used to detect cycles in a linked list:
def has_cycle(self):
if not self.head:
return False
tortoise = self.head
hare = self.head
while hare and hare.next:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return True
return False5.2 Merging Sorted Linked Lists
def merge_sorted_lists(list1, list2):
dummy = Node(0)
current = dummy
while list1 and list2:
if list1.data < list2.data:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
if list1:
current.next = list1
if list2:
current.next = list2
return dummy.nextConclusion
Linked lists are versatile data structures that offer efficient insertion and deletion operations. While they may not be as commonly used in Python as in lower-level languages, understanding their implementation and principles is crucial for any programmer. By mastering linked lists, you'll gain insights into memory management, pointer manipulation, and algorithm design that will benefit you across various programming tasks and languages.
Comments
Post a Comment