Section 24.1. Introduction

24.1. Introduction

This chapter begins our three-chapter data structures treatment. The data structure that we've studied thus far have had fixed sizes, such as one- and two-dimensional arrays. Here we introduce dynamic data structure that can grow and shrink at execution time. Linked lists are collections of data items "lined up in a row"users can make insertions and deletions anywhere in a linked list. Stacks are important in compilers and operating systems; insertions and deletions are made at only one endthe top of the stack. Queues represent waiting lines; insertions are only made at the back (also referred to as the tail) of a queue, and deletions are made only from the front (also referred to as the head) of a queue. Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representation of file system directories and compilation of expressions into machine language. All these data structures have many other interesting applications as well.

We will discuss each of these data structures and implement programs that create and manipulate them. We use classes, inheritance and composition to create and package these data structures for reusability and maintainability. In Chapter 25, we introduce generics, which allow you to declare data structures that can be easily adapted to contain data of any type. In Chapter 26, we discuss the FCL's predefined classes that implement various data structures.

The chapter examples are practical programs that will be useful in more advanced courses and in industrial applications. The programs focus on reference manipulation.