Can you remember what the Fragmentation is? We talked about in the previous post. Fragmentation happens when Data is not stored in consecutive Memory Cells, but is sliced and spread across Memory. You probably wonder how do we operate on such a disorder. The concept of Linked List (LL) is a great solution for this problem. This Data Structure comes in a few forms, which are: Singly Linked List, Doubly Linked List and Circular Linked List. They serve different purposes and let me go through them for you.
Basic element of the Linked List is called a Node. This structure may take one of two shapes. First one is a Node having reference to the next one, second shape has references for both next and previous Node.
Singly Linked List
A singly linked list is a linear structure in which each element (node) contains a data part and a link (or reference) pointing to the next node in the sequence. The last node’s link points to None, indicating the end of the 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):
"""Checks if the linked list is empty."""
return self.head is None
def append(self, data):
"""Adds a new node with the given data to the end of the list."""
new_node = Node(data)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, data):
"""Adds a new node with the given data to the beginning of the list."""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def delete(self, data):
"""Removes the first occurrence of a node with the given data."""
if self.is_empty():
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next and current.next.data != data:
current = current.next
if current.next:
current.next = current.next.next
def display(self):
"""Displays the elements of the linked list."""
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")Below you can see the example usage which demonstrates the basic operations of creating a singly linked list, appending and prepending elements, and deleting an element. Singly linked lists are versatile and efficient for many dynamic data storage scenarios.
# Create a singly linked list
my_list = SinglyLinkedList()
# Append elements
my_list.append(1)
my_list.append(2)
my_list.append(3)
# Prepend an element
my_list.prepend(0)
# Display the linked list: 0 -> 1 -> 2 -> 3 -> None
my_list.display()
# Delete an element
my_list.delete(2)
# Display the linked list after deletion: 0 -> 1 -> 3 -> None
my_list.display()
Doubly Linked List
A doubly linked list is a data structure in which each node contains a data element and two pointers, one pointing to the next node in the sequence, and another pointing to the previous node. This structure allows for easy traversal in both directions.
Below is a simple explanation of doubly linked lists along with code examples in Python for common operations such as insertion, deletion, and traversal. A node in a doubly linked list contains three fields:
- Data: The actual data stored in the node.
- Next: A pointer to the next node in the sequence.
- Prev: A pointer to the previous node in the sequence.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
"""Insert at the beginning"""
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_end(self, data):
"""Insert at the end"""
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
new_node.prev = current
def delete_node(self, key):
"""Delete a node"""
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
return
current = current.next
def display(self):
"""Display the doubly linked list"""
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()And now some usage examples.
# Create a doubly linked list
dll = DoublyLinkedList()
# Insert at the beginning
dll.insert_at_beginning(3)
dll.insert_at_beginning(2)
dll.insert_at_beginning(1)
# Insert at the end
dll.insert_at_end(4)
dll.insert_at_end(5)
# Display the doubly linked list
print("Doubly Linked List:")
dll.display()
# Delete a node
dll.delete_node(3)
# Display the doubly linked list after deletion
print("Doubly Linked List after deletion:")
dll.display()This code provides a basic implementation of a doubly linked list in Python with operations for insertion, deletion, and display. Feel free to customize and expand upon it based on your specific needs.
Circular Linked List
A circular linked list is a variation of a linked list in which the last node points back to the first node instead of having a None reference, creating a closed loop. Here’s an article with code examples in Python for a circular linked list, covering insertion, deletion, and traversal.
A node in a circular linked list contains two fields:
- Data: The actual data stored in the node.
- Next: A pointer to the next node in the sequence.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
"""Insert at the beginning"""
new_node = Node(data)
if not self.head:
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
self.head = new_node
def insert_at_end(self, data):
"""Insert at the end"""
new_node = Node(data)
if not self.head:
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_node(self, key):
"""Delete a node"""
if not self.head:
return
current = self.head
prev = None
while True:
if current.data == key:
if current == self.head:
temp = self.head
while temp.next != self.head:
temp = temp.next
if self.head == self.head.next:
self.head = None
else:
temp.next = self.head.next
self.head = self.head.next
else:
prev.next = current.next
return
elif current.next == self.head:
break
prev = current
current = current.next
def display(self):
"""Display the circular linked list"""
current = self.head
if not current:
return
while True:
print(current.data, end=" ")
current = current.next
if current == self.head:
break
print()Usage examples.
# Create a circular linked list
cll = CircularLinkedList()
# Insert at the beginning
cll.insert_at_beginning(3)
cll.insert_at_beginning(2)
cll.insert_at_beginning(1)
# Insert at the end
cll.insert_at_end(4)
cll.insert_at_end(5)
# Display the circular linked list
print("Circular Linked List:")
cll.display()
# Delete a node
cll.delete_node(3)
# Display the circular linked list after deletion
print("Circular Linked List after deletion:")
cll.display()
Real-World Use Cases of Linked Lists
In practical applications, linked lists find widespread use in various real-world scenarios due to their dynamic nature and efficient handling of insertions and deletions.
Memory Management in Operating Systems: Linked lists are fundamental in managing dynamic memory allocation and deallocation. They allow for the creation of data structures like free memory blocks and process control blocks.
File Systems: File systems often use linked lists to maintain the structure of directories and files. Each directory entry points to the next, forming a linked list.
Undo/Redo Functionality in Text Editors: Text editors use linked lists to implement undo and redo functionality. Each operation creates a new node, and the linked list keeps track of the sequence of changes.
Network Routing Tables: Linked lists are employed in routing tables to represent the connections between network nodes. This dynamic structure facilitates efficient updates in the case of network changes.
Music and Video Player Playlists: Playlists in music and video players are often implemented using linked lists. Each song or video is a node pointing to the next in the sequence.
Symbol Tables in Compilers: Compilers use symbol tables to manage variables and their scope. Linked lists help organize and navigate the symbol entries efficiently.
Dynamic Data Structures: In scenarios where the size of the data is unpredictable, linked lists provide an excellent choice. Examples include dynamic stacks, queues, and hash tables.
Job Scheduling in Operating Systems: Operating systems use linked lists to manage the order and priority of processes in the job scheduling queue.
Undo/Redo Functionality in Graphics Software: Graphics software often utilizes linked lists to implement undo and redo functionality for drawing and design operations.
Blockchain Technology: Some implementations of blockchain use linked lists to store the transaction history in a decentralized and secure manner.
Linked lists are not just abstract data structures but have practical applications in various fields. Their ability to adapt to changing data sizes and efficiently handle modifications makes them a valuable tool in real-world scenarios where dynamic and flexible data structures are required.
Summary
In conclusion, linked lists are dynamic data structures that offer flexibility in managing elements with efficient insertions and deletions. The basic building block is the node, which contains data and a reference to the next (and sometimes previous) node. Singly linked lists are simple and memory-efficient, while doubly linked lists provide bidirectional traversal. Circular linked lists form a closed loop.
Operations like insertion and deletion can be performed efficiently, making linked lists suitable for scenarios where the size is not known in advance or frequent modifications are expected. However, they may have drawbacks, such as slower random access and additional memory overhead.
In choosing a linked list type, consider the specific needs of the application. Linked lists play a crucial role in dynamic memory allocation and are particularly useful when managing changing datasets.