Home Page

Chapter 5: Vectors, Lists, and Sequences

Cell

The concept of a sequence, where each object comes before or after another, is fundamental. We see it in a line-by-line listing of the code of a computer program, where the order of instructions determines the computation that the program represents. We also see it in the sequence of network packets that together comprise an e-mail message, which, if it is to make sense, requires that the packets be assembled in the same order in which they are sent. Sequences are interesting, then, for they represent the important relationships of `next' and `previous' between related objects. In addition, sequences are widely used to realize and implement other data structures; hence, they are foundational building blocks for data structure design.

In this chapter, we present the vector, list, and sequence ADTs, each of which represents a collection of linearly arranged elements and provides methods for accessing, inserting, and removing arbitrary elements. The different types of sequences are distinguished from one another by the specific ways in which these operations are defined. Stacks, queues, and deques, studied in Chapter 4, can be viewed as restricted types of sequences that access only the first and/or last elements. An important property of a sequence is that, just as with stacks, queues, and deques, the order of the elements in a sequence is determined by the operations in the abstract data type specification, and not by the values of the elements.

The vector ADT is an extension of the concrete array data structure. It provides accessor methods that can index into the middle of a sequence and it also provides update methods for adding and removing elements by their indices. To avoid confusion with the way items are accessed in the concrete array data structure, we typically use the term rank to refer to the index of an element in a vector.

The list ADT, on the other hand, is an object-oriented extension of the concrete linked list data structure. It provides accessor and update methods based on an object-oriented encapsulation of the node objects used by linked lists. We call these abstract node objects positions, for they provide an object-oriented way of referring to `places' where elements are stored, independent of the specific implementation of the list.

Finally, the full sequence ADT is a unification of the vector and list concepts. Therefore, it is useful in contexts where we desire a generic data structure that can be implemented naturally using either an array or a linked list. We show, however, that this generality comes at a cost, for we give two basic ways of implementing a sequence, with an array and with a doubly linked list, and we point out performance trade-offs between these two implementations.

We illustrate the use of the sequence ADT through the implementation of a well-known (though inefficient) sorting algorithm known as bubble-sort. We also discuss the iterator (or enumeration) design pattern and mention its realization by means of a vector or list.