Exploring Time Complexity of Linked List Operations
This article is a complementary resource to the DSA with Python and DSA with C++ courses.
Exploring Time Complexity of Linked List Operations
In this article, we'll explore the time complexity of common linked list operations (such as traversal, insertion, deletion, and search) to better understand their performance characteristics.
Traversal
Here is how you can traverse a singly linked list.
def traverse_linked_list(self):
current = self.head
# Iterate until we reach the end node
while current:
print(f"{current.data}", end="->")
current = current.next
print(None)
void traverse_linked_list() {
Node<T>* current = head;
// Iterate until we reach the end node
while (current != nullptr) {
cout << current->data << "->";
current = current -> next;
}
cout << "nullptr";
}
Traversing a linked list involves visiting each element in sequence, which requires a constant amount of time for each node.
Since the list contains n nodes, the total time required to traverse the list is proportional to the number of nodes, resulting in a time complexity of O(n).
Insertion
Insertion involves adding a new node to the linked list. The time complexity of insertion depends on the location of the insertion point.
Insertion at the Beginning
Here is how you can insert a node at the beginning of a singly linked list:
def insert_node_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
# Update the head
self.head = new_node
// Inserts a node at the beginning of the list
void insert_node_at_beginning(T data) {
// Create a new node
Node<T>* new_node = new Node<T>({data});
// New node points to the former head
new_node->next = head;
// Head now points to the new node
head = new_node;
}
Inserting at the beginning of the linked list only requires an update in the head pointer, which is a constant time operation. This results in a time complexity of O(1).
Insertion at Other Positions
Here is how you can insert a node at a position other than the beginning of a singly linked list:
def insert_node_at_position(self, data, position):
new_node = Node(data)
current = self.head
for i in range(1, position -1 ):
current = current.next
new_node.next = current.next
current.next = new_node
// Inserts a node at a specific position (1-based index)
void insert_node_at_position(T data, int position) {
// If inserting at the beginning,
// call insert_at_begining
if (position == 1) {
insert_node_at_beginning(data);
return;
}
// Create a new node
Node<T>* new_node = new Node<T>({data});
Node<T>* current = head;
int i = 1;
// Traverse to the position
// before where the new node will be inserted
while (i < position - 1) {
current = current->next;
++i;
}
// Insert the new node in its correct position
new_node->next = current->next;
current->next = new_node;
}
Inserting nodes at positions other than the beginning requires traversing the list to locate the desired insertion point, which has a time complexity of O(n).
On the other hand, updating the pointers has a time complexity of O(1).
Since the total computing cost of this operation is dominated by traversal itself, the time complexity of this entire operation is O(n).
Insertion Into an Empty Linked List
Here is how you can insert a node into an empty linked list:
def append_into_empty(self, data):
new_node = Node(data)
self.head = new_node
void append_into_empty(T data){
Node<T>* new_node = new Node<T>({data});
head = new_node;
}
Inserting into an empty linked list only requires an update in the head pointer, which is a constant time operation. This results in the time complexity of O(1).
Deletion
Deletion involves removing a node from the linked list. Like with insertion, the time complexity of deletion depends on the location of the node to be deleted.
Deleting the First Node
Here is how you can delete the first node from a singly linked list:
def delete_first_node(self):
if self.head:
# make second node as new head node
self.head = self.head.next
// Deletes the first node of the list
void delete_first_node() {
if (head == nullptr) return;
Node<T>* node_to_delete = head;
// Head is moved to the second node
head = head->next;
// Delete the former head node
delete node_to_delete;
}
Deleting the first node of a linked list only requires an update in the head pointer, which is a constant time operation. This results in the time complexity of O(1).
Deleting Other Nodes
Here's how you can delete nodes at positions other than the beginning of the linked list:
def delete_node(self, position):
# Traverse the list to find the node before the one to be deleted
for i in range(1, position - 1):
# condition to handle if position
# is greater than number of nodes
if not current.next:
return
current = current.next
if current.next:
current.next = current.next.next
// Delete a node at a specified position (1- based index)
void delete_node(int position) {
Node<T>* current = head;
int i = 1;
// If position is valid,
// Traverse to the node before the one to be deleted
while (i < position - 1) {
current = current->next;
++i;
}
Node<T>* node_to_delete = current->next;
current->next = node_to_delete->next;
delete node_to_delete;
}
Deleting nodes at positions other than the beginning requires traversing the list to locate the node, which has a time complexity of O(n).
And, updating the pointers has the time complexity of O(1).
Since the total computing cost of this operation is dominated by traversal itself, the time complexity of this entire operation is O(n).
Summary
| Operation | Time Complexity |
|---|---|
| Traversal | O(n) |
| Insertion at Beginning | O(1) |
| Insertion at Other Positions | O(n) |
| Insertion Into an Empty Linked List | O(1) |
| Deletion at Beginning | O(1) |
| Deletion at Other Positions | O(n) |