Java structures

Java Structures

Data Structures in Java for the Principled Programmer

The

√

7 Edition

(Software release 33)

Duane A. Bailey

Williams College September 2007

This

√

7 text copyrighted 2005-2007 by

All rights are reserved by The Author. No part of this draft publiciation may be reproduced or distributed in any form without prior, written consent of the author.Contents
Preface to First Edition Preface to the Second Edition Preface to the “Root 7” Edition 0 Introduction 0.1 Read Me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2 He Can’t Say That, Can He? . . . . . . . . . . . . . . . . . . . . . 1 The Object-Oriented Method 1.1 Data Abstraction and Encapsulation . . . . . 1.2 The Object Model . . . . . . . . . . . . . . . 1.3Object-Oriented Terminology . . . . . . . . 1.4 A Special-Purpose Class: A Bank Account . . 1.5 A General-Purpose Class: An Association . . 1.6 Sketching an Example: A Word List . . . . . 1.7 Sketching an Example: A Rectangle Class . 1.8 Interfaces . . . . . . . . . . . . . . . . . . . 1.9 Who Is the User? . . . . . . . . . . . . . . . 1.10 Conclusions . . . . . . . . . . . . . . . . . . 1.11 Laboratory:The Day of the Week Calculator 2 Comments, Conditions, and Assertions 2.1 Pre- and Postconditions . . . . . . . . . 2.2 Assertions . . . . . . . . . . . . . . . . . 2.3 Craftsmanship . . . . . . . . . . . . . . . 2.4 Conclusions . . . . . . . . . . . . . . . . 2.5 Laboratory: Using Javadoc Commenting 3 Vectors 3.1 The Interface . . . . . . . . . . . 3.2 Example: The Word List Revisited 3.3Example: Word Frequency . . . . 3.4 The Implementation . . . . . . . 3.5 Extensibility: A Feature . . . . . . 3.6 Example: L-Systems . . . . . . . 3.7 Example: Vector-Based Sets . . . 3.8 Example: The Matrix Class . . . . 3.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi xiii xv 1 1 2 5 6 7 8 11 14 18 20 22 24 25 29 33 34 34 36 37 39 43 45 47 48 50 53 56 57 60 64

iv

Contents 3.10 Laboratory: The Silver Dollar Game . . . . . . . . . . . . . . . . . 67 4 Generics 4.1Motivation (in case we need some) . . . 4.1.1 Possible Solution: Specialization 4.2 Implementing Generic Container Classes 4.2.1 Generic Associations . . . . . . 4.2.2 Parameterizing the Vector Class 4.2.3 Restricting Parameters . . . . . . 4.3 Conclusions . . . . . . . . . . . . . . . . 5 Design Fundamentals 5.1 Asymptotic Analysis Tools . . . . . . . . 5.1.1 Time and Space Complexity . . . 5.1.2Examples . . . . . . . . . . . . . 5.1.3 The Trading of Time and Space . 5.1.4 Back-of-the-Envelope Estimations 5.2 Self-Reference . . . . . . . . . . . . . . . 5.2.1 Recursion . . . . . . . . . . . . . 5.2.2 Mathematical Induction . . . . . 5.3 Properties of Design . . . . . . . . . . . 5.3.1 Symmetry . . . . . . . . . . . . . 5.3.2 Friction . . . . . . . . . . . . . . 5.4 Conclusions . . . . . . . . .. . . . . . . 5.5 Laboratory: How Fast Is Java? . . . . . . 6 Sorting 6.1 Approaching the Problem . . . . . . . 6.2 Selection Sort . . . . . . . . . . . . . . 6.3 Insertion Sort . . . . . . . . . . . . . . 6.4 Mergesort . . . . . . . . . . . . . . . . 6.5 Quicksort . . . . . . . . . . . . . . . . 6.6 Radix Sort . . . . . . . . . . . . . . . . 6.7 Sorting Objects . . . . . . . . . . . . . 6.8...