DATA STRUCTURES

DATA STRUCTURES

Abstraction and Design
Using
Java

Our goal in writing this book was to combine a strong emphasis on problem solving and
software design with the study of data structures. To this end, we discuss applications of each
data structure to motivate its study. After providing the specification (interface) and the
implementation (a Java class), we then cover case studies that use the data structure to solve
a significant problem. Examples include maintaining an ordered list, evaluating arithmetic
expressions using a stack, finding the shortest path through a maze, and Huffman coding
using a binary tree and a priority queue. In the implementation of each data structure and in
the solutions of the case studies, we reinforce the message “Think, then code” by performing
a thorough analysis of the problem and then carefully designing a solution (using pseudo‐
code and UML class diagrams) before the implementation. We also provide a performance
analysis when appropriate. Readers gain an understanding of why different data structures
are needed, the applications they are suited for, and the advantages and disadvantages of their
possible implementations.

ELLIOT B. KOFFMAN
&PAUL A. T. WOLFGANG