When to Use Linked Lists?
Insertion & Deletion
When considering time complexity, linked lists may appear underwhelming compared to arrays. They exhibit similar performance to arrays for search, insertion, and deletion operations and are notably slower regarding reading. With this in mind, one might question why anyone would ever want to use a linked list.
The key lies in the fact that the actual steps involved in inserting and deleting nodes in a linked list have a constant time complexity of O(1). This is aside from the initial work to find the actual space you'd like to insert or delete, which we previously discussed is O(N).
Let's consider an example where we are developing an application that scans a list of phone numbers to eliminate any numbers with an incorrect format.
Regardless of whether the list is implemented as an array or a linked list, we need to traverse the entire list one element at a time to inspect each phone number, which naturally takes N steps. However, there's more to consider regarding what happens when we actually perform the deletion once we've found an incorrectly formatted phone number.
In the case of an array, each time we delete a phone number, we must undertake an additional O(N) steps to shift the remaining data to the left and close the gap. This shifting operation occurs before we can proceed to inspect the next phone number. Let's assume that 1 in 5 phone numbers is incorrect. If we have a list of 2,000 phone numbers, we would have approximately 400 incorrect numbers. Our algorithm would require 2,000 steps for reading all the phone numbers. Considering the extra step to shift the remaining elements after a deletion, however, the entire deletion process could entail almost 800,000 additional steps. For each of the 400 deleted numbers, we may need to shift nearly 2,000 other elements.
On the other hand, with a linked list, as we traverse the list, each deletion can be accomplished in just one step by modifying the link of a previous node to point to the appropriate following node and moving on. In the case of our example with 2,000 phone numbers, our algorithm would only require 2,400 steps — 2,000 steps for reading all the phone numbers and 400 steps for the deletion process.
Therefore, it becomes clear that linked lists excel as a data structure for efficiently traversing an entire list while making multiple insertions or deletions. This advantage lies in the fact that we never need to concern ourselves with shifting other elements during these operations.