|
Data Structures in Java: From Abstract Data Types to the Java Collections Framework
This book focus is on the design of data structures and takes the reader through the design phase of developing the ADTs in abstract terms, then developing the methods, discussing the alternatives and potential pitfalls. Each collection type is presented as an Abstract Data Type(ADT) and then tested before implementation. There is extensive use of
UML and all collections developed are designed to work within the Java Collections Framework(JCF). Readers who want to become independent problem-solvers and master abstraction, software testing and object-oriented concepts.
CONTENTS:
Chapter 0 Introduction to What We Will be Studying 0.1 Abstraction
0.2 Algorithms
0.3 Object-Oriented Programming
0.4 The Software Life Cycle
0.5 Software Testing
0.6 The Unified Modeling Language: Using Pictures to Express Design
0.7 Software Design Patterns: Applying Proven Solutions to New Problems
0.8 Collections and the Java Collections Framework
Exercises
Chapter 1 Object-Oriented Programming and Java 1.1 Abstraction and Abstract Data Types
1.2 The Object-Oriented Approach
1.3 Code Reuse Through Composition and Inheritance
Investigate: Inheritance, Packages, and Access Modifiers
1.4 Polymorphism and Generic Programming
1.5 Case Study: a Shapes Hierarchy
1.6 Java Generic Types
Exercises
Chapter 2 Error Handling, Software Testing, and Program Efficiency
2.1 Error Handling with Exceptions
2.2 Software Testing
2.3 Analysis and Measurement of Algorithms
Exercises
Chapter 3 Fundamental Data Structures: The Array and Linked Data Structures
3.1 The Array Data Structure
3.2 Array Operations
3.3 The Linked Data Structure
3.4 A Generic Singly Linked Data Structure
3.5 The Doubly Linked Data Structure
3.6 The Circular Linked List
3.7 Selecting a Data Structure
3.8 Focus on Problem Solving: The ACME Courier Company
Exercises
Chapter 4 A Basic Collection Class
4.1 The Collection Interface in the Java Collections Framework
4.2 Iterators and the Iterator Design Pattern
4.3 Collection Basics: Objects, Casting, Operations, and Iterators
4.4 Developing a Test Plan for BasicCollection
4.5 Testing with JUnit
4.6 The java.util.AbstractCollection Abstract Class
4.7 More Java Generics: Inheritance, Wildcards, and Generic Methods
4.8 Implementation of the BasicCollection Class
4.9 Analysis of the Implementation
Investigate: equals(), hashcode(), and toArray()
4.10 Cloning
Exercises
Chapter 5 The List Abstract Data Type
5.1 List Description
5.2 The List ADT
5.3 The List Interface in the Java Collections Framework
5.4 Designing a Test Plan
5.5 Focus on Problem Solving: CourierModel Revisited
Investigate: The Serializable Interface — Adding Persistence to the Courier Application
5.6 A Linked List Implementation of the List ADT
5.7 Implementing the Test Plan
5.8 Analysis and Measurement
Exercises
Chapter 6 The Stack Abstract Data Type
6.1 Stack Description
6.2 Stack Specification
6.3 The Stack Interface
6.4 Designing a Test Plan
6.5 Focus on Problem Solving: Evaluation of Postfix Expressions
6.6 Stack Implementation: ListStack–Using the Adapter Design Pattern
6.7 Stack Implementation: ListStack–Using a Linked Data Structure
6.8 Implementing the Test Plan
6.9 Evaluation of the Implementations
Investigate: Measuring the Cost of Using and Adapter
Exercises
Chapter 7 The Queue Abstract Data Type
7.1 Queue Description
7.2 Queue Specification
7.3 The Queue Interface
7.4 Designing a Test Plan
7.5 Focus on Problem Solving: The Leaky Bucket Algorithm
7.6 List Implementation Using the Adapter Design Pattern
7.7 ArrayQueue: Implementing Queue Using an Array
7.8 Testing the Implementation
7.9 Evaluation of the Implementations
Investigate: A First Look at Priority Queues
Exercises
Chapter 8 Recursion
8.1 What Is Recursion?
8.2 Recursive Definitions
8.3 Problem Definitions and Recursive Programming
8.4 Recursion as Iteration
8.5 Evaluating Recursion
8.6 Focus on Problem Solving: Cell Identification in MineSweeper
Investigate: Simulating Recursion Using Loops and a Stack
Exercises
Chapter 9 Sorting and Searching
9.1 Sorting Terminology
9.2 Sorting Primitive Types in an Array
9.3 Comparing Objects
9.4 Sorting Lists and Linked Lists
Investigate: Using Comparators to Sort WorkOrders
9.5 Searching for Objects
9.6 Focus on Problem Solving: External Sorting
Exercises
Chapter 10 Trees
10.1 Tree Terminology
10.2 Binary Tree Description
10.3 Binary Tree Specification
10.4 Implementations of the Binary Tree ADT
10.5 Heaps and Binary Trees
10.6 Focus on Problem Solving: Data Compression Using Huffman Trees
Investigate: A Second Look at Priority Queues
Exercises
Chapter 11 Binary Search Trees
11.1 The Binary Search Tree ADT
11.2 Linked Implementation of BinarySearchTree
11.3 Focus on Problem Solving: A Modifiable Spell Checker
11.4 The Need for a Balanced Search Tree
11.5 AVL Tree: A Balanced Binary Search Treee
Investigate: Finding the kth Smallest Element in a Binary Search Tree
11.6 Splay Tree: A Self-Adjusting Binary Search Tree
Exercises
Chapter 12 The Map ADT
12.1 The Map ADT
12.2 Focus on Problem Solving: A Pizza Ordering System
12.3 Hashing and Hash Tables
12.3 HashMap: A Hash Table Implementation of Map
12.3.1 Testing HashMap
Investigate: Radix Sort
12.4 Ordered Map
12.5 MultiMap
Exercises
|
