Linked lists are one of the fundamental data structures used in computer science and programming. They consist of nodes that are linked together by pointer references. Understanding the time complexity of basic operations on linked lists like searching, insertion, and deletion is key to deciding when to use them versus other data structures like arrays. This article will analyze the time complexities of these core operations on singly and doubly linked lists.
Overview of Linked Lists
A linked list organizes data in the form of nodes as shown in the diagram below:
Each node contains the data and a reference or pointer to the next node. This forms the links between nodes, allowing you to traverse the full list by following the next references.
The above shows a singly linked list where nodes only reference the next node. There are also doubly linked lists where nodes have both a next and previous reference:
This allows you to traverse the list in both forward and backward directions.
There are also circular linked lists where the last node points back to the first, creating a continuous loop.
Time Complexity Basics
Before analyzing the specific time complexities, let‘s define what time complexity means:
- Time complexity – The number of operations/steps required for an algorithm/operation as the input size grows. Typically shown using Big O notation.
- Big O notation – Represents the upper bound time complexity of an algorithm, showing how the number of steps grows relative to input size n.
For example:
- O(1) – Constant time, the operation takes roughly the same number of steps for any input size
- O(log n) – Logarithmic time, the operation steps grow logarithmically relative to input size
- O(n) – Linear time, the operation steps grow directly proportionally to input size
With this background, let‘s look at how the core linked list operations scale.
Searching a Linked List
Searching for a node by its value requires traversing the linked list node-by-node until you find a match or reach the end.
For both singly and doubly linked lists, this search process visits each node at most once, requiring n steps for a list of n nodes:
Therefore, searching has O(n) linear time complexity since in the worst case when the value is not found, every node in the list must be visited once. The number of steps grows linearly relative to the number of nodes n.
This contrasts with data structures like arrays and binary search trees which can use random access or ordering to achieve faster O(1) or O(log n) search time.
Optimized Search Variants
There are some advanced variants of linked lists optimized specifically for faster search:
Skip List
A skip list augments a regular linked list by adding additional layers of pointers to shortcut over nodes, as shown:
This allows search time to be reduced to O(log n) with high probability by leveraging these express lanes. Inserts and deletes are more complex however.
XOR Linked List
XOR linked lists save memory by storing the next pointer as the XOR value between adjacent node addresses rather than directly. This allows getting the next node in O(1) time but hurts search performance.
Understanding these tradeoffs can help pick the right linked list for your use case.
Insertion Time Complexity
Insertion adds a new node into the linked list. For singly linked lists, this involves:
- Search to find insertion point – O(n)
- Update next pointer of previous node – O(1)
- Update next pointer of new node – O(1)
Therefore insertion takes O(n) time since searching the position takes linear time complexity.
For doubly linked lists, there is the additional step of updating the previous pointer of the next node requiring O(1) time.
So insertion takes O(n) time for both singly and doubly linked lists due to search time dominating. Each insertion requires traversing the list to the insertion point.
Comparison to Array Insertion
Unlike arrays, inserting anywhere in a linked list just requires updating a couple pointers rather than shifting elements over. Linked lists have consistent O(n) insertion time regardless of position, compared to O(1) insertion for arrays appending to the end. So linked lists have advantage when inserts spread randomly across huge lists.
Deletion Time Complexity
Deletion removes an existing node from the linked list. For singly linked lists, this involves:
- Search to find node to delete – O(n)
- Update next pointer of previous node – O(1)
As with insertion, deletion takes O(n) time due to search time.
For doubly linked lists, there is the additional O(1) step of updating the next node‘s previous pointer.
However, the overall time complexity remains O(n) due to search time dominating.
Comparison to Array Deletion
Like insertion, deleting anywhere from a linked list just requires rewiring a couple pointers versus shifting down array elements. So linked lists have better asymptotics for handling tons of deletes spread randomly across the data structure.
Summary of Core Operations Time Complexity
Based on the above analysis:
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Search | O(n) | O(n) |
| Insertion | O(n) | O(n) |
| Deletion | O(n) | O(n) |
For all the core operations, doubly linked lists do not provide better asymptotic time complexity compared to singly linked lists. The linear search time dominates the overall complexities.
However, doubly linked lists provide more flexibility to iterate in both forward or backward directions. So they may have advantages for real-world performance and algorithms involving bidirectional traversal.
When Linked Lists Have Advantages Over Arrays
The key benefit of linked lists is efficient O(1) insertion and deletion anywhere in the list without having to shift other elements around in memory.
In contrast, inserting into and deleting from arrays requires shifting remaining elements, taking O(n) time in the worst case.
Therefore linked lists have an asymptotic edge for handling lots of inserts and deletes spread throughout huge lists. The downside is the O(n) search time versus O(1) time to access array elements directly by index.
Array vs linked list operation time complexity (source: geeksforgeeks.org)
So linked lists have advantages when:
- Frequently adding and removing elements from arbitrary positions
- Unknown overall size of data in advance
- Need dynamic allocation over fixed-sized array
Real-World Use Cases
Some example use cases taking advantage of linked lists:
- Hash table chaining – Linked lists handle collisions gracefully when hash table load factors get high
- Graphs adjacency lists – Can efficiently represent dynamic graph connections
- Undo/redo functionality – Add to stack of previous editor states
- Process scheduling queues – Easy insertion and removal from queues
There are many other applications where these properties provide optimization.
Optimized Variants
There are more advanced linked list variants that improve certain operations:
Skip List
Skip lists use additional pointer layers to enable O(log n) search time instead of linear traversal:
The tradeoff is higher insertion and deletion complexity to maintain these pointers.
XOR Linked Lists
XOR linked lists save memory by storing the next pointer as the XOR value between adjacent node addresses rather than directly. This allows getting the next node in O(1) time but hurts search performance having to XOR backpointer values.
Self Organizing Lists
These linked lists automatically reorder elements to improve access patterns based on frequency and recent use, trading off memory overhead in the process.
Understanding these variants and how they optimize trade-offs around metrics like search, storage, and traversal can help decide which fits your application‘s specific performance needs.
Comparison of Languages and Frameworks
Most programming frameworks and libraries provide standard linked list implementations:
- C++ – std::list doubles linked list
- Java – java.util.LinkedList
- Python – collections.deque
- JS – doubly/singly-linked-list libraries
Additionally, many provide those optimized variants discussed above out of the box like skip lists.
So while important to understand the intricacies of implementing and tuning linked lists, many languages provide great building blocks.
Linked Lists vs Other Self Referential Structures
Linked lists have relationship with other data structures that use self-referential node linking:
Trees
Trees arrange nodes into hierarchical tree structures with each node tracking child nodes. Linked lists form a single chain of nodes. Trees enable faster O(log n) searching with ordering but slower sequential access.
Graphs
Graphs create arbitrary node connections allowing more complex relationship modeling. Linked lists establish one ordered chain of nodes. Graphs enable more modeling flexibility but require more complex access algorithms.
So linked lists fill an important niche balancing simplicity and use cases around linear node sequences and fast inserts/deletes while other structures optimize different properties.
Conclusion
The core operations of search, insertion, and deletion on linked lists have linear O(n) time complexity dominated by the list traversal between nodes.
Doubly linked lists provide more flexible iteration order but do not improve the asymptotic complexities themselves over singly linked lists.
Linked lists can be highly efficient for handling frequent inserts and deletes compared to arrays but have slower search than random access. Choosing the right data structures in light of these trade-offs is a key skill for programmers and software architects. Understanding how different linked list variants shift these trade-offs via alternate pointer arrangements can also enable tuning implementations for different use case patterns.