Data Structures and Algorithms in Java, 6th Edition

Chapter 7

List and Iterator ADTs

Contents

7.1 The List ADT

7.2 Array Lists

7.2.1 Dynamic Arrays

7.2.2 Implementing a Dynamic Array

7.2.3 Amortized Analysis of Dynamic Arrays

7.2.4 Java's StringBuilder class

7.3 Positional Lists

7.3.1 Positions

7.3.2 The Positional List Abstract Data Type

7.3.3 Doubly Linked List Implementation

7.4 Iterators

7.4.1 The Iterable Interface and Java's For-Each Loop

7.4.2 Implementing Iterators

7.5 The Java Collections Framework

7.5.1 List Iterators in Java

7.5.2 Comparison to Our Positional List ADT

7.5.3 List-Based Algorithms in the Java Collections Framework

7.6 Sorting a Positional List

7.7 Case Study: Maintaining Access Frequencies

7.7.1 Using a Sorted List

7.7.2 Using a List with the Move-to-Front Heuristic

7.8 Exercises

7.1 The List ADT

In Chapter 6, we introduced the stack, queue, and deque abstract data types, and discussed how either an array or a linked list could be used for storage in an efficient concrete implementation of each. Each of those ADTs represents a linearly ordered sequence of elements. The deque is the most general of the three, yet even so, it only allows insertions and deletions at the front or back of a sequence.

In this chapter, we explore several abstract data types that represent a linear sequence of elements, but with more general support for adding or removing elements at arbitrary positions. However, designing a single ...