Basic List Operations Time Complexity

The next table shows the time complexity of basic operations for linked lists.

Search Operation

Searching in a linked list involves traversing the list from the beginning until the desired element is found. This operation has a time complexity of O(n) in both the worst and average cases. Unlike arrays, linked lists do not support direct access to elements based on their index, resulting in linear time complexity for searching.

Insert Operation

Inserting an element into a linked list can be done efficiently by updating only a few pointers. Specifically, we need to update the pointer of the element after which we are inserting the new element, ensuring it points to the new element, and the pointer of the new element must point to the next element in the list. This operation has a time complexity of O(1).

Delete Operation

Just like in inserting operation we need toupdate the pointers of the adjacent nodes to bypass the deleted node. As a result we have O(1) time complexity for deleting operation.

Note

When inserting or deleting an element in a linked list, the process involves adjusting pointers accordingly. In contrast, when working with arrays, to achieve the same operation, a segment of the array must be rewritten.