A Common-Sense Guide to Data Structures and Algorithms

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, that we’re building an application that combs through lists of email addresses and removes any email address that has an invalid format. Our algorithm inspects each and every email address one at a time, and uses a regular expression (a specific pattern for identifying certain types of data) to determine whether the email address is invalid. If it’s invalid, it removes it from the list.

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 value, which would take N steps. However, let’s examine what happens when we actually ...