Introduction

This chapter begins our three-chapter treatment of data structures. The data structures that we have studied thus far have had fixed sizes, such as one- and two-dimensional arrays. This chapter introduces dynamic data structures that 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 endits top. Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue, and deletions are made 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. These data structures have many other interesting applications as well.

We will discuss each of these major types of 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 26, we introduce generics, which allow you to declare data structures that can be automatically adapted to contain data of any type. In Chapter 27, Collections, we discuss C#'s pre-defined 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. The exercises offer a rich collection of useful applications.