Table of Contents
Introduction
A Linked List is a linear data structure where elements are stored in nodes. Unlike arrays, linked list elements are not stored in contiguous memory locations. Each node contains data and a reference (pointer) to the next node in the sequence.
Advantages over Arrays:
- Dynamic size (no need to declare size initially)
- Easy insertion/deletion at any position
- No memory wastage
Disadvantages:
- No random access (must traverse from head)
- Extra memory for storing pointers
- Not cache-friendly
Singly Linked List
A singly linked list is a type of linked list where each node contains data and a reference to the next node.
Structure
[Data | Next] -> [Data | Next] -> [Data | Next] -> NoneImplementation
class Node:
"""Node class for Singly Linked List"""
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
"""Singly Linked List Implementation"""
def __init__(self):
self.head = None
self.size = 0
def is_empty(self):
"""Check if the linked list is empty"""
return self.head is None
def get_size(self):
"""Return the size of the linked list"""
return self.size
# ==================== Insertion Operations ====================
def insert_at_beginning(self, data):
"""Insert a node at the beginning - O(1)"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.size += 1
def insert_at_end(self, data):
"""Insert a node at the end - O(n)"""
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
self.size += 1
def insert_at_position(self, data, position):
"""Insert a node at a specific position - O(n)"""
if position < 0 or position > self.size:
raise IndexError("Position out of bounds")
if position == 0:
self.insert_at_beginning(data)
return
new_node = Node(data)
current = self.head
for _ in range(position - 1):
current = current.next
new_node.next = current.next
current.next = new_node
self.size += 1
def insert_after_value(self, target_value, data):
"""Insert a node after a specific value - O(n)"""
if self.is_empty():
raise ValueError("List is empty")
current = self.head
while current:
if current.data == target_value:
new_node = Node(data)
new_node.next = current.next
current.next = new_node
self.size += 1
return
current = current.next
raise ValueError(f"Value {target_value} not found in the list")
# ==================== Deletion Operations ====================
def delete_at_beginning(self):
"""Delete the first node - O(1)"""
if self.is_empty():
raise IndexError("Cannot delete from empty list")
deleted_data = self.head.data
self.head = self.head.next
self.size -= 1
return deleted_data
def delete_at_end(self):
"""Delete the last node - O(n)"""
if self.is_empty():
raise IndexError("Cannot delete from empty list")
if self.head.next is None:
deleted_data = self.head.data
self.head = None
self.size -= 1
return deleted_data
current = self.head
while current.next.next:
current = current.next
deleted_data = current.next.data
current.next = None
self.size -= 1
return deleted_data
def delete_at_position(self, position):
"""Delete a node at a specific position - O(n)"""
if position < 0 or position >= self.size:
raise IndexError("Position out of bounds")
if position == 0:
return self.delete_at_beginning()
current = self.head
for _ in range(position - 1):
current = current.next
deleted_data = current.next.data
current.next = current.next.next
self.size -= 1
return deleted_data
def delete_by_value(self, value):
"""Delete the first occurrence of a value - O(n)"""
if self.is_empty():
raise ValueError("List is empty")
if self.head.data == value:
return self.delete_at_beginning()
current = self.head
while current.next:
if current.next.data == value:
deleted_data = current.next.data
current.next = current.next.next
self.size -= 1
return deleted_data
current = current.next
raise ValueError(f"Value {value} not found in the list")
# ==================== Search Operations ====================
def search(self, value):
"""Search for a value and return its position - O(n)"""
current = self.head
position = 0
while current:
if current.data == value:
return position
current = current.next
position += 1
return -1
def get_at_position(self, position):
"""Get the value at a specific position - O(n)"""
if position < 0 or position >= self.size:
raise IndexError("Position out of bounds")
current = self.head
for _ in range(position):
current = current.next
return current.data
# ==================== Utility Operations ====================
def reverse(self):
"""Reverse the linked list - O(n)"""
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev
def get_middle(self):
"""Get the middle element using slow-fast pointer - O(n)"""
if self.is_empty():
return None
slow = fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.data
def detect_cycle(self):
"""Detect if there's a cycle using Floyd's algorithm - O(n)"""
if self.is_empty():
return False
slow = fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def remove_duplicates(self):
"""Remove duplicates from a sorted list - O(n)"""
current = self.head
while current and current.next:
if current.data == current.next.data:
current.next = current.next.next
self.size -= 1
else:
current = current.next
def display(self):
"""Display the linked list - O(n)"""
if self.is_empty():
print("List is empty")
return
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print(" -> ".join(elements) + " -> None")
def to_list(self):
"""Convert linked list to Python list - O(n)"""
result = []
current = self.head
while current:
result.append(current.data)
current = current.next
return result
def __str__(self):
"""String representation"""
return " -> ".join(str(x) for x in self.to_list()) + " -> None"
def __len__(self):
"""Return length of the list"""
return self.size
def __iter__(self):
"""Make the list iterable"""
current = self.head
while current:
yield current.data
current = current.nextUsage Example
# Create a singly linked list
sll = SinglyLinkedList()
# Insert elements
sll.insert_at_end(10)
sll.insert_at_end(20)
sll.insert_at_end(30)
sll.insert_at_beginning(5)
sll.insert_at_position(15, 2)
print("Original list:")
sll.display() # Output: 5 -> 10 -> 15 -> 20 -> 30 -> None
# Delete elements
sll.delete_by_value(15)
print("\nAfter deleting 15:")
sll.display() # Output: 5 -> 10 -> 20 -> 30 -> None
# Search
position = sll.search(20)
print(f"\n20 found at position: {position}") # Output: 2
# Reverse
sll.reverse()
print("\nReversed list:")
sll.display() # Output: 30 -> 20 -> 10 -> 5 -> None
# Get middle element
middle = sll.get_middle()
print(f"\nMiddle element: {middle}") # Output: 20Time Complexity Summary
| Operation | Time Complexity |
|---|---|
| Insert at beginning | O(1) |
| Insert at end | O(n) |
| Insert at position | O(n) |
| Delete at beginning | O(1) |
| Delete at end | O(n) |
| Delete at position | O(n) |
| Search | O(n) |
| Reverse | O(n) |
| Access by index | O(n) |
Doubly Linked List
A doubly linked list is a type of linked list where each node contains data and two references: one to the next node and one to the previous node.
Structure
None <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> NoneAdvantages over Singly Linked List:
- Can traverse in both directions
- Deletion is more efficient (no need to track previous node)
- Can insert before a given node easily
Disadvantages:
- Extra memory for storing previous pointer
- More complex implementation
Implementation
class DoublyNode:
"""Node class for Doubly Linked List"""
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
"""Doubly Linked List Implementation"""
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def is_empty(self):
"""Check if the linked list is empty"""
return self.head is None
def get_size(self):
"""Return the size of the linked list"""
return self.size
# ==================== Insertion Operations ====================
def insert_at_beginning(self, data):
"""Insert a node at the beginning - O(1)"""
new_node = DoublyNode(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 insert_at_end(self, data):
"""Insert a node at the end - O(1)"""
new_node = DoublyNode(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 insert_at_position(self, data, position):
"""Insert a node at a specific position - O(n)"""
if position < 0 or position > self.size:
raise IndexError("Position out of bounds")
if position == 0:
self.insert_at_beginning(data)
return
if position == self.size:
self.insert_at_end(data)
return
new_node = DoublyNode(data)
current = self.head
for _ in range(position):
current = current.next
new_node.prev = current.prev
new_node.next = current
current.prev.next = new_node
current.prev = new_node
self.size += 1
def insert_after_value(self, target_value, data):
"""Insert a node after a specific value - O(n)"""
if self.is_empty():
raise ValueError("List is empty")
current = self.head
while current:
if current.data == target_value:
new_node = DoublyNode(data)
new_node.prev = current
new_node.next = current.next
if current.next:
current.next.prev = new_node
else:
self.tail = new_node
current.next = new_node
self.size += 1
return
current = current.next
raise ValueError(f"Value {target_value} not found in the list")
def insert_before_value(self, target_value, data):
"""Insert a node before a specific value - O(n)"""
if self.is_empty():
raise ValueError("List is empty")
current = self.head
while current:
if current.data == target_value:
new_node = DoublyNode(data)
new_node.next = current
new_node.prev = current.prev
if current.prev:
current.prev.next = new_node
else:
self.head = new_node
current.prev = new_node
self.size += 1
return
current = current.next
raise ValueError(f"Value {target_value} not found in the list")
# ==================== Deletion Operations ====================
def delete_at_beginning(self):
"""Delete the first node - O(1)"""
if self.is_empty():
raise IndexError("Cannot delete from empty list")
deleted_data = self.head.data
if self.head == self.tail:
self.head = self.tail = None
else:
self.head = self.head.next
self.head.prev = None
self.size -= 1
return deleted_data
def delete_at_end(self):
"""Delete the last node - O(1)"""
if self.is_empty():
raise IndexError("Cannot delete from empty list")
deleted_data = self.tail.data
if self.head == self.tail:
self.head = self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.size -= 1
return deleted_data
def delete_at_position(self, position):
"""Delete a node at a specific position - O(n)"""
if position < 0 or position >= self.size:
raise IndexError("Position out of bounds")
if position == 0:
return self.delete_at_beginning()
if position == self.size - 1:
return self.delete_at_end()
current = self.head
for _ in range(position):
current = current.next
deleted_data = current.data
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
return deleted_data
def delete_by_value(self, value):
"""Delete the first occurrence of a value - O(n)"""
if self.is_empty():
raise ValueError("List is empty")
current = self.head
while current:
if current.data == value:
if current == self.head:
return self.delete_at_beginning()
elif current == self.tail:
return self.delete_at_end()
else:
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
return current.data
current = current.next
raise ValueError(f"Value {value} not found in the list")
# ==================== Search Operations ====================
def search(self, value):
"""Search for a value and return its position - O(n)"""
current = self.head
position = 0
while current:
if current.data == value:
return position
current = current.next
position += 1
return -1
def get_at_position(self, position):
"""Get the value at a specific position - O(n)"""
if position < 0 or position >= self.size:
raise IndexError("Position out of bounds")
# Optimize: start from tail if position is in second half
if position < self.size // 2:
current = self.head
for _ in range(position):
current = current.next
else:
current = self.tail
for _ in range(self.size - position - 1):
current = current.prev
return current.data
# ==================== Utility Operations ====================
def reverse(self):
"""Reverse the doubly linked list - O(n)"""
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 get_middle(self):
"""Get the middle element using slow-fast pointer - O(n)"""
if self.is_empty():
return None
slow = fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.data
def remove_duplicates(self):
"""Remove duplicates from a sorted list - O(n)"""
current = self.head
while current and current.next:
if current.data == current.next.data:
node_to_delete = current.next
current.next = node_to_delete.next
if node_to_delete.next:
node_to_delete.next.prev = current
else:
self.tail = current
self.size -= 1
else:
current = current.next
def display_forward(self):
"""Display the linked list forward - O(n)"""
if self.is_empty():
print("List is empty")
return
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print("None <- " + " <-> ".join(elements) + " -> None")
def display_backward(self):
"""Display the linked list backward - O(n)"""
if self.is_empty():
print("List is empty")
return
elements = []
current = self.tail
while current:
elements.append(str(current.data))
current = current.prev
print("None <- " + " <-> ".join(elements) + " -> None")
def to_list(self):
"""Convert linked list to Python list - O(n)"""
result = []
current = self.head
while current:
result.append(current.data)
current = current.next
return result
def __str__(self):
"""String representation"""
return " <-> ".join(str(x) for x in self.to_list())
def __len__(self):
"""Return length of the list"""
return self.size
def __iter__(self):
"""Make the list iterable (forward)"""
current = self.head
while current:
yield current.data
current = current.next
def reverse_iter(self):
"""Iterate backward"""
current = self.tail
while current:
yield current.data
current = current.prevUsage Example
# Create a doubly linked list
dll = DoublyLinkedList()
# Insert elements
dll.insert_at_end(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.insert_at_beginning(5)
dll.insert_at_position(15, 2)
print("Original list (forward):")
dll.display_forward() # Output: None <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> None
print("\nOriginal list (backward):")
dll.display_backward() # Output: None <- 30 <-> 20 <-> 15 <-> 10 <-> 5 -> None
# Delete elements
dll.delete_by_value(15)
print("\nAfter deleting 15:")
dll.display_forward() # Output: None <- 5 <-> 10 <-> 20 <-> 30 -> None
# Insert before value
dll.insert_before_value(20, 15)
print("\nAfter inserting 15 before 20:")
dll.display_forward() # Output: None <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> None
# Reverse
dll.reverse()
print("\nReversed list:")
dll.display_forward() # Output: None <- 30 <-> 20 <-> 15 <-> 10 <-> 5 -> None
# Iterate backward
print("\nBackward iteration:")
for value in dll.reverse_iter():
print(value, end=" ") # Output: 5 10 15 20 30Time Complexity Summary
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Insert at beginning | O(1) | O(1) |
| Insert at end | O(n) | O(1) ⭐ |
| Insert at position | O(n) | O(n) |
| Delete at beginning | O(1) | O(1) |
| Delete at end | O(n) | O(1) ⭐ |
| Delete at position | O(n) | O(n) |
| Search | O(n) | O(n) |
| Reverse | O(n) | O(n) |
Comparison
Singly Linked List vs Doubly Linked List
| Feature | Singly Linked List | Doubly Linked List |
|---|---|---|
| Pointers per node | 1 (next) | 2 (next, prev) |
| Memory usage | Less | More |
| Traversal | Forward only | Both directions |
| Insertion at end | O(n) without tail | O(1) with tail |
| Deletion at end | O(n) | O(1) with tail |
| Complexity | Simpler | More complex |
| Use cases | Stack, simple lists | LRU Cache, Browser history |
When to Use Which?
Use Singly Linked List when:
- Memory is limited
- You only need forward traversal
- Implementing a stack
- Simple data structure requirements
Use Doubly Linked List when:
- You need bidirectional traversal
- Frequent deletions at both ends
- Implementing LRU cache, deque, browser history
- Navigation is important (undo/redo operations)
Common Interview Problems
1. Reverse a Linked List
def reverse_linked_list(head):
"""Reverse a singly linked list - O(n) time, O(1) space"""
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev2. Detect Cycle in Linked List (Floyd’s Cycle Detection)
def has_cycle(head):
"""Detect cycle using slow-fast pointer - O(n) time, O(1) space"""
if not head or not head.next:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False3. Find Middle of Linked List
def find_middle(head):
"""Find middle using slow-fast pointer - O(n) time, O(1) space"""
if not head:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow4. Merge Two Sorted Linked Lists
def merge_sorted_lists(l1, l2):
"""Merge two sorted linked lists - O(n+m) time, O(1) space"""
dummy = Node(0)
current = dummy
while l1 and l2:
if l1.data <= l2.data:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next5. Remove Nth Node From End
def remove_nth_from_end(head, n):
"""Remove nth node from end - O(n) time, O(1) space"""
dummy = Node(0)
dummy.next = head
first = second = dummy
# Move first n+1 steps ahead
for _ in range(n + 1):
if first is None:
return head
first = first.next
# Move both pointers
while first:
first = first.next
second = second.next
# Remove the node
second.next = second.next.next
return dummy.next6. Check if Linked List is Palindrome
def is_palindrome(head):
"""Check if linked list is palindrome - O(n) time, O(1) space"""
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
current = slow
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
# Compare both halves
left, right = head, prev
while right:
if left.data != right.data:
return False
left = left.next
right = right.next
return True7. Intersection of Two Linked Lists
def get_intersection_node(headA, headB):
"""Find intersection point - O(m+n) time, O(1) space"""
if not headA or not headB:
return None
ptrA, ptrB = headA, headB
# When one pointer reaches end, redirect to other head
while ptrA != ptrB:
ptrA = ptrA.next if ptrA else headB
ptrB = ptrB.next if ptrB else headA
return ptrA # Either intersection node or None8. Remove Duplicates from Sorted List
def remove_duplicates(head):
"""Remove duplicates from sorted list - O(n) time, O(1) space"""
current = head
while current and current.next:
if current.data == current.next.data:
current.next = current.next.next
else:
current = current.next
return head9. Add Two Numbers Represented as Linked Lists
def add_two_numbers(l1, l2):
"""Add two numbers represented as linked lists - O(max(m,n)) time"""
dummy = Node(0)
current = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.data if l1 else 0
val2 = l2.data if l2 else 0
total = val1 + val2 + carry
carry = total // 10
current.next = Node(total % 10)
current = current.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next10. Rotate Linked List
def rotate_right(head, k):
"""Rotate linked list to the right by k places - O(n) time"""
if not head or not head.next or k == 0:
return head
# Find length and make it circular
length = 1
current = head
while current.next:
current = current.next
length += 1
current.next = head # Make circular
# Find new tail: (length - k % length - 1)th node
k = k % length
steps_to_new_tail = length - k - 1
new_tail = head
for _ in range(steps_to_new_tail):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head11. Clone a Linked List with Random Pointer
class RandomNode:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def copy_random_list(head):
"""Clone a linked list with random pointer - O(n) time, O(n) space"""
if not head:
return None
# Create mapping from old nodes to new nodes
old_to_new = {}
# First pass: create all nodes
current = head
while current:
old_to_new[current] = RandomNode(current.data)
current = current.next
# Second pass: assign next and random pointers
current = head
while current:
if current.next:
old_to_new[current].next = old_to_new[current.next]
if current.random:
old_to_new[current].random = old_to_new[current.random]
current = current.next
return old_to_new[head]12. Flatten a Multilevel Doubly Linked List
def flatten(head):
"""Flatten a multilevel doubly linked list - O(n) time, O(n) space"""
if not head:
return None
stack = []
current = head
while current:
if current.child:
if current.next:
stack.append(current.next)
current.next = current.child
current.child.prev = current
current.child = None
if not current.next and stack:
next_node = stack.pop()
current.next = next_node
next_node.prev = current
current = current.next
return headAdditional Tips
Memory Management
- In Python, garbage collection handles memory automatically
- Break circular references before deleting (set references to None)
- Use
delto explicitly remove references if needed
Best Practices
- Always check for empty list before operations
- Handle edge cases (single node, two nodes)
- Update size counter consistently
- Maintain both head and tail pointers for doubly linked lists
- Use dummy/sentinel nodes for simplification in certain algorithms
Common Mistakes to Avoid
- Losing reference to head while traversing
- Not updating tail pointer in doubly linked list
- Forgetting to update previous pointers in doubly linked list
- Off-by-one errors in position-based operations
- Not handling None values properly
Practice Problems
- LeetCode Easy:
- Reverse Linked List (206)
- Merge Two Sorted Lists (21)
- Remove Duplicates from Sorted List (83)
- Linked List Cycle (141)
- Palindrome Linked List (234)
- LeetCode Medium:
- Add Two Numbers (2)
- Remove Nth Node From End (19)
- Rotate List (61)
- Swap Nodes in Pairs (24)
- Reorder List (143)
- LeetCode Hard:
- Merge k Sorted Lists (23)
- Reverse Nodes in k-Group (25)
- Copy List with Random Pointer (138)
Conclusion
Linked lists are fundamental data structures that provide flexibility in memory allocation and efficient insertion/deletion operations. While they have drawbacks like no random access and extra memory for pointers, they excel in scenarios requiring dynamic size and frequent modifications.
Key Takeaways:
- Singly linked lists are simpler and use less memory
- Doubly linked lists allow bidirectional traversal and more efficient operations
- Master the two-pointer technique for many linked list problems
- Practice edge cases: empty list, single node, two nodes
- Understand when to use linked lists over arrays
Happy Coding! 🚀
Discover more from Altgr Blog
Subscribe to get the latest posts sent to your email.
