### List

A list uses pointers to link each element to its predecessor and successor. This implementation does not require contiguous memory for storing an array, which means that elements do not have to be shifted to make room for new elements or to close up gaps created by deleted elements.

Because storage is dynamically allocated and freed, this implementation variant is a good choice in applications that add or delete many elements, particularly where you cannot predict the amount of storage required. The figure below shows a list implementation variant.

List Implementation Variant

Introduction to the Collection Classes
Collection Class Hierarchy
Overall Implementation Structure
Flat Collections
Trees
AVL Tree
B* Tree
Diluted Table
Hash Table
Table

Class Template Naming Conventions
Possible Implementation Paths
Choosing One of the Provided Implementation Variants
Replacing the Default Implementation
Taking Advantage of the Abstract Class Hierarchy
Instantiating the Collection Classes