Lists occur as naturally in programming as they do in real life. We manipulate guest lists, grocery lists, class lists, and things-to-do lists. The list of lists is endless. Three properties characterize lists: The items are homogeneous, the items are linear, and lists have varying lengths. By linear, we mean that each item except the first has a unique component that comes before it, and  each item except the last has a unique component that comes after it. For example, if there are at least three items in a list, the second item comes after the first and before the third.

Whereas stacks and queues have all the semantics in the deletion operation, lists usually provide operations to insert an item (Insert), delete an item (Delete), check whether an item is there (IsThere), and report the number of items in a list (GetLength). In addition, they have some mechanism for allowing the user to view each item in sequence (Reset, GetNext, MoreItems). Because items can be deleted and retrieved, the items in the list must be able to be compared.

Do not mistake a list for an array. An array is a structure that’s part of a programming language; a list is an abstract structure. However, a list may be implemented using an array, as shown in FIGURE 8.1.

A list may also be visualized as a linked structure. A linked structure is based on the concept of a node. A node consists of two pieces of information: the user’s data and a link or pointer that indicates where to find the next node. The end of the list is a link that contains null, which is indicated by a ‘/’. See FIGURE 8.2.

Unordered lists are those for which order is unimportant. Items are just haphazardly put into them. Sorted lists are those where there is a semantic relationship between items in the list. All items except the first come before the next item in this kind of list under some ordering relationship. All items except the last come after the one before it under the same relationship. FIGURES 8.3 and 8.4 visualize the array-based and linked versions of a sorted list.

Here is an algorithm that reads values from a file and puts them into a list. The list is then printed.

We use Reset, MoreItems, and GetNext to iterate through the list, returning each item in sequence. If the list is unsorted, the items will be printed in the order in which they are inserted. If the list is sorted, the items will be printed in sorted order. This algorithm works regardless of the implementation of the list.