Here is the best, worst, and average-case complexity for linked list operations:
|
Operation |
Time Complexity: Worst Case |
Time Complexity: Average Case |
|
Insert at beginning or end |
O(1) |
O(1) |
|
Delete at beginning or end |
O(1) |
O(1) |
|
Search |
O(n) |
O(n) |
|
Access |
O(n) |
O(n) |
We can achieve the O(1) insert complexity at the end of the linked list by keeping a track of the last node, as we did for the first node in our examples. This will help us jump directly to the last node of the linked list without any iteration.