C++ How to Program, 10/e

19.1 Introduction

We’ve studied fixed-size data structures—such as one- and two-dimensional template-based arrays (Chapter 7) and built-in arrays (Chapter 8)—and various C++ Standard Library dynamic data structures (arrays and vectors in Chapter 7 and other template-based containers in Chapter 15) that can grow and shrink during execution.

In this chapter, we demonstrate how you can create your own custom templatized dynamic data structures. We discuss several popular and important data structures and implement programs that create and manipulate them:

• Linked lists are collections of data items logically “lined up in a row”—insertions and removals are made anywhere in a linked list.

• Stacks (which we introduced in Section 6.11 and discussed ...