Data Structures and Algorithms in C++, Second Edition

Chapter 6. List and Iterator ADTs

Contents

6.1 Vectors	228
6.1.1 The Vector Abstract Data Type	228
6.1.2 A Simple Array-Based Implementation	229
6.1.3 An Extendable Array Implementation	231
6.1.4 STL Vectors	236
6.2 Lists	238
6.2.1 Node-Based Operations and Iterators	238
6.2.2 The List Abstract Data Type	240
6.2.3 Doubly Linked List Implementation	242
6.2.4 STL Lists	247
6.2.5 STL Containers and Iterators	248
6.3 Sequences	255
6.3.1 The Sequence Abstract Data Type	255
6.3.2 Implementing a Sequence with a Doubly Linked List	255
6.3.3 Implementing a Sequence with an Array	257
6.4 Case Study: Bubble-Sort on a Sequence	259
6.4.1 The Bubble-Sort Algorithm	259
6.4.2 A Sequence-Based Analysis of Bubble-Sort	260
6.5 Exercises	262

Vectors

Suppose we have a collection S of n elements stored in a certain linear order, so that we can refer to the elements in S as first, second, third, and so on. Such a collection is generically referred to as a list or sequence. We can uniquely refer to each element e in S using an integer in the range [0,n − 1] that is equal to the number of elements of S that precede e in S. The index of an element e in S is the number of elements that are before e in S. Hence, the first element in S has index 0 and the last element has index n − 1. Also, if an element of S has index i, its previous element (if it exists) has index i − 1, and its next element (if it exists) has index i + 1. This concept of index ...