Theory
Linked List Representation
1. Singly Linked List (Node Class)
Singly Linked List 1
Copy
class ListNode:
def __init__(self, data, next=None):
self.data = data
self.next = next
def print_ll(head: ListNode):
while head is not None:
print(head.data, end=" ")
head = head.next
print()
def insert_at_start(head: ListNode, data) -> ListNode:
temp = ListNode(data, head)
return temp
def insert_at_end(head: ListNode, data) -> ListNode:
new_node = ListNode(data)
if head is None:
return new_node
current = head
while current.next is not None:
current = current.next
current.next = new_node
return new_node
def delete_tail(head: ListNode):
# Check if the linked list is empty or has only one node
if head is None or head.next is None:
return None
# Create a temporary pointer for traversal
temp = head
# Traverse the list until the second-to-last node
while temp.next.next is not None:
temp = temp.next
# Nullify the connection from the second-to-last node to delete the last node
temp.next = None
# Return the updated head of the linked list
return head
def delete_front(head: ListNode):
# Check if the linked list is empty or has only one node
if head is None:
return None
head = head.next
if __name__ == "__main__":
# Sample array and value for insertion
arr = [12, 8, 5, 7]
val = 100
# Creating a linked list with initial elements from the array
head = ListNode(12)
head.next = ListNode(8)
head.next.next = ListNode(5)
head.next.next.next = ListNode(7)
# Inserting a new node at the head of the linked list
head = insert_at_start(head, val)
# Printing the linked list
# print_ll(head)
insert_at_end(head, 10000)
print_ll(head)
print()
delete_tail(head)
print_ll(head)
2. Singly Linked List (Linked List Class)
Singly Linked List 2
Copy
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None # Initialize an empty list with no head
def insert_at_start(self, data) -> Node:
temp = Node(data, self.head)
return temp
def insert_at_end(self, data):
"""Insert a new node with the given data at the end of the list."""
new_node = Node(data)
if not self.head: # If the list is empty, make the new node the head
self.head = new_node
return
current = self.head
while current.next: # Traverse to the last node
current = current.next
current.next = new_node # Point the last node to the new node
def delete_from_end(self):
if self.head is None or self.head.next is None:
self.head = None
current = self.head
while current.next.next is not None:
current = current.next
current.next = None
return self.head
def delete_from_start(self):
if self.head is None:
return None
self.head = self.head.next
def length(self) -> int:
count = 0
current = self.head
while current is not None:
current = current.next
count += 1
return count
def print(self):
"""Print all the nodes in the linked list."""
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
if __name__ == "__main__":
ll = SinglyLinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.print() # Output: 1 -> 2 -> 3 -> None
print(ll.length())
ll.delete_from_end()
ll.print()
print(ll.length())
3. Doubly Linked List (DLLNode Class)
Doubly Linked List 1
Copy
class DLLNode:
def __init__(self, data, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev
def print_dll_forward(head: DLLNode):
while head is not None:
print(head.data, end=" ")
last = head
head = head.next
print()
return last if 'last' in locals() else None
def print_dll_backward(tail: DLLNode):
while tail is not None:
print(tail.data, end=" ")
tail = tail.prev
print()
def insert_at_start(head: DLLNode, data) -> DLLNode:
new_node = DLLNode(data, next=head)
if head:
head.prev = new_node
return new_node
def insert_at_end(head: DLLNode, data) -> DLLNode:
new_node = DLLNode(data)
if head is None:
return new_node
curr = head
while curr.next is not None:
curr = curr.next
curr.next = new_node
new_node.prev = curr
return head
def delete_tail(head: DLLNode) -> DLLNode:
if head is None or head.next is None:
return None
curr = head
while curr.next is not None:
curr = curr.next
if curr.prev:
curr.prev.next = None
return head
def delete_front(head: DLLNode) -> DLLNode:
if head is None:
return None
new_head = head.next
if new_head:
new_head.prev = None
return new_head
if __name__ == "__main__":
arr = [12, 8, 5, 7]
val = 100
head = DLLNode(12)
head = insert_at_end(head, 8)
head = insert_at_end(head, 5)
head = insert_at_end(head, 7)
head = insert_at_start(head, val)
print("Forward:", end=" ")
tail = print_dll_forward(head)
print("Backward:", end=" ")
print_dll_backward(tail)
head = insert_at_end(head, 10000)
print("After insert at end:", end=" ")
tail = print_dll_forward(head)
head = delete_tail(head)
print("After delete tail:", end=" ")
tail = print_dll_forward(head)
head = delete_front(head)
print("After delete front:", end=" ")
tail = print_dll_forward(head)
4. Doubly Linked List (DLL Class)
Doubly Linked List 2
Copy
class Node:
def __init__(self, data, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev
class DoublyLinkedList:
def __init__(self):
self.head = None # Initialize an empty list
def insert_at_start(self, data):
"""Insert a new node at the start of the list."""
new_node = Node(data, next=self.head)
if self.head:
self.head.prev = new_node # Update the previous pointer of the old head
self.head = new_node # Update the head to the new node
def insert_at_end(self, data):
"""Insert a new node at the end of the list."""
new_node = Node(data)
if not self.head: # If the list is empty, make the new node the head
self.head = new_node
return
current = self.head
while current.next: # Traverse to the last node
current = current.next
current.next = new_node # Point the last node to the new node
new_node.prev = current # Set the previous pointer of the new node
def delete_from_start(self):
"""Delete the node at the start of the list."""
if not self.head: # If the list is empty, do nothing
return
if not self.head.next: # If there's only one node, remove it
self.head = None
return
self.head = self.head.next # Update the head
self.head.prev = None # Remove the reference to the old head
def delete_from_end(self):
"""Delete the node at the end of the list."""
if not self.head: # If the list is empty, do nothing
return
if not self.head.next: # If there's only one node, remove it
self.head = None
return
current = self.head
while current.next: # Traverse to the last node
current = current.next
current.prev.next = None # Remove the last node
def length(self):
"""Return the length of the list."""
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
def print_forward(self):
"""Print all the nodes in the linked list from head to tail."""
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def print_backward(self):
"""Print all the nodes in the linked list from tail to head."""
current = self.head
if not current:
print("None")
return
while current.next: # Traverse to the last node
current = current.next
while current: # Traverse backward using prev pointers
print(current.data, end=" -> ")
current = current.prev
print("None")
if __name__ == "__main__":
# Example Usage
dll = DoublyLinkedList()
dll.insert_at_start(3)
dll.insert_at_start(2)
dll.insert_at_start(1)
dll.print_forward() # Output: 1 -> 2 -> 3 -> None
dll.print_backward() # Output: 3 -> 2 -> 1 -> None
dll.insert_at_end(4)
dll.insert_at_end(5)
dll.print_forward() # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None
dll.print_backward() # Output: 5 -> 4 -> 3 -> 2 -> 1 -> None
dll.delete_from_start()
dll.print_forward() # Output: 2 -> 3 -> 4 -> 5 -> None
dll.delete_from_end()
dll.print_forward() # Output: 2 -> 3 -> 4 -> None
Common Operations
ctd.Problems
Solution to All Linked List solutions Github
Easy Problems
- Inserting a node in LinkedList
- Deleting a node in LinkedList
2.2. Deleting a node(front,middle, end) in LinkedList - Find the length of the linkedlist
- Search an element in the LL
Doubly Linked List
Medium Problems
- Middle of a LinkedList [TortoiseHare Method]
- Reverse a LinkedList [Iterative]
- Reverse a LL [Recursive]
- Detect a loop in LL
- Find the starting point in LL
- Length of Loop in LL
- Check if LL is a palindrome or not
- Segregate odd and even nodes in LL
- Remove Nth node from the back of the LL
- Delete the middle node of LL
- Sort LL
- Sort a LL of 0’s 1’s and 2’s by changing links
- Find the intersection point of Y LL
- Add 1 to a number represented by LL
- Add 2 numbers in LL
Doubly Linked List
- Delete all occurrences of a key in DLL
- Find pairs with the given sum in DLL
- Remove duplicates from sorted DLL
- Add 2 numbers in a DLL