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
    No review for this book yet, be the first to review.
      No comment for this book yet, be the first to comment
      You May Also Like
      The Java EE 6 Tutorial
      Free
      The Java EE 6 Tutorial
      By Oracle Corporation
      NIO_Paper
      Free
      NIO_Paper
      By Unknown
      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
      Open Data Structures
      Free
      Open Data Structures
      By Pat Morin
      Java 3D Programming
      Free
      Java 3D Programming
      By Daniel Selman
      Also Available On
      App store smallGoogle play small
      Categories
      Curated Lists
      • Pattern Recognition and Machine Learning (Information Science and Statistics)
        by Christopher M. Bishop
        Data mining
        by I. H. Witten
        The Elements of Statistical Learning: Data Mining, Inference, and Prediction
        by Various
        See more...
      • CK-12 Chemistry
        by Various
        Concept Development Studies in Chemistry
        by John Hutchinson
        An Introduction to Chemistry - Atoms First
        by Mark Bishop
        See more...
      • Microsoft Word - How to Use Advanced Algebra II.doc
        by Jonathan Emmons
        Advanced Algebra II: Activities and Homework
        by Kenny Felder
        de2de
        by
        See more...
      • The Sun Who Lost His Way
        by
        Tania is a Detective
        by Kanika G
        Firenze_s-Light
        by
        See more...
      • Java 3D Programming
        by Daniel Selman
        The Java EE 6 Tutorial
        by Oracle Corporation
        JavaKid811
        by
        See more...