Linked Lists — Singly, Doubly & Circular Guide
In this tutorial, you'll learn about Linked Lists. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A Linked List is a linear data structure where elements, called nodes, are connected via pointers. Unlike arrays, linked lists do not require contiguous memory — each node stores data and a reference to the next (and optionally previous) node.
What You'll Learn
You will learn to implement singly linked lists, doubly linked lists, and circular linked lists with insert, delete, and search operations, and understand their time and space complexity trade-offs.
Why It Matters
Linked lists provide O(1) insertions and deletions at known positions, making them ideal for scenarios where the data size changes frequently. They are the foundation for stacks, queues, and adjacency lists in graphs.
Real-World Use
Durga Antivirus Pro uses a doubly Linked List for its real-time file system watcher. When new files are created or modified, nodes are inserted into the watch list with O(1) cost. The linked structure allows efficient traversal without resizing.
Singly Linked List
Each node has data and a next pointer. Traversal is forward-only.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
node = Node(data)
node.next = self.head
self.head = node
def insert_at_tail(self, data):
if not self.head:
self.head = Node(data)
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = Node(data)
def delete(self, data):
if not self.head:
return
if self.head.data == data:
self.head = self.head.next
return
curr = self.head
while curr.next and curr.next.data != data:
curr = curr.next
if curr.next:
curr.next = curr.next.next
def search(self, data):
curr = self.head
while curr:
if curr.data == data:
return True
curr = curr.next
return False
def display(self):
elements = []
curr = self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
print(" -> ".join(elements) + " -> None")
sll = SinglyLinkedList()
sll.insert_at_tail(10)
sll.insert_at_tail(20)
sll.insert_at_head(5)
sll.display()
sll.delete(20)
sll.display()
print("Search 10:", sll.search(10))
print("Search 20:", sll.search(20))
Expected output:
5 -> 10 -> 20 -> None
5 -> 10 -> None
Search 10: True
Search 20: False
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
constructor() { this.head = null; }
insertAtHead(data) {
let node = new Node(data);
node.next = this.head;
this.head = node;
}
insertAtTail(data) {
if (!this.head) { this.head = new Node(data); return; }
let curr = this.head;
while (curr.next) curr = curr.next;
curr.next = new Node(data);
}
delete(data) {
if (!this.head) return;
if (this.head.data === data) { this.head = this.head.next; return; }
let curr = this.head;
while (curr.next && curr.next.data !== data) curr = curr.next;
if (curr.next) curr.next = curr.next.next;
}
display() {
let elements = [];
let curr = this.head;
while (curr) { elements.push(curr.data); curr = curr.next; }
console.log(elements.join(" -> ") + " -> null");
}
}
let sll = new SinglyLinkedList();
sll.insertAtTail(10);
sll.insertAtTail(20);
sll.insertAtHead(5);
sll.display();
sll.delete(20);
sll.display();
Expected output:
5 -> 10 -> 20 -> -> null
5 -> 10 -> -> null
Doubly Linked List
Each node has prev and next pointers, enabling bidirectional traversal. Insertions and deletions are more flexible but use extra memory.
class DoublyNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_head(self, data):
node = DoublyNode(data)
if not self.head:
self.head = self.tail = node
return
node.next = self.head
self.head.prev = node
self.head = node
def insert_at_tail(self, data):
node = DoublyNode(data)
if not self.tail:
self.head = self.tail = node
return
node.prev = self.tail
self.tail.next = node
self.tail = node
def delete(self, data):
curr = self.head
while curr:
if curr.data == data:
if curr.prev:
curr.prev.next = curr.next
else:
self.head = curr.next
if curr.next:
curr.next.prev = curr.prev
else:
self.tail = curr.prev
return
curr = curr.next
def display_forward(self):
elements = []
curr = self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
print(" <-> ".join(elements) + " -> None")
def display_backward(self):
elements = []
curr = self.tail
while curr:
elements.append(str(curr.data))
curr = curr.prev
print("None <- " + " <-> ".join(reversed(elements)))
dll = DoublyLinkedList()
dll.insert_at_tail(1)
dll.insert_at_tail(2)
dll.insert_at_head(0)
dll.display_forward()
dll.display_backward()
dll.delete(2)
dll.display_forward()
Expected output:
0 <-> 1 <-> 2 -> None
None <- 0 <-> 1 <-> 2
0 <-> 1 -> None
Circular Linked List
The last node points back to the head, forming a circle. Useful for round-robin scheduling and cyclic buffers.
class CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
node = Node(data)
if not self.head:
self.head = node
node.next = self.head
return
curr = self.head
while curr.next != self.head:
curr = curr.next
curr.next = node
node.next = self.head
def display(self):
if not self.head:
return
elements = []
curr = self.head
while True:
elements.append(str(curr.data))
curr = curr.next
if curr == self.head:
break
print(" -> ".join(elements) + " -> (back to head)")
cll = CircularLinkedList()
cll.insert(10)
cll.insert(20)
cll.insert(30)
cll.display()
Expected output:
10 -> 20 -> 30 -> (back to head)
Linked List vs Array
graph TD
A["Array: O(1) access, O(n) insert/delete"] --> B["Contiguous memory"]
C["Linked List: O(n) access, O(1) insert/delete"] --> D["Non-contiguous memory"]
style A fill:#4a90d9,stroke:#333,color:#fff
style C fill:#e67e22,stroke:#333,color:#fff
| Operation | Array | Singly Linked | Doubly Linked |
|---|---|---|---|
| Access by index | O(1) | O(n) | O(n) |
| Insert at head | O(n) | O(1) | O(1) |
| Insert at tail | O(1)* | O(1)** | O(1) |
| Delete at head | O(n) | O(1) | O(1) |
| Delete at tail | O(1) | O(n) | O(1) |
| Memory overhead | Low | Medium | High |
*Amortized. **With tail pointer.
Common Pitfalls
1. Losing the Head Pointer
When inserting at the head, always update self.head before assigning node.next. Order matters.
2. Null Pointer Dereference
Always check curr.next is not None before accessing curr.next.data. Traversing past the tail causes AttributeError.
3. Forgetting to Update Both Pointers in Doubly Linked Lists
When deleting a node, update both prev and next references. Missing one breaks the chain.
4. Infinite Loops in Circular Lists
Traversal conditions must detect the head node. Use while curr.next != self.head instead of while curr.next.
5. Memory Leaks in Garbage-Collected Languages
In languages without GC, you must explicitly free nodes. Python and JavaScript handle this, but be mindful in production systems.
Practice Questions
1. Reverse a singly Linked List.
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
2. Detect a cycle in a Linked List (Floyd's algorithm).
3. Find the middle of a Linked List in one pass.
4. Challenge: Implement an LRU (Least Recently Used) cache using a doubly Linked List and a hash map.
5. Real-world task: DodaZIP uses linked lists to manage the directory tree during archive extraction. Write a function that flattens a Linked List of nested directory nodes into a single-level list.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro