Java Structures: Data Structures for the Principled Programmer
Free

Java Structures: Data Structures for the Principled Programmer

By Duane A. Bailey
Free
Book Description
Table of Contents
  • Java Structures
  • Copyright (c) 2005-2007 Duane A. Bailey
  • Table of 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.3 Object-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.3 Example: 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
    • 3.10 Laboratory: The Silver Dollar Game
  • 4 Generics
    • 4.1 Motivation (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.2 Examples
      • 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 Ordering Objects Using Comparators
    • 6.9 Vector-Based Sorting
    • 6.10 Conclusions
    • 6.11 Laboratory: Sorting with Comparators
  • 7 A Design Method
    • 7.1 The Interface-Based Approach
      • 7.1.1 Design of the Interface
      • 7.1.2 Development of an Abstract Implementation
      • 7.1.3 Implementation
    • 7.2 Example: Development of Generators
    • 7.3 Example: Playing Cards
    • 7.4 Conclusions
  • 8 Iterators
    • 8.1 Java's Enumeration Interface
    • 8.2 The Iterator Interface
    • 8.3 Example: Vector Iterators
    • 8.4 Example: Rethinking Generators
    • 8.5 Example: Filtering Iterators
    • 8.6 Conclusions
    • 8.7 Laboratory: The Two-Towers Problem
  • 9 Lists
    • 9.1 Example: A Unique Program
    • 9.2 Example: Free Lists
    • 9.3 Partial Implementation: Abstract Lists
    • 9.4 Implementation: Singly Linked Lists
    • 9.5 Implementation: Doubly Linked Lists
    • 9.6 Implementation: Circularly Linked Lists
    • 9.7 Implementation: Vectors
    • 9.8 List Iterators
    • 9.9 Conclusions
    • 9.10 Laboratory: Lists with Dummy Nodes
  • 10 Linear Structures
    • 10.1 Stacks
      • 10.1.1 Example: Simulating Recursion
      • 10.1.2 Vector-Based Stacks
      • 10.1.3 List-Based Stacks
      • 10.1.4 Comparisons
    • 10.2 Queues
      • 10.2.1 Example: Solving a Coin Puzzle
      • 10.2.2 List-Based Queues
      • 10.2.3 Vector-Based Queues
      • 10.2.4 Array-Based Queues
    • 10.3 Example: Solving Mazes
    • 10.4 Conclusions
    • 10.5 Laboratory: A Stack-Based Language
    • 10.6 Laboratory: The Web Crawler
  • 11 Ordered Structures
    • 11.1 Comparable Objects Revisited
      • 11.1.1 Example: Comparable Ratios
      • 11.1.2 Example: Comparable Associations
    • 11.2 Keeping Structures Ordered
      • 11.2.1 The OrderedStructure Interface
      • 11.2.2 The Ordered Vector and Binary Search
      • 11.2.3 Example: Sorting Revisited
      • 11.2.4 A Comparator-based Approach
      • 11.2.5 The Ordered List
      • 11.2.6 Example: The Modified Parking Lot
    • 11.3 Conclusions
    • 11.4 Laboratory: Computing the ``Best Of''
  • 12 Binary Trees
    • 12.1 Terminology
    • 12.2 Example: Pedigree Charts
    • 12.3 Example: Expression Trees
    • 12.4 Implementation
      • 12.4.1 The BinaryTree Implementation
    • 12.5 Example: An Expert System
    • 12.6 Traversals of Binary Trees
      • 12.6.1 Preorder Traversal
      • 12.6.2 In-order Traversal
      • 12.6.3 Postorder Traversal
      • 12.6.4 Level-order Traversal
      • 12.6.5 Recursion in Iterators
    • 12.7 Property-Based Methods
    • 12.8 Example: Huffman Compression
    • 12.9 Example Implementation: Ahnentafel
    • 12.10 Conclusions
    • 12.11 Laboratory: Playing Gardner's Hex-a-Pawn
  • 13 Priority Queues
    • 13.1 The Interface
    • 13.2 Example: Improving the Huffman Code
    • 13.3 A Vector-Based Implementation
    • 13.4 A Heap Implementation
      • 13.4.1 Vector-Based Heaps
      • 13.4.2 Example: Heapsort
      • 13.4.3 Skew Heaps
    • 13.5 Example: Circuit Simulation
    • 13.6 Conclusions
    • 13.7 Laboratory: Simulating Business
  • 14 Search Trees
    • 14.1 Binary Search Trees
    • 14.2 Example: Tree Sort
    • 14.3 Example: Associative Structures
    • 14.4 Implementation
    • 14.5 Splay Trees
    • 14.6 Splay Tree Implementation
    • 14.7 An Alternative: Red-Black Trees
    • 14.8 Conclusions
    • 14.9 Laboratory: Improving the BinarySearchTree
  • 15 Maps
    • 15.1 Example Revisited: The Symbol Table
    • 15.2 The Interface
    • 15.3 Simple Implementation: MapList
    • 15.4 Constant Time Maps: Hash Tables
      • 15.4.1 Open Addressing
      • 15.4.2 External Chaining
      • 15.4.3 Generation of Hash Codes
      • 15.4.4 Hash Codes for Collection Classes
      • 15.4.5 Performance Analysis
    • 15.5 Ordered Maps and Tables
    • 15.6 Example: Document Indexing
    • 15.7 Conclusions
    • 15.8 Laboratory: The Soundex Name Lookup System
  • 16 Graphs
    • 16.1 Terminology
    • 16.2 The Graph Interface
    • 16.3 Implementations
      • 16.3.1 Abstract Classes Reemphasized
      • 16.3.2 Adjacency Matrices
      • 16.3.3 Adjacency Lists
    • 16.4 Examples: Common Graph Algorithms
      • 16.4.1 Reachability
      • 16.4.2 Topological Sorting
      • 16.4.3 Transitive Closure
      • 16.4.4 All Pairs Minimum Distance
      • 16.4.5 Greedy Algorithms
    • 16.5 Conclusions
    • 16.6 Laboratory: Converting Between Units
  • A Answers
    • A.1 Solutions to Self Check Problems
    • A.2 Solutions to Odd-Numbered Problems
  • B Beginning with Java
    • B.1 A First Program
    • B.2 Declarations
      • B.2.1 Primitive Types
      • B.2.2 Reference Types
    • B.3 Important Classes
      • B.3.1 The structure.ReadStream Class
      • B.3.2 The java.util.Scanner Class
      • B.3.3 The PrintStream Class
      • B.3.4 Strings
    • B.4 Control Constructs
      • B.4.1 Conditional Statements
      • B.4.2 Loops
    • B.5 Methods
    • B.6 Inheritance and Subtyping
      • B.6.1 Inheritance
      • B.6.2 Subtyping
      • B.6.3 Interfaces and Abstract Classes
    • B.7 Use of the Assert Command
    • B.8 Use of the Keyword Protected
  • C Collections
    • C.1 Collection Class Features
    • C.2 Parallel Features
    • C.3 Conversion
  • D Documentation
    • D.1 Structure Package Hierarchy
    • D.2 Principles
  • Index
  • Colophon
The book hasn't received reviews yet.
You May Also Like
The Java EE 7 Tutorial
Free
The Java EE 7 Tutorial
By Oracle Corporation
JavaKid811
Free
JavaKid811
By Unknown
OSGi in Practice
Free
OSGi in Practice
By Neil Bartlett
The Java EE 6 Tutorial
Free
The Java EE 6 Tutorial
By Oracle Corporation
NIO_Paper
Free
NIO_Paper
By Unknown
Open Data Structures
Free
Open Data Structures
By Pat Morin
Java 3D Programming
Free
Java 3D Programming
By Daniel Selman
Also Available On
Categories
Curated Lists