Previous Section
 < Free Open Study > 
Next Section


3.1 Lists

In computer programs, lists are very useful abstract data types. They are members of a general category of abstract data types called containers, whose purpose is to hold other objects. In some languages, the list is a built-in structure. In Lisp, for example, the list is the main data structure provided in the language. In C++, while lists are provided in the Standard Template Library, the techniques for building lists and other abstract data types are so important that we show you how to design and write your own.

Linear relationship Each element except the first has a unique predecessor, and each element except the last has a unique successor

Length The number of items in a list; the length can vary over time

Unsorted list A list in which data items are placed in no particular order; the only relationships between data elements are the list predecessor and successor relationships

Sorted list A list that is sorted by the value in the key; a semantic relationship exists among the keys of the items in the list

Key A member of a record (struct or class) whose value is used to determine the logical and/or physical order of the items in a list

From a theoretical point of view, a list is a homogeneous collection of elements, with a linear relationship between elements. Linear means that, at the logical level, each element in the list except the first one has a unique predecessor, and each element except the last one has a unique successor. (At the implementation level, a relationship also exists between the elements, but the physical relationship may not be the same as the logical one.) The number of items in the list, which we call the length of the list, is a property of a list. That is, every list has a length.

Lists can be unsorted-their elements may be placed into the list in no particular order-or they can be sorted in a variety of ways. For instance, a list of numbers can be sorted by value, a list of strings can be sorted alphabetically, and a list of grades can be sorted numerically. When the elements in a sorted list are of composite types, their logical (and often physical) order is determined by one of the members of the structure, called the key member. For example, a list of students on the honor roll can be sorted alphabetically by name or numerically by student identification number. In the first case, the name is the key; in the second case, the identification number is the key. Such sorted lists are also called key-sorted lists.

If a list cannot contain items with duplicate keys, it is said to have unique keys. This chapter deals with both unsorted lists and lists of elements with unique keys, sorted from smallest to largest key value.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)