Linked List Variations
Linked lists come in various forms, each designed to cater to different use cases
and performance requirements. These variations modify the structure or behavior
of the linked list to improve performance or add additional functionality.
1. Singly Linked List
As previously discussed, a singly linked list is the simplest form of a linked list. It
has nodes that store data and a reference (or pointer) to the next node in the list.
The last node points to null (or None in Python).
Advantages:
o Simple and easy to implement.
o Memory-efficient for simple operations like insertions and deletions
at the beginning.
Disadvantages:
o Can only be traversed in one direction.
o Limited access to nodes (no backward traversal).
Example: Already covered in earlier sections.
2. Doubly Linked List
In a doubly linked list, each node contains two pointers:
1. One points to the next node.
2. One points to the previous node.
This allows for traversal in both directions (forward and backward), making
operations like deletion more efficient.
Advantages:
o Allows bidirectional traversal.
, o Efficient deletion (can remove nodes from both ends without
traversal).
Disadvantages:
o Uses more memory per node (due to the extra pointer).
o Slightly slower operations due to the need to maintain two pointers.
Example: Already covered in earlier sections.
3. Circular Linked List
A circular linked list is a variation of a singly or doubly linked list where the last
node points back to the first node, forming a circle.
Singly Circular Linked List: Only the next pointer is used, and the last node
points back to the head.
Doubly Circular Linked List: Both next and prev pointers are used, and the
last node points back to the head, while the head points to the last node.
Advantages:
o Useful for applications that require continuous traversal (e.g., round-
robin scheduling).
o Efficient for cyclic buffers and circular queues.
Disadvantages:
o Can be tricky to detect the end of the list, especially in singly circular
linked lists.
o Extra logic required to prevent infinite loops during traversal.
Example (Singly Circular Linked List):
class CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
Linked lists come in various forms, each designed to cater to different use cases
and performance requirements. These variations modify the structure or behavior
of the linked list to improve performance or add additional functionality.
1. Singly Linked List
As previously discussed, a singly linked list is the simplest form of a linked list. It
has nodes that store data and a reference (or pointer) to the next node in the list.
The last node points to null (or None in Python).
Advantages:
o Simple and easy to implement.
o Memory-efficient for simple operations like insertions and deletions
at the beginning.
Disadvantages:
o Can only be traversed in one direction.
o Limited access to nodes (no backward traversal).
Example: Already covered in earlier sections.
2. Doubly Linked List
In a doubly linked list, each node contains two pointers:
1. One points to the next node.
2. One points to the previous node.
This allows for traversal in both directions (forward and backward), making
operations like deletion more efficient.
Advantages:
o Allows bidirectional traversal.
, o Efficient deletion (can remove nodes from both ends without
traversal).
Disadvantages:
o Uses more memory per node (due to the extra pointer).
o Slightly slower operations due to the need to maintain two pointers.
Example: Already covered in earlier sections.
3. Circular Linked List
A circular linked list is a variation of a singly or doubly linked list where the last
node points back to the first node, forming a circle.
Singly Circular Linked List: Only the next pointer is used, and the last node
points back to the head.
Doubly Circular Linked List: Both next and prev pointers are used, and the
last node points back to the head, while the head points to the last node.
Advantages:
o Useful for applications that require continuous traversal (e.g., round-
robin scheduling).
o Efficient for cyclic buffers and circular queues.
Disadvantages:
o Can be tricky to detect the end of the list, especially in singly circular
linked lists.
o Extra logic required to prevent infinite loops during traversal.
Example (Singly Circular Linked List):
class CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
