Exploring Time Complexity of Doubly Linked List Operations
This article is a complementary resource to the DSA with Python and DSA with C++ courses.
Exploring Time Complexity of Doubly Linked List Operations
In this article, we'll explore the time complexity of common doubly linked list operations (such as traversal, insertion, deletion, and search) to better understand their performance characteristics.
Traversal
Traversing a linked list involves visiting each element in a sequence. 
def traverse(self):
current = self.head
print("None", end = " <-> ")
while current is not None:
print(f"{current.data} <-> ", end="")
current = current.next
print("None")
void traverse() {
// Start traversal from head
Node<T>* current = head;
cout << "nullptr <-> ";
while (current != nullptr) {
cout << current->data << " <-> ";
// Move to the next node
current = current->next;
}
cout << "nullptr\n";
}
The total time required to traverse the list is proportional to the number of nodes. If the list contains n nodes, it results in a time complexity of O(n).
However, for an empty linked list (i.e., when the head is nullptr or None), the traversal loop does not execute, and the time complexity is O(1).
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 we can insert a node at the beginning of the linked list:
def insert_at_beginning(self, data):
# create new node
new_node = Node(data)
# update pointers
new_node.next = self.head
self.head.prev = new_node
# update head
self.head = new_node
void insert_at_beginning(T data){
// Create a new node to append
Node<T>* new_node = new Node<T>({data});
// If the list is empty
// new_node is both
// the head and tail
if (head == nullptr){
head = new_node;
tail = new_node;
return;
}
// head will be next to new_node
new_node->next = head;
// head is prev to new_node
head->prev = new_node;
// new_node is the head
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. So, this results in the time complexity of O(1) .
Insertion at the End
Here is how you can add a node to the end of a doubly linked list:
def append_node(self, data):
# initialize a new node
new_node = Node(data)
# update links
new_node.prev = self.tail
self.tail.next = new_node
# update tail
self.tail = new_node
void append(T data){
// Create a new node to append
Node<T>* new_node = new Node<T>({data});
// If the list is empty
// new_node is both the
// head and tail
if (head == nullptr){
head = new_node;
tail = new_node;
return;
}
// prev of new_node is the current tail
new_node->prev = tail;
// new_node is next to current tail
tail->next = new_node;
// new_node is the tail now
tail = new_node;
}
Inserting at the end of the doubly linked list only requires an update in the tail pointer, which is a constant time operation. So, this results in the time complexity of O(1).
Insertion at Other Positions
Here's how you can insert a node at a position other than beginning or the end of a doubly linked list:
def insert_at_position(self, position, data):
# create new node
new_node = Node(data)
# bring a pointer to desired position
current = self.head
for i in range(position - 1):
current = current.next
# get a pointer to the next node
next_node = current.next
# update pointers
current.next = new_node
next_node.prev = new_node
new_node.prev = current
new_node.next = next_node
void insert_at_position(T data, int position){
int i = 1;
// Start from the head
Node<T>* current = head;
while (i < position - 1){
// Move to next node
current = current -> next;
++i;
}
// Get a pointer to next node
Node<T>* next_node = current->next;
// new_node is next to current_node.
current->next = new_node;
// new_node is prev to next_node
next_node->prev = new_node;
// prev of new_node is current
new_node->prev = current;
// next of new_node is
// next of current node
new_node->next = next_node;
}
Inserting nodes at positions other than the beginning of the list requires:
- Traversing the list to locate the desired insertion point, which has a time complexity of
O(n). - Updating the pointer, which has a time complexity of
O(1).
As the total computing cost of this operation is dominated by the traversal, 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 list:
def append_to_empty(self, data):
new_node = Node(data)
self.head = new_node
self.tail = new_node
void insert_into_empty(T data) {
// Create a new node to append
Node<T>* new_node = new Node<T>({data});
if (head == nullptr){
head = new_node;
tail = new_node;
return;
}
}
Inserting into an empty linked list only requires an update in the head pointer, which is a constant time operation. So, this results in a time complexity of O(1).
Deletion
Deletion involves removing a node from the linked list. 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 doubly linked list:
def delete_from_beginning(self):
current = self.head
self.head = self.head.next
self.head.prev = None
# Update the next of current
current.next = None
void delete_from_beginning(){
if(head == nullptr) return;
// head is to be deleted
Node<T>* node_to_delete = head;
// next of head is the new head
head = head->next;
// prev of head is nullptr
head->prev = nullptr;
// Deallocate the memory
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. So, this results in the time complexity of O(1).
Deleting the Last Node
Here's how you can delete the last node of a doubly linked list:
def delete_from_end(self):
# Get reference to the tail node
current = self.tail
self.tail = self.tail.prev
self.tail.next = None
current.prev = None
void delete_from_end(){
// tail is the end node
Node<T>* node_to_delete = tail;
// New tail is the previous
// of the previous tail
tail = tail->prev;
tail->next = nullptr;
node_to_delete->prev = nullptr;
// Deallocate the memory
delete node_to_delete;
}
Deleting the last node of a linked list only requires an update in the tail pointer, which is a constant time operation. So, this results in the time complexity of O(1).
Deleting Nodes at Other Positions
Here is how you can delete a node of a doubly linked list in some position other than the beginning or the end of the list.
def delete_from_position(self, position):
current = self.head
prev_node = next_node = None
for i in range(position-1):
current = current.next
prev_node = current.prev
next_node = current.next
prev_node.next = next_node
next_node.prev = prev_node
current.next = None
current.prev = None
void delete_from_position(int position){
int i = 1;
Node<T>* current = head;
// Loop until we reach the position to delete
while (i < position){
// Move to next node
current = current->next;
++i;
}
// Get the pointer to prev and next of current node
Node<T>* prev_node = current->prev;
Node<T>* next_node = current->next;
// Update pointers
prev_node->next = next_node;
next_node->prev = prev_node;
// Deallocate the memory
delete current;
}
Deleting nodes at positions other than the beginning or the end requires
- Traversing the list to locate the node, which has the time complexity of
O(n). - Updating the pointers, which has a time complexity of
O(1).
As the total computing cost of this operation is dominated by the traversal, the time complexity of this entire operation is O(n).
Summary
| Operation | Time Complexity |
|---|---|
| Traversal | O(n) |
| Insertion at the Beginning | O(1) |
| Insertion at the End | O(1) |
| Insertion Into Other Nodes | O(n) |
| Insertion Into Empty Linked List | O(1) |
| Deletion at the Beginning | O(1) |
| Deletion at the End | O(1) |
| Deletion at Other Positions | O(n) |