Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have presented the Time Complexity analysis of different operations in Linked List. It clears several misconceptions such that Time Complexity to access i-th element takes O(1) time but in reality, it takes O(√N * N) time. We have presented space complexity of Linked List operations as well.
Table of contents:
- Introduction to Singly Linked List
- Time Complexity of Linked List
- Space Complexity of Linked List
Let us get started with Time Complexity Analysis of Linked List.
Introduction to Singly Linked List
Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form, yet it is effective for several problems such as Big Integer calculations.
A singly linked list is made up of nodes where each node has two parts:
- The first part contains the actual data of the node
- The second part contains a link that points to the next node of the list that is the address of the next node.
The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.
The main difference from an array is:
- Elements are not stored in contiguous memory locations.
- Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.
In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.
To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.
Time Complexity of Linked List
From this article on time complexity of memory address, we known that to access a specific element, the time complexity is O(√N) where N is block of continuous elements being read.
As Linked List elements are not contiguous, each element access incur a Time Complexity of O(√N).
This is an overhead compared to Array where the overhead to encountered only once.
The advantage of Linked List comes when we have to insert an element at current location or delete current element. This is done in constant time as we need to change the address stored to previous nodes only.
In case of array, for similar operation, we need to shift all other elements which makes the time complexity linear.
Operations at the end of Linked List like inserting element at the end takes linear time because we have to traverse to the end. If we are already at the end, then we can insert the element in constant time.
The summary of Time Complexity of operations in a Linked List is:
| Singly Linked List operation | Real Time Complexity | Assumed Time Complexity |
|---|---|---|
| Access i-th element | O(√N * N) | O(N) |
| Traverse all elements | O(√N * N) | O(N) |
| Insert element E at current point | O(1) | O(1) |
| Delete current element | O(1) | O(1) |
| Insert element E at front | O(1) | O(1) |
| Insert element E at end | O(√N * N) | O(N) |
There are other variants of Linked List like:
- Doubly Linked List (each node stores the address of previous node as well)
- Circular Linked List (last node points to the first node)
Time Complexity of different operations in different variants vary.
For example, Time Complexity to insert element at front is O(1) in Singly Linked List but it is O(√N) for Doubly Linked List as we have to access the next element to set its previous address to the new element.
Space Complexity of Linked List
The Space Complexity of the above Linked List operations is O(1).
This is because we do not need extra space beyond a fixed number of variables.
For some operations, you may need extra space of the order of O(N). For example, sorting a Linked List using a sorting algorithm that is not in-place.
With this article at OpenGenus, you have the perfect idea of the Time and Space Complexity of Linked List.
