CHAPTER 14 Access Types and Dynamic Data Structures

14.1 Data Structures: Access Types and the NEW Operator
14.2 Data Structures: Linked Lists and Their Operations
14.3 Data Structures: Linked Lists with Head and Tail Pointers
14.4 Problem Solving: Ordered Insertions in Linked Lists
14.5 System Structures: A Generic Version of the Linked-List Package
14.6 Problem Solving: Stacks and Queues
14.7 Tricks of the Trade: Debugging Programs with Linked Lists
Chapter Review

Dynamic data structures are data structures that expand and contract as a program executes. A dynamic data structure is a collection of elements--called nodes--that are generally implemented as records. Whereas an array always contains storage for a fixed number of elements, in a dynamic data structure the programmer can increase or reduce the storage allocated, as elements are added to or deleted from the structure.

Dynamic data structures are extremely flexible. It is relatively easy to add new information by creating a new node and inserting it between two existing nodes. It is also relatively easy to delete a node. In this chapter we introduce dynamic data structures and a new kind of Ada type called an access type. Access types--often called pointer types--are an essential part of using dynamic data structures.

Also introduced in this chapter are the stack and queue data structure, implemented using linked lists.