Data Structures in Java From Abstract Data Types to the Java Collections Framework

Name: Data Structures in Java From Abstract Data Types to the Java Collections Framework
Availability: InStock
ISBN: 9780321392794

ISBN-10: 0321392795

ISBN-13: 9780321392794

Edition: 2007

Authors: Simon Gray

List price: $173.32

30 day, 100% satisfaction guarantee!

Semester Rental: $19.09 Due date: 8/13/2024

Rental notice: supplementary materials (access codes, CDs, etc.) are not guaranteed with rental orders.

Buy used: $7.16

Buy used: $9.25

Marketplace

2 new & used from $5.70

what's this?

Rush Rewards U
Members Receive:

You have reached 400 XP and carrot coins. That is the daily max!

Description:

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.

Book details

List price: $173.32
Copyright year: 2007
Publisher: Addison Wesley
Publication date: 10/19/2006
Binding: Paperback
Pages: 688
Size: 7.25" wide x 9.25" long x 1.25" tall
Weight: 2.244
Language: English

Playwright Simon Gray was born in Hayling Island, Hampshire, England on October 21, 1936. He received degrees from Dalhousie University in Halifax, Nova Scotia, Canada and from Cambridge University. He has edited a literary review (like the characters in The Common Pursuit) and taught drama, poetry, and English literature in universities, both major and provincial. He has written 40 plays, television plays, and screenplays and five novels, and adapted Fyodor Dostoevsky's The Idiot for the National Theatre. Some of his works include Butley, Otherwise Engaged, Quartermaine's Terms, The Smoking Diaries, The Year of the Jouncer, and The Last Cigarette. He died on August 6, 2008.




Introduction to What We Will Be Studying



Abstraction



Managing Complexity



Abstraction and Abstract Data Types (ADTs)



Algorithms



Algorithm Development



Determining the Cost of an Algorithm



Living with Tradeoffs



Generic Algorithms



Object-Oriented Programming



Enforcing Abstraction: Classes, Encapsulation, and Information Hiding



Creating the New from the Old: Inheritance and Composition



Plugging in Related Objects: Polymorphism



The Software Life Cycle



The Classic Waterfall Model



The Object-Oriented Spiral/Incremental Model



Software Testing



The Unified Modeling Language: Using Pictures to Express Design



Software Design Patterns: Applying Proven Solutions to New Problems



Collections and the Java Collections Framework



Collection Categories



Collection Operations



The Java Collections Framework (JCF)



How We Will Use the Java Collections Framework



The JCF Collection Hierarchy


On the Web



Object-Oriented Programming and Java



Abstraction and Abstract Data Types



Specification of ADTs



Example: a Rectangle ADT



The Object-Oriented Approach



A First Look at the Unified Modeling Language



Characteristics of an Object



Classes and Objects



Characteristics of Good Class Design



Code Reuse through Composition and Inheritance



Composition



Inheritance


Investigate: Inheritance, Packages, and Access Modifiers



Polymorphism and Generic Programming



Case Study: a Shapes Hierarchy



Abstract Shape



Inheritance and Concrete Classes Rectangle and Circle



Overriding Object Methods toString() and equals()



3D Shapes, Interfaces, and the ThreeD Interface



Polymorphism with Shapes



Java Generic Types



Using a Generic Type



Defining a Generic Type



Generic Types and Erasure


Exercises


On the Web



Error Handling, Software Testing, and Program Efficiency



Error Handling with Exceptions



What Can Go Wrong with Your Program?



The Java Exception Hierarchy



Try-Catch Blocks



Throwing Exceptions



Defining Your Own Exception Class



Software Testing



Testing Throughout the Software Development Process



Checking the Specification



Writing Test Cases for Unit Testing



Testing During the Implementation



Testing After the Implementation Is Complete



Testing with JUnit2



Creating a Test Program Using the JUnit Framework



Putting It All Together



When a Test Fails



Analysis and Measurement of Algorithms



Theta ([Theta]) Notation



Big-Oh (0) Notation



Algorithm Measurement


Exercises


On the Web



Fundamental Data Structures: The Array and Linked Structures



The Array Data Structure



Memory Allocation: Static versus Dynamic Arrays



Storage and Access Characteristics



Size versus Capacity of an Array



Array Operations



Traversing an Array (Bidirectional)



Expanding the Capacity of an Array



Replacing an Element in an Array



Inserting an Element into an Array



Deleting an Element from an Array



The Linked Data Structure



Memory Allocation: Dynamic Allocation of Nodes



Storage and Access Characteristics



Size versus Capacity



A Generic Singly Linked Data Structure



A Generic Singly Linked Node: The SLNode[left angle bracket]E[right angle bracket] Class



Basic Operations on a Singly Linked Node



The SinglyLinkedList[left angle bracket]E[right angle bracket] Class



Creating an Instance of the SinglyLinkedList[left angle bracket]E[right angle bracket] Class



Traversing a Singly Linked List (Unidirectional)



Finding a Position or an Element in a Singly Linked List



Replacing an Element in a Singly Linked List



Inserting an Element at the Head of a Singly Linked List



Inserting a Node at an Indexed Position in a Singly Linked List



Deleting a Node from a Singly Linked List



The Doubly Linked Data Structure



Defining a Doubly Linked Node: The DLNode[left angle bracket]E[right angle bracket] Class



Traversing a Doubly Linked List (Bidirectional)



Finding a Position or Element in a Doubly Linked List



Inserting an Element into a Doubly Linked List



Removing an Element from a Doubly Linked List



The Circular Linked List



Selecting a Data Structure


Exercises


On the Web



A Basic Collection Class



The Collection Interface in the Java Collections Framework



Iterators and the Iterator Design Pattern



The Iterator Design Pattern



The java.util.Iterator Interface



Collection Basics: Objects, Casting, Operations, and Iterators



Developing a Test Plan for BasicCollection



Testing with JUnit



Creating a Test Program Using the JUnit Framework



Putting It All Together



The java.util.AbstractCollection Abstract Class



More Java Generics: Inheritance, Wildcards, and Generic Methods



Generics, Type Parameters, and Inheritance Hierarchies



Unbounded Wildcards



Bounded Wildcards



Generic Methods



Implementation of the BasicCollection Class



BasicCollection Task 1: Define Collection Attributes as Data Fields



BasicCollection Task 2: Implement the Abstract Methods size() and iterator()



BasicCollection Task 3: Define the Iterator Class: BasicIterator



BasicCollection Task 4: Implement the Collection Mutator Methods: add() and remove()



Analysis of the Implementation


Investigate: equals(), hashCode(), and toArray()



Cloning


Exercises


On the Web



The List Abstract Data Type



List Description



The List ADT



The List Interface in the Java Collections Framework



The java.util.List Interface



The java.util.ListIterator[left angle bracket]E[right angle bracket] Interface



Examples of List Operations



Designing a Test Plan


Investigate: The Serializable Interface-Adding Persistence to the Courier Application



A Linked List Implementation of the List ADT



The JCF AbstractList and AbstractSequentialList



The LinkedList Class



LinkedList Task 1: Define List attributes



LinkedList Task 2: Implement Abstract Method listIterator(int)



LinkedList Task 3: Define the ListIterator Class: LinkedListIterator



LinkedListIterator Task 1: Map Logical Model to Doubly Linked List



LinkedListIterator Task 2: Identify Data Fields



LinkedListIterator Task 3: Implement Required Methods



LinkedListIterator Task 4: Implement Optional Methods



Implementing the Test Plan



Analysis and Measurement



A Last Comment on Lists in the JCF


Exercises


On the Web



The Stack Abstract Data Type



Stack Description



Stack Specification



The Stack Interface



Designing a Test Plan



Stack Implementation: ListStack-Using the Adapter Design Pattern



The Adapter Software Design Pattern



Building a Stack from a List Using the Adapter Design Pattern



ListStack Task 1: Map Stack Attributes to List Attributes/Methods



ListStack Task 2: Map Stack Methods to List Methods



ListStack Task 3: Implement Stack Methods Using List and the Adapter Pattern



Stack Implementation: LinkedStack-Using a Linked Data Structure



LinkedStack Task 1: Decide Which Linked Structure Representation to Use



LinkedStack Task 2: Map Stack ADT Attributes to a Linked List Implementation?



LinkedStack Task 3: Implement the LinkedStack Methods



Implementing the Test Plan



Evaluation of the Implementations


Investigate: Measuring the Cost of Using an Adapter


Exercises


On the Web



The Queue Abstract Data Type



Queue Description



Queue Specification



The Queue Interface



Designing a Test Plan



List Implementation Using the Adapter Design Pattern



ListQueue Task 1: Choose Which Implementation of List Is Most Appropriate for Representing a Queue



ListQueue Task 2: Decide Which Attributes from List Will Play the Roles of the Queue Attributes



ListQueue Task 3: Select Methods from List That Will Provide the Behavior Needed for the Queue API



ListQueue Task 4: Decide How to Support Queue Behavior or Attributes Not Supported by List



ListQueue Task 5: Define the Exception Classes FullQueueException and EmptyQueueException



ArrayQueue: Implementing Queue Using an Array



ArrayQueue Task 1: Map Queue ADT Attributes to a Circular Array Implementation



ArrayQueue Task 1: Implement the Queue ADT Operations as Methods



Determining Whether the Queue Is Empty



Inserting an Element into a Queue



Clearing the Queue



Testing the Implementation



Evaluation of the Implementations


Investigate: A First Look at Priority Queues


Exercises


On the Web



Recursion



What Is Recursion?



Recursive Definitions



Programming Languages



Data Structures and ADTs



Problem Definitions and Recursive Programming



The Factorial Function



Recursive Searching: The Linear and Binary Search Algorithms



Finding the kth Smallest Value of an Array



Recursion as Iteration



Recursion, Activation Records, and the Runtime Stack



Tail Recursion



Evaluating Recursion



Space and Time



Dynamic Programming and the Fibonacci Numbers



Smart Recursion-Exponentiation


Investigate: Simulating Recursion Using Loops and a Stack


Exercises


On the Web



Sorting and Searching



Sorting Terminology



Sorting Primitive Types in an Array



Selection Sort



Insertion Sort



Quicksort



Merge Sort



Comparing Objects



Modifying the Sort Methods to Use Comparable[left angle bracket]T[right angle bracket]



Customizing a Class to Be Comparable



Sorting Lists and Linked Lists


Investigate: Using Comparators to Sort WorkOrders



Searching for Objects


Exercises


On the Web



Trees



Tree Terminology



Binary Tree Description



Binary Tree Properties



Tree Traversals



Tree Traversals Using an Iterator



Tree Traversals with a Visitor



Binary Tree Specification



The BinaryTree and BinaryTreeNode Interfaces



Designing a Test Plan for BinaryTree



Implementations of the Binary Tree ADT



Array Implementation



Linked Implementation and the BinaryTreeNode Class: Another Recursive Data Structure



LinkedBinaryTree Task 1: Constructor to create a binary tree from an element and two subtrees



LinkedBinaryTree Task 2: Implement remove()



LinkedBinaryTree Task 3: Implement preorderTraversal() using a Visitor



Testing the Implementations



Evaluation of Implementations



Heaps and Binary Trees



Heap ADT Specification and Java Interface



Heap Implementation


Investigate: A Second Look at Priority Queues


Exercises


On the Web



Binary Search Trees



The Binary Search Tree ADT



Binary Search Tree Description



Binary Search Tree Specification



The BinarySearchTree Interface



The Tree Iterator



Designing a Test Plan for BinarySearchTree



Linked Implementation of BinarySearchTree



Class BSTNode



Class LinkedBST



Method contains(): Finding an Element in a LinkedBST



Method add(): Inserting a Node into a LinkedBST



Method remove(): Removing a Node from a Binary Search Tree



Method iterator(): Providing the Client with an Iterator



AbstractBinarySearchTree-an Abstract Class Implementation of BinarySearchTree



The Need for a Balanced Search Tree



AVL Tree: A Balanced Binary Search Tree



Specification



Rotations to Rebalance a BST Tree



Method add()-Adding an Element to an AVL Tree



Analysis



Designing a Test Plan


Investigate: Finding the kth Smallest Element in a Binary Search Tree



Splay Tree: A Self-Adjusting Binary Search Tree



Specification



Designing a Test Plan



Splay Rotations



Implementation



Amortization Analysis


Exercises


On the Web



The Map ADT



The Map ADT



Map Specification



The Map Interface



Designing a Test Plan for a Map



Hashing and Hash Tables



Collision Resolution Strategies



Open Addressing: Linear Probing



Closed Addressing: Chaining



Hashing Functions



HashMap: A Hash Table Implementation of Map



HashMap Task 1: Representing an Entry in a Map with Entry and LinkEntry



HashMap Task 2: Identify HashMap Data Fields



HashMap Task 3: HashMap.put() - Inserting an Entry into the Map



HashMap Task 4: HashMap.containsKey() and HashMap.containsValue()



HashMap Task 5: HashMap.values()-Providing a Collection View of the Values Stored in a Map



HashMap Task 6: HashMapIterator-Providing an Iterator That Can Return Values, Keys, or Entries



Testing HashMap


Investigate: Radix Sort



Ordered Map



MultiMap


Exercises


On the Web



Graphs (located on the Web at www.aw.com/cssupport)



Graph Terminology



Representations of Graphs



Graph Algorithms: Traversals



Graph Algorithms: Minimum Cost Paths and Minimal Spanning Trees



Graph ADTs



Implementation of Graph ADTs


Exercises


Index