Chapter 3. Lists
Lists are one of the most common organizing tools people use in their day-to-day lives. We have to-do lists, grocery lists, top-ten lists, bottom-ten lists, and many other types. Our computer programs can also use lists, particularly if we only have a few items to store in list form. Lists are especially useful if we don’t have to perform searches on the items in the list or put them into some type of sorted order. When we need to perform long searches or complex sorts, lists become less useful, especially with more complex data structures.
This chapter presents the creation of a simple list class. We start with the definition of a list abstract data type (ADT) and then demonstrate how to implement the ADT. We wrap up the chapter with some problems that are best solved with lists.
A List ADT
In order to design an ADT for a list, we have to provide a definition of the list, including its properties, as well as the operations performed on it and by it.
A list with no elements is an empty list. The number of elements stored in a list is called the length of the list. Internally, the number of elements in a list is kept in a
listSize variable. ...