A list, also known as collection or container, is a logical grouping of data items into a single unit. List data structures specify the layout of items in memory, the relationships between them, and the available operations. Operations include (but are not limited to) searching, sorting, insertion, deletion, and enumeration. There are several popular list data structures which each have distinct strengths, weaknesses, and capabilities. The purpose of this section is to provide readers with the tools they need to master list data structures.
For many algorithms, having a general awareness is sufficient. One can always refer back to documentation for a quick review. However, this isn’t true of list data structures. It’s well worth the effort to build a visceral connection with this section’s material. List manipulation is the single most common programming task. The greatest majority of algorithms rely on one or more lists and the choice of list data structure has profound implications. Sometimes choosing the right one is easy because a particular utility is required. However, be forewarned that it’s possible to choose one that satisfies functional requirements while inadvertently incurring an unnecessary prodigious negative performance impact. Modern programming languages contribute to this phenomenon.
All mainstream languages have builtin list abstractions. For instance, LISP,
which stands for LISt Processor, is designed entirely around the concept. C#
has the IEnumerable interface, Java has the Iterable interface, Python has
list. There are many more examples but there is no need to belabor the point.
The utility these abstractions provide is significant; however, the underlying
data structure isn’t always entirely obvious to the untrained eye. List data
structure comprehension enables programmers to properly capitalize on the
abstractions.
Without further ado, it’s time to set yourself to the task of mastering list data structures.
Source Code
Relevant Directories: