A Concise Introduction to Data Structures using Java

Chapter 6

Lists

The power of stacks and queues as linear data structures lies in their limited interface: elements may only be added or removed in specific ways. Controlling insertion and deletion in this way allows designing for O(1) performance for those operations.

Lists, on the other hand, provide a very flexible interface that allows inserting and removing elements anywhere in the list. This flexibility comes at a price, though: operations will no longer necessarily be O(1).

6.1 Interface

The List ADT views its data much like an array does: elements are accessible via consecutive indices.

List Indexing

Think of references in a list as stored at indices 0 through one less than the number of elements in the list, just like an array:

This ...