Linked lists are fundamental data structures that form the building blocks for many more complex data structures and algorithms. Unlike arrays, linked lists provide dynamic memory allocation and efficient insertions/deletions.
In this guide, we’ll explore singly linked lists, doubly linked lists, and circular linked lists—understanding their implementations, operations, time complexities, and when to use each type.
Understanding Linked Lists
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked lists don’t require contiguous memory allocation.
┌─────────────────────────────────────────────────────────────┐
│ Linked List Structure │
│ │
│ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │
│ │ 10 │ ───►│ 25 │ ───►│ 33 │ ───►│ 47 │ ───►│ 62 │ │
│ └────┘ └────┘ └────┘ └────┘ └────┘ │
│ │ │ │
│ HEAD nullptr │
│ │
│ Node: [Data | Next] │
└─────────────────────────────────────────────────────────────┘
Key Components
class Node:
"""A node in a linked list."""
def __init__(self, data):
self.data = data # The value stored in the node
self.next = None # Pointer to next node
def __repr__(self):
return f"Node({self.data})"
Singly Linked List
A singly linked list is the simplest form where each node points to the next node, and the last node points to null.
Implementation
class SinglyLinkedList:
"""Singly linked list implementation."""
def __init__(self):
self.head = None
self.size = 0
def is_empty(self) -> bool:
"""Check if list is empty."""
return self.head is None
def append(self, data) -> None:
"""Add element to end of list."""
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
self.size += 1
def prepend(self, data) -> None:
"""Add element to beginning of list."""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.size += 1
def delete(self, data) -> bool:
"""Delete first occurrence of data."""
if self.head is None:
return False
if self.head.data == data:
self.head = self.head.next
self.size -= 1
return True
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
self.size -= 1
return True
current = current.next
return False
def find(self, data) -> bool:
"""Check if data exists in list."""
current = self.head
while current:
if current.data == data:
return True
current = current.next
return False
def get(self, index) -> any:
"""Get element at index."""
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
current = self.head
for _ in range(index):
current = current.next
return current.data
def insert_at(self, index, data) -> None:
"""Insert element at specific index."""
if index < 0 or index > self.size:
raise IndexError("Index out of bounds")
if index == 0:
self.prepend(data)
return
new_node = Node(data)
current = self.head
for _ in range(index - 1):
current = current.next
new_node.next = current.next
current.next = new_node
self.size += 1
def reverse(self) -> None:
"""Reverse the linked list."""
previous = None
current = self.head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
self.head = previous
def __len__(self) -> int:
return self.size
def __iter__(self):
"""Iterate through list."""
current = self.head
while current:
yield current.data
current = current.next
def __repr__(self):
if self.is_empty():
return "Empty List"
nodes = []
current = self.head
while current:
nodes.append(str(current.data))
current = current.next
return " -> ".join(nodes) + " -> None"
Time Complexity
# Singly Linked List Complexity
operations = {
"Access by index": "O(n) - must traverse",
"Search": "O(n) - worst case",
"Insert at beginning": "O(1)",
"Insert at end": "O(n) - need traversal, O(1) with tail pointer",
"Insert at middle": "O(n) - need traversal to position",
"Delete at beginning": "O(1)",
"Delete at end": "O(n) - need traversal to find previous",
"Delete at middle": "O(n) - need traversal to position",
"Space": "O(n)"
}
Practical Example: Stack Implementation
class Stack:
"""Stack implemented using linked list."""
def __init__(self):
self._list = SinglyLinkedList()
def push(self, item):
"""Add item to top of stack."""
self._list.prepend(item)
def pop(self):
"""Remove and return top item."""
if self.is_empty():
raise IndexError("Pop from empty stack")
item = self._list.head.data
self._list.head = self._list.head.next
self._list.size -= 1
return item
def peek(self):
"""Return top item without removing."""
if self.is_empty():
raise IndexError("Peek from empty stack")
return self._list.head.data
def is_empty(self):
return self._list.is_empty()
def __len__(self):
return len(self._list)
# Usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop()) # 30
print(stack.pop()) # 20
print(stack.peek()) # 10
Doubly Linked List
A doubly linked list allows traversal in both directions. Each node contains pointers to both the next and previous nodes.
┌─────────────────────────────────────────────────────────────┐
│ Doubly Linked List │
│ │
│ nullptr◄──┌────┐──►┌────┐──►┌────┐──►┌────┐──► nullptr │
│ │ 10 │ │ 25 │ │ 33 │ │ 47 │ │
│ ◄────────┴────┴───┴────┴───┴────┴───┴────┘─────────► │
│ (prev) (prev) (prev) (prev) │
│ │
│ HEAD TAIL │
└─────────────────────────────────────────────────────────────┘
Implementation
class DNode:
"""Node in a doubly linked list."""
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def __repr__(self):
return f"DNode({self.data})"
class DoublyLinkedList:
"""Doubly linked list implementation."""
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def is_empty(self) -> bool:
return self.head is None
def append(self, data) -> None:
"""Add element to end of list."""
new_node = DNode(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.size += 1
def prepend(self, data) -> None:
"""Add element to beginning of list."""
new_node = DNode(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.size += 1
def delete(self, data) -> bool:
"""Delete first occurrence of data."""
if self.is_empty():
return False
current = self.head
while current:
if current.data == data:
if current.prev:
current.prev.next = current.next
else:
self.head = current.next
if current.next:
current.next.prev = current.prev
else:
self.tail = current.prev
self.size -= 1
return True
current = current.next
return False
def reverse(self) -> None:
"""Reverse the linked list."""
if self.is_empty():
return
current = self.head
self.head, self.tail = self.tail, self.head
while current:
current.prev, current.next = current.next, current.prev
current = current.prev
def __iter__(self):
current = self.head
while current:
yield current.data
current = current.next
def __reversed__(self):
"""Iterate in reverse."""
current = self.tail
while current:
yield current.data
current = current.prev
def __repr__(self):
return " <-> ".join(str(x) for x in self) + " <-> None"
Practical Example: Browser History
class BrowserHistory:
"""Browser history using doubly linked list."""
class HistoryNode:
def __init__(self, url):
self.url = url
self.prev = None
self.next = None
def __init__(self, homepage: str):
self.head = self.HistoryNode(homepage)
self.current = self.head
self.tail = self.head
def visit(self, url: str) -> None:
"""Visit a new URL."""
new_node = self.HistoryNode(url)
# Remove forward history
if self.current.next:
self.current.next.prev = None
self.current.next = None
# Add new page
new_node.prev = self.current
self.current.next = new_node
self.current = new_node
# Update tail if needed
if new_node.next is None:
self.tail = new_node
def back(self, steps: int) -> str:
"""Go back in history."""
for _ in range(steps):
if self.current.prev:
self.current = self.current.prev
return self.current.url
def forward(self, steps: int) -> str:
"""Go forward in history."""
for _ in range(steps):
if self.current.next:
self.current = self.current.next
return self.current.url
# Usage
browser = BrowserHistory("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.visit("stackoverflow.com")
print(browser.back(2)) # youtube.com
print(browser.forward(1)) # github.com
Circular Linked List
In a circular linked list, the last node points back to the first node, forming a circle.
┌─────────────────────────────────────────────────────────────┐
│ Circular Linked List │
│ │
│ ┌─────────────────────────────────────────┐ │
│ │ │ │
│ ▼ │ │
│ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ │
│ │ A │ ───►│ B │ ───►│ C │ ───►│ D │ ───┘ │
│ └────┘ └────┘ └────┘ └────┘ │
│ ▲ │ │
│ └───────────────────────────────────────────────┘ │
│ │
│ Last node points back to first │
└─────────────────────────────────────────────────────────────┘
Implementation
class CircularLinkedList:
"""Circular singly linked list."""
def __init__(self):
self.head = None
self.size = 0
def append(self, data) -> None:
"""Add element to end of circular list."""
new_node = Node(data)
if self.head is None:
new_node.next = new_node # Points to itself
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
self.size += 1
def delete(self, data) -> bool:
"""Delete first occurrence of data."""
if self.head is None:
return False
current = self.head
# If head needs to be deleted
if current.data == data:
if self.size == 1:
self.head = None
else:
# Find last node
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
self.size -= 1
return True
# Search for node to delete
while current.next != self.head:
if current.next.data == data:
current.next = current.next.next
self.size -= 1
return True
current = current.next
return False
def rotate(self, steps: int = 1) -> None:
"""Rotate list by moving head."""
if self.head is None or steps == 0:
return
steps = steps % self.size
current = self.head
for _ in range(self.size - steps - 1):
current = current.next
self.head = current.next
def __iter__(self):
if self.head is None:
return
current = self.head
while True:
yield current.data
current = current.next
if current == self.head:
break
def __repr__(self):
if self.head is None:
return "Empty List"
return " -> ".join(str(x) for x in self) + " -> (back to head)"
Practical Example: Round-Robin Scheduling
class RoundRobinScheduler:
"""CPU scheduler using round-robin."""
def __init__(self, quantum: int = 2):
self.quantum = quantum
self.tasks = CircularLinkedList()
def add_task(self, task_id: str) -> None:
"""Add a task to the queue."""
self.tasks.append(task_id)
def execute_next(self) -> str:
"""Execute next task in queue."""
if self.tasks.head is None:
return None
task = self.tasks.head.data
self.tasks.rotate(1)
return task
def get_queue(self) -> list:
"""Get current task queue."""
return list(self.tasks)
# Usage
scheduler = RoundRobinScheduler(quantum=2)
scheduler.add_task("Task-A")
scheduler.add_task("Task-B")
scheduler.add_task("Task-C")
print(scheduler.execute_next()) # Task-A
print(scheduler.execute_next()) # Task-B
print(scheduler.execute_next()) # Task-C
print(scheduler.execute_next()) # Task-A (wraps around)
Linked Lists vs Arrays
Understanding when to use linked lists versus arrays is crucial.
# Comparison
comparison = {
"access_by_index": {
"array": "O(1) - Direct access",
"linked_list": "O(n) - Must traverse"
},
"insertion_at_beginning": {
"array": "O(n) - Shift all elements",
"linked_list": "O(1) - Change head pointer"
},
"insertion_at_end": {
"array": "O(1) amortized (dynamic)",
"linked_list": "O(n) - Need traversal (O(1) with tail)"
},
"deletion_at_beginning": {
"array": "O(n) - Shift all elements",
"linked_list": "O(1) - Change head pointer"
},
"deletion_at_end": {
"array": "O(1)",
"linked_list": "O(n) - Need previous node"
},
"memory": {
"array": "Contiguous, fixed size",
"linked_list": "Scattered, dynamic"
},
"cache_friendliness": {
"array": "Excellent (contiguous)",
"linked_list": "Poor (scattered)"
},
"search": {
"array": "O(n) - linear, O(log n) - binary (sorted)",
"linked_list": "O(n) - linear only"
}
}
When to Use Linked Lists
# Use Linked Lists when:
good_use_cases:
- Frequent insertions/deletions at beginning
- Unknown size at compile time
- Memory is fragmented
- Implementing other data structures (stack, queue)
- Need to preserve insertion order with frequent changes
# Use Arrays when:
bad_use_cases:
- Random access is frequent
- Memory locality matters (cache performance)
- Size is fixed and known
- Searching is the primary operation
- Binary search is needed
Advanced Operations
Merge Two Sorted Lists
def merge_sorted_lists(list1: SinglyLinkedList,
list2: SinglyLinkedList) -> SinglyLinkedList:
"""Merge two sorted linked lists."""
result = SinglyLinkedList()
node1 = list1.head
node2 = list2.head
while node1 and node2:
if node1.data <= node2.data:
result.append(node1.data)
node1 = node1.next
else:
result.append(node2.data)
node2 = node2.next
# Append remaining nodes
while node1:
result.append(node1.data)
node1 = node1.next
while node2:
result.append(node2.data)
node2 = node2.next
return result
Detect Cycle (Floyd’s Algorithm)
def has_cycle(head: Node) -> bool:
"""Detect if linked list has a cycle using Floyd's algorithm."""
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next # Move one step
fast = fast.next.next # Move two steps
if slow == fast:
return True
return False
Find Middle Node
def find_middle(head: Node) -> Node:
"""Find middle node using slow/fast pointers."""
if not head:
return None
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Conclusion
Linked lists are essential data structures that offer dynamic memory allocation and efficient insertions/deletions. Key takeaways:
- Singly Linked List: Simple, memory-efficient, one-way traversal
- Doubly Linked List: Bidirectional traversal, useful for undo/redo, browser history
- Circular Linked List: Useful for round-robin scheduling, cycling through data
Understanding when to use linked lists versus arrays is crucial for writing efficient code. Use linked lists when you need frequent insertions/deletions and use arrays when you need fast random access.
Comments