Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Ordered Lists and Sorted Lists

The most simple, yet one of the most versatile containers is the list . In this chapter we consider lists as abstract data types. A list is a series of items. In general, we can insert and remove items from a list and we can visit all the items in a list in the order in which they appear.

In this chapter we consider two kinds of lists--ordered lists and sorted lists. In an ordered list the order of the items is significant. Consider a list of the titles of the chapters in this book. The order of the items in the list corresponds to the order in which they appear in the book. However, since the chapter titles are not sorted alphabetically, we cannot consider the list to be sorted. Since it is possible to change the order of the chapters in book, we must be able to do the same with the items of the list. As a result, we may insert an item into an ordered list at any position.

On the other hand, a sorted list is one in which the order of the items is defined by some collating sequence. For example, the index of this book is a sorted list. The items in the index are sorted alphabetically. When an item is inserted into a sorted list, it must be inserted at the correct position.

The list abstractions can be implemented in many ways. In this chapter we examine implementations based on the array and the linked list foundational data structures presented in Chapter .