Handbook of Data Structures and Applications, 2nd Edition

2

Basic Structures*

Dinesh P. Mehta

Colorado School of Mines

2.1Introduction

2.2Arrays

Operations on an Array•Sorted Arrays•Array Doubling•Multiple Lists in a Single Array•Heterogeneous Arrays•Multidimensional Arrays•Sparse Matrices

2.3Linked Lists

Chains•Circular Lists•Doubly Linked Circular Lists•Generalized Lists

2.4Stacks and Queues

Stack Implementation•Queue Implementation

Acknowledgments

References

2.1Introduction

In this chapter, we review several basic structures that are usually taught in a first class on data structures. There are several text books that cover this material, some of which are listed here [1–4]. However, we believe that it is valuable to review this material for the following reasons:

1.In practice, these structures ...