Linked Lists Explained: Navigate Your Dynamic Data Efficiently
Hi, I'm Keerthi Ravilla Subramanyam, a passionate tech enthusiast with a Master's in Computer Science. I love diving deep into topics like Data Structures, Algorithms, and Machine Learning. With a background in cloud engineering and experience working with AWS and Python, I enjoy solving complex problems and sharing what I learn along the way. On this blog, you’ll find articles focused on breaking down DSA concepts, exploring AI, and practical coding tips for aspiring developers. I’m also on a journey to apply my skills in real-world projects like predictive maintenance and data analysis. Follow along for insightful discussions, tutorials, and code snippets to sharpen your technical skills.
In our journey through Data Structures and Algorithms (DSA), we’ve explored arrays and strings—static data structures that store elements in a continuous block of memory. Now, it’s time to introduce a more flexible data structure: the Linked List.
Linked lists allow dynamic memory allocation, meaning elements can be scattered in memory, and linked together using pointers. This flexibility makes linked lists ideal for efficient insertion and deletion operations, especially when compared to arrays. Let's break down how linked lists work. Firstly..,
What is a Linked List?
A Linked List is a linear data structure where each element (called a node) contains two parts:
Data: The value of the element.
Pointer/Reference: A link to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each element points to the next one, forming a chain. This allows linked lists to grow or shrink dynamically during runtime.
Types of Linked Lists
Singly Linked List
A Singly Linked List is the simplest form of a linked list where each node points to the next node, and the last node points to
null. It's a one-way street!Insertion: Adding a new node at the head, tail, or any position requires adjusting pointers, but there’s no need to shift elements like in arrays.
Deletion: Removing a node is as simple as redirecting the pointer from the previous node to the next one.
Traversal: You can only traverse from the head node to the tail in one direction.
Basic operations in a singly linked list:
class Node:
def __init__(self, data):
# Initialize a new node with the given data and no next node
self.data = data # Store the data value in the node
self.next = None # Initialize the next pointer to None, indicating the end of the list
class SinglyLinkedList:
def __init__(self):
# Initialize an empty linked list with no head node
self.head = None # The head of the list is set to None, indicating the list is empty
# Insert a new node at the beginning of the list
def insert_at_head(self, data):
new_node = Node(data) # Create a new node with the given data
new_node.next = self.head # Point the new node's next to the current head
self.head = new_node # Update the head to be the new node
# Delete the first occurrence of a given value from the list
def delete_node(self, key):
temp = self.head # Start from the head of the list
# Check if the list is not empty and if the head needs to be deleted
if temp is not None:
if temp.data == key: # If the head node holds the value to be deleted
self.head = temp.next # Update the head to the next node
temp = None # Remove the reference to the deleted node
return # Exit the method since the node has been deleted
# Traverse the list to find the node to delete
while temp is not None:
if temp.data == key: # Check if the current node holds the value to be deleted
break # Exit the loop if the node is found
prev = temp # Keep track of the previous node
temp = temp.next # Move to the next node
# If we reached the end of the list without finding the key
if temp is None:
return # Exit since the value was not found in the list
# Remove the node from the list
prev.next = temp.next # Link the previous node to the node after the current node
temp = None # Remove the reference to the deleted node
Doubly Linked List
In a Doubly Linked List, each node contains two pointers—one that points to the next node and one that points to the previous node. This allows traversal in both directions.
Bidirectional traversal: Unlike the singly linked list, you can traverse both forward and backward.
Insertion and deletion: Similar to singly linked lists but require adjusting two pointers instead of one.
Basic operations in a doubly linked list:
class Node:
def __init__(self, data):
# Initialize a new node with the given data and no previous or next node
self.data = data # Store the data value in the node
self.prev = None # Initialize the previous pointer to None, indicating no previous node
self.next = None # Initialize the next pointer to None, indicating no next node
class DoublyLinkedList:
def __init__(self):
# Initialize an empty doubly linked list with no head node
self.head = None # The head of the list is set to None, indicating the list is empty
# Insert a new node at the beginning of the list
def insert_at_head(self, data):
new_node = Node(data) # Create a new node with the given data
if self.head is not None: # If the list is not empty
self.head.prev = new_node # Set the previous pointer of the current head to the new node
new_node.next = self.head # Point the new node's next to the current head
self.head = new_node # Update the head to be the new node
new_node.prev = None # The new head's previous node should be None
# Delete a node with a given value from the list
def delete_node(self, key):
temp = self.head # Start from the head of the list
# Traverse the list to find the node to delete
while temp is not None:
if temp.data == key: # Check if the current node holds the value to be deleted
# Node found; perform deletion
if temp.prev is not None:
temp.prev.next = temp.next # Link the previous node to the next node
if temp.next is not None:
temp.next.prev = temp.prev # Link the next node to the previous node
if temp == self.head: # If the node to delete is the head
self.head = temp.next # Update the head to the next node
temp = None # Remove the reference to the deleted node
return # Node deleted; exit function
temp = temp.next # Move to the next node
# Print the list in a readable format
def print_list(self):
temp = self.head # Start from the head of the list
while temp: # Traverse until the end of the list
print(temp.data, end=' <-> ') # Print the current node's data
temp = temp.next # Move to the next node
print('None') # Indicate the end of the list
Circular Linked List
In a Circular Linked List, the last node points back to the first node, creating a circular structure. Circular linked lists can either be singly or doubly linked. In a circular linked list:
The last node's next pointer points to the first node, forming a closed loop.
It can either be singly or doubly linked, depending on whether nodes point only to the next node or to both the next and previous nodes.
This structure is particularly useful in applications that require repeated cycling through a sequence, such as implementing a round-robin scheduling algorithm.
Basic operations in circular linked list:
class Node:
def __init__(self, data):
# Initialize a new node with the given data and no next node
self.data = data # Store the data value in the node
self.next = None # Initialize the next pointer to None, indicating no next node
class CircularLinkedList:
def __init__(self):
# Initialize an empty circular linked list with no head node
self.head = None # The head of the list is set to None, indicating the list is empty
# Insert a new node at the end of the circular linked list
def insert(self, data):
new_node = Node(data) # Create a new node with the given data
if not self.head: # If the list is empty
self.head = new_node # Set the new node as the head
new_node.next = self.head # Point the new node's next to itself (circular link)
else:
temp = self.head
while temp.next != self.head: # Traverse till the last node
temp = temp.next
temp.next = new_node # Last node's next becomes the new node
new_node.next = self.head # New node points back to the head
# Delete a node by its value from the circular linked list
def delete(self, key):
if self.head is None: # If the list is empty, nothing to delete
return
curr = self.head
prev = None
# If the node to be deleted is the head
if curr.data == key:
if curr.next == self.head: # Only one node in the list
self.head = None # Set head to None, indicating the list is now empty
else:
while curr.next != self.head: # Traverse to the last node
curr = curr.next
curr.next = self.head.next # Last node points to the second node
self.head = self.head.next # Update head to the next node
return
# Deleting a non-head node
curr = self.head
while curr.next != self.head and curr.data != key: # Traverse the list to find the node
prev = curr
curr = curr.next
if curr.data == key: # If the node to delete is found
prev.next = curr.next # Bypass the current node
else:
print(f"Node with value {key} not found") # If the node is not found
# Traverse and print the circular linked list
def print_list(self):
if not self.head: # If the list is empty
print("List is empty")
return
temp = self.head
while True: # Start from the head and loop through the list
print(temp.data, end=" -> ") # Print the current node's data
temp = temp.next # Move to the next node
if temp == self.head: # Stop once we circle back to the head
break
print() # Print a newline at the end
Advantages and disadvantages of Linked Lists
| Advantages | Disadvantages |
| Dynamic Size: Linked Lists can grow and shrink in size dynamically, allowing for efficient memory usage. | Memory Overhead: Each node in a linked list requires extra memory for a pointer/reference. |
| Efficient Insertions/Deletions: Adding or removing nodes can be done in constant time (O(1)) if the pointer/reference to the location is known. | No Direct Access: Elements must be accessed sequentially, leading to O(n) time complexity for searching. |
| No Predefined Size: Unlike arrays, linked lists do not require a fixed size at initialization. | Cache Locality: Linked lists do not have good locality of reference compared to arrays, which can affect performance. |
| Flexibility: Linked lists can easily implement complex data structures like stacks, queues, and graphs. | Complexity: Implementation and manipulation of linked lists can be more complex than arrays. |
| Circular Linked Lists allow traversal from any node to any other node, which can be useful in certain applications. | Potential Memory Leaks: If nodes are not properly deallocated, it can lead to memory leaks, especially in languages without garbage collection. |
Common Use Cases for Linked Lists
Implementation of stacks and queues.
Undo functionality in applications like text editors (using doubly linked lists).
Circular buffering (using circular linked lists).
Essential Resources for Mastering Linked Lists
Conclusion
Linked lists are an essential data structure for anyone diving into DSA. Their flexibility and efficiency make them suitable for dynamic scenarios, especially where frequent insertions and deletions are needed. However, the trade-off comes in terms of memory overhead and slower access times compared to arrays.
Next, we’ll explore more advanced data structures that build on these concepts, but for now, mastering linked lists is a crucial step in understanding the underlying mechanics of many algorithms and systems.
