Linked List Operations
A linked list is a fundamental data structure used in computer science to store a collection of elements. Unlike arrays, which have a fixed size, linked lists provide dynamic memory allocation, allowing for efficient insertion and deletion of elements.
In this blog, we'll delve into the essential Linked List operations that allow you to manage a list of nodes effectively. These operations include:
We’ll also provide Python code examples for each operation, explaining the logic behind them.
The primary operations on a linked list are:
There are three common types of insertion operations in a linked list:
This operation involves creating a new node and making it the head of the list. The next reference of this new node is pointed to the previous head of the list.
To insert a new node at the end, traverse the list to find the last node and set its next reference to the new node.
This involves inserting a node after a specific node, given its position. The node’s next reference points to the next node of the position, and the previous node’s next reference points to the new node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# Insert at the beginning
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
# Insert at the end
def insert_at_end(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
# Insert at a specific position
def insert_at_position(self, data, position):
new_node = Node(data)
current = self.head
count = 0
# Traverse to the position
while current and count < position - 1:
current = current.next
count += 1
if not current:
print("Position out of bounds.")
return
new_node.next = current.next
current.next = new_node
# Traverse and print the list
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
ll = LinkedList()
ll.insert_at_beginning(10)
ll.insert_at_end(20)
ll.insert_at_position(15, 1) # Insert at position 1
ll.traverse() # Output: 10 -> 15 -> 20 -> None
Deletion operations in a linked list remove nodes based on the following:
None.
class LinkedList:
# Other methods as before...
# Delete from the beginning
def delete_from_beginning(self):
if self.head:
self.head = self.head.next
# Delete from the end
def delete_from_end(self):
if not self.head:
return
if not self.head.next:
self.head = None
return
last_node = self.head
while last_node.next and last_node.next.next:
last_node = last_node.next
last_node.next = None
# Delete a node by value
def delete_node(self, key):
temp = self.head
if temp and temp.data == key:
self.head = temp.next
temp = None
return
prev = None
while temp and temp.data != key:
prev = temp
temp = temp.next
if not temp:
print(f"Node with data {key} not found.")
return
prev.next = temp.next
temp = None
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.traverse() # Output: 10 -> 20 -> 30 -> None
ll.delete_from_beginning()
ll.traverse() # Output: 20 -> 30 -> None
ll.delete_from_end()
ll.traverse() # Output: 20 -> None
ll.delete_node(20)
ll.traverse() # Output: None
Traversal is the process of visiting each node in the linked list, one by one, and performing an operation (e.g., printing the node’s data). This is commonly done in a forward direction, from head to tail.
class LinkedList:
# Other methods as before...
# Traverse the list and print all elements
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.traverse() # Output: 10 -> 20 -> 30 -> None
To search for a node in a linked list, we start from the head node and traverse the list until we find the node containing the target value.
class LinkedList:
# Other methods as before...
# Search for a value in the list
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
print(ll.search(20)) # Output: True
print(ll.search(40)) # Output: False
Reversing a linked list means changing the direction of the links, so the head becomes the tail and vice versa. This can be done iteratively or recursively.
class LinkedList:
# Other methods as before...
# Reverse the 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
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.traverse() # Output: 10 -> 20 -> 30 -> None
ll.reverse()
ll.traverse() # Output: 30 -> 20 -> 10 -> None
To count the number of nodes in the list, we traverse through all the nodes and keep a counter.
class LinkedList:
# Other methods as before...
# Count the number of nodes
def count_nodes(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
print(ll.count_nodes()) # Output: 3
A loop in a linked list occurs when a node's next pointer refers back to a previous node, causing the list to form a cycle. A common algorithm to detect loops is Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm).
class LinkedList:
# Other methods as before...
# Detect a loop in the list
def detect_loop(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
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.head.next.next.next = ll.head # Creating a loop
print(ll.detect_loop()) # Output: True