Linked Lists
Singly Linked List
A Singly Linked List is a simple data structure where each node contains data and a reference to the next node in the sequence. This structure is ideal when you only need forward traversal of the list.
Space Complexity: O(n)
Time Complexity: O(n) for traversal
Best Case: Ω(1)
Average Case: Θ(n)
Worst Case: O(n)
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example Usage
sll = SinglyLinkedList()
for i in range(20):
sll.append(random.randint(0, 100))
sll.display()
Doubly Linked List
A Doubly Linked List is a more complex structure where each node contains references to both the previous and next nodes. This allows for traversal in both directions, making it more versatile for certain algorithms.
Space Complexity: O(n)
Time Complexity: O(n) for traversal
Best Case: Ω(1)
Average Case: Θ(n)
Worst Case: O(n)
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def display(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
# Example Usage
dll = DoublyLinkedList()
for i in range(20):
dll.append(random.randint(0, 100))
dll.display()
Singly Circular Linked List
A Singly Circular Linked List is similar to a singly linked list, but with the last node pointing back to the first node, creating a loop. This is useful in scenarios where the list needs to be traversed in a circular manner, such as in round-robin scheduling.
Space Complexity: O(n)
Time Complexity: O(n) for traversal
Best Case: Ω(1)
Average Case: Θ(n)
Worst Case: O(n)
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyCircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.head.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 display(self):
if not self.head:
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print(current.data + " (head)")
Doubly Circular Linked List
A Doubly Circular Linked List combines the features of a doubly linked list and a circular linked list. It allows traversal in both directions and ensures that the last node points back to the first. This structure is useful when you need to traverse data both forwards and backwards in a circular loop.
Space Complexity: O(n)
Time Complexity: O(n) for traversal
Best Case: Ω(1)
Average Case: Θ(n)
Worst Case: O(n)
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyCircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data);
if (!this.head) {
this.head = new_node;
this.head.next = this.head;
this.head.prev = this.head;
} else {
let current = this.head;
while (current.next !== this.head) {
current = current.next;
}
current.next = new_node;
new_node.prev = current;
new_node.next = this.head;
this.head.prev = new_node;
}
}
display() {
if (!this.head) return 'Empty List';
const elements: number[] = [];
let current = this.head;
do {
elements.push(current.data);
current = current.next!;
} while (current !== this.head);
return elements.join(' <-> ') + ' <-> (head)';
}
}