DSA Linked List Operations
Beyond building a list, real programs need to insert, delete, traverse, and search linked lists efficiently and correctly.
The Four Core Operations
Every linked list implementation is built from four fundamental operations: traversing the list to visit each node, searching for a value, inserting a new node at a given position, and deleting a node. Mastering how these operations manipulate next pointers is the key to working confidently with any linked-list-based structure, including stacks, queues, and graphs.
Traversal and Search
Traversal starts at the head and follows next pointers until it reaches None, visiting every node exactly once in O(n) time. Search is traversal with an early exit: as soon as the target value is found, you can stop and report success instead of walking all the way to the end of the list.
- Traverse: start at head, follow next until None, visiting each node once.
- Search: traverse but stop and return early once the target value is found.
- Insert at head: create a new node whose next is the old head, then update head to point to the new node — O(1).
- Insert after a given node: point the new node's next at that node's next, then point that node's next at the new node — O(1) once you have the node.
- Delete at head: move head to head.next, letting the old head be garbage collected — O(1).
- Delete a node given its predecessor: point the predecessor's next past the deleted node — O(1) once you have the predecessor.
Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
def insert_at_head(head, value):
new_node = Node(value)
new_node.next = head
return new_node # new_node is the new head
def insert_after(node, value):
new_node = Node(value)
new_node.next = node.next
node.next = new_node
head = Node(20)
head = insert_at_head(head, 10) # 10 -> 20
insert_after(head, 15) # 10 -> 15 -> 20
current = head
while current:
print(current.value, end=" ")
current = current.next
# 10 15 20Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
def delete_at_head(head):
if head is None:
return None
return head.next # old head is dropped
def delete_after(node):
if node is not None and node.next is not None:
node.next = node.next.next
head = Node(10)
head.next = Node(15)
head.next.next = Node(20)
delete_after(head) # removes 15: 10 -> 20
head = delete_at_head(head) # removes 10: 20
print(head.value) # 20
print(head.next) # NoneTraversal, Search, Insert, and Delete Together
Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, value):
node = Node(value)
node.next = self.head
self.head = node
def search(self, value):
current = self.head
index = 0
while current is not None:
if current.value == value:
return index
current = current.next
index += 1
return -1
def delete(self, value):
if self.head is None:
return False
if self.head.value == value:
self.head = self.head.next
return True
previous = self.head
current = self.head.next
while current is not None:
if current.value == value:
previous.next = current.next
return True
previous = current
current = current.next
return False
def traverse(self):
values = []
current = self.head
while current is not None:
values.append(current.value)
current = current.next
return values
ll = LinkedList()
for value in [30, 20, 10]:
ll.insert_at_head(value)
print(ll.traverse()) # [10, 20, 30]
print(ll.search(20)) # 1
ll.delete(20)
print(ll.traverse()) # [10, 30]Exercise: DSA Linked List Operations
When inserting a new node at the head of a singly linked list, what must be updated?
