A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Linked Lists in Action

One case where linked lists shine is when we examine a single list and delete many elements from it. Let’s say, for example, we’re building an application that combs through existing lists of email addresses and removes any email address that has an invalid format.

No matter whether the list is an array or a linked list, we need to comb through the entire list one element at a time to inspect each email address. This, naturally, takes N steps. However, let’s examine what happens when we actually delete each email address.

With an array, each time we delete an email address, we need another O(N) steps to shift the remaining data to the left to close the gap. All this shifting will happen before we can even inspect the next ...