Java Software Structures : Designing and Using Data Structures

by Lewis, John; Chase, Joseph

• ISBN13: 9780321245847
• ISBN10: 0321245849
• Edition: 3rd
• Format: Paperback
• Copyright: 2010-01-01
• Publisher: Addison Wesley

Summary

The second edition of Java Software Structures embraces the enhancements of Java 5.0, where all structures and collections are based on generics. The framework of the text walks the reader through three main areas: conceptualization, explanation, and implementation, allowing for a consistent and coherent introduction to data structures. The addition of integrated case studies provides complete examples to aid readers starting with the problem statement, to design rationale, through full implementation. Readers will learn how to develop high-quality software systems using well-designed collections and algorithms.

Table of Contents

Preface	vii
Software Development	1	(28)
Software Engineering	2	(1)
Professionalism and Ethics	3	(1)
Software Quality	3	(5)
Correctness	4	(1)
Reliability	4	(1)
Robustness	5	(1)
Usability	5	(1)
Maintainability	6	(1)
Reusability	6	(1)
Portability	7	(1)
Efficiency	7	(1)
Quality Issues	8	(1)
Development Life Cycle Models	8	(5)
The Waterfall Model	10	(1)
The Spiral Model	11	(1)
The Evolutionary Development Model	12	(1)
The Unified Modeling Language (UML)	13	(5)
UML Relationships	15	(3)
Error Handling	18	(1)
Analysis of Algorithms	19	(5)
Growth Functions and Big O() Notation	20	(1)
Comparing Growth Functions	21	(1)
Analyzing Loop Execution	22	(1)
Nested Loops	23	(1)
Software Engineering and Data Structures	24	(5)
Object-Oriented Design	29	(54)
Overview of Object-Orientation	30	(1)
Using Objects	31	(3)
Abstraction	32	(1)
Creating Objects	33	(1)
Class Libraries and Packages	34	(2)
The import Declaration	35	(1)
State and Behavior	36	(1)
Classes	37	(3)
Instance Data	39	(1)
Encapsulation	40	(3)
Visibility Modifiers	41	(1)
Local Data	42	(1)
Constructors	43	(1)
Method Overloading	43	(2)
References Revisited	45	(5)
The null Reference	45	(1)
The this Reference	46	(1)
Aliases	47	(2)
Garbage Collection	49	(1)
Passing Objects as Parameters	50	(1)
The static Modifier	50	(2)
Static Variables	51	(1)
Static Methods	51	(1)
Wrapper Classes	52	(1)
Interfaces	53	(3)
The Comparable Interface	55	(1)
The Iterator Interface	55	(1)
Inheritance	56	(4)
Derived Classes	56	(2)
The protected Modifier	58	(1)
The super Reference	59	(1)
Overriding Methods	59	(1)
Class Hierarchies	60	(4)
The Object Class	61	(1)
Abstract Classes	62	(2)
Interface Hierarchies	64	(1)
Polymorphism	64	(6)
References and Class Hierarchies	65	(1)
Polymorphism via Inheritance	66	(2)
Polymorphism via Interfaces	68	(2)
Generic Types	70	(1)
Exceptions	71	(12)
Exception Messages	71	(1)
The try Statement	72	(1)
Exception Propagation	73	(1)
The Exception Class Hierarchy	73	(10)
Collections	83	(36)
Introduction to Collections	84	(3)
Abstract Data Types	85	(2)
The Java Collections API	87	(1)
A Set Collection	87	(5)
Interfaces	89	(2)
Iterators	91	(1)
Exceptions	92	(1)
Using a Set: Bingo	92	(4)
Implementing a Set: With Arrays	96	(2)
Managing Capacity	97	(1)
The ArraySet Class	98	(15)
The size and isEmpty Operations	101	(1)
The add Operation	102	(2)
The addAll Operation	104	(1)
The removeRandom Operation	104	(1)
The remove Operation	105	(1)
The union Operation	106	(1)
The contains Operation	107	(1)
The equals Operation	108	(1)
The iterator Operation	109	(2)
The toString Operation	111	(1)
UML Description	112	(1)
Analysis of ArraySet	113	(6)
Analysis of add	113	(1)
Analysis of remove	113	(1)
Analysis of removeRandom	114	(1)
Analysis of addAll	114	(1)
Analysis of find and contains	114	(1)
Analysis of union	114	(1)
Analysis of equals	114	(5)
Linked Structures	119	(24)
References as Links	120	(2)
Managing Linked Lists	122	(3)
Inserting Nodes	122	(2)
Deleting Nodes	124	(1)
Dummy Nodes	124	(1)
Elements Without Links	125	(1)
Doubly Linked Lists	126	(1)
Implementing a Set: with Links	126	(9)
The LinkedSet Class	127	(3)
The add Operation	130	(1)
The removeRandom Operation	130	(2)
The remove Operation	132	(1)
The iterator Operation	133	(2)
Analysis of LinkedSet	135	(8)
Analysis of add	135	(1)
Analysis of remove	136	(1)
Analysis of removeRandom	137	(6)
Black Jack	143	(34)
A Black Jack Game	144	(1)
Initial Design	144	(4)
Implementing a Black Jack Game	148	(29)
The Card Class	148	(4)
The Deck Class	152	(5)
The Hand Class	157	(4)
The BlackJack Class	161	(4)
The BlackJackGUI Class	165	(7)
The BlackJackDemo Class	172	(5)
Stacks	177	(34)
A Stack Adt	178	(4)
Using Stacks: Evaluating Postfix Expressions	182	(7)
Using Stacks: Traversing a Maze	189	(6)
Implementing Stacks: With Links	195	(3)
The push Operation	195	(1)
The pop Operation	196	(2)
Other Operations	198	(1)
Implementing Stacks: With Arrays	198	(3)
The push Operation	199	(1)
The pop Operation	200	(1)
Other Operations	201	(1)
Implementing Stacks: The java.util.Stack Class	201	(2)
Unique Operations	202	(1)
Inheritance and Implementation	202	(1)
Analysis of Stack Implementations	203	(8)
Analysis of push	204	(1)
Analysis of pop	205	(6)
Queues	211	(38)
A Queue Adt	212	(3)
Using Queues: Code Keys	215	(3)
Using Queues: Ticket Counter Simulation	218	(4)
Using Queues: Radix Sort	222	(5)
Implementing Queues: With Links	227	(5)
The enqueue Operation	228	(2)
The dequeue Operation	230	(1)
Other Operations	231	(1)
Implementing Queues: with Arrays	232	(3)
The enqueue Operation	232	(1)
The dequeue Operation	233	(2)
Other Operations	235	(1)
Implementing Queues: With Circular Arrays	235	(4)
Analysis of Queue Implementations	239	(10)
enqueue	240	(1)
dequeue	241	(8)
Lists	249	(40)
A List Adt	250	(7)
Using Ordered Lists: Tournament Maker	257	(6)
Using Index Lists: The Josephus Problem	263	(4)
Implementing Lists: With Arrays	267	(6)
The remove Operation	267	(3)
The contains Operation	270	(1)
The add Operation for an Ordered List	270	(1)
Operations Particular to Unordered Lists	271	(1)
Operations Particular to Indexed Lists	272	(1)
Implementing Lists: With Links	273	(5)
The remove Operation	273	(1)
Doubly Linked Lists	274	(4)
Analysis of List Implementations	278	(11)
Analysis of Ordered List Implementations	280	(1)
Analysis of Unordered List Implementations	280	(3)
Analysis of Indexed List Implementations	283	(6)
Calculator	289	(22)
A Calculator	290	(1)
Initial Design	290	(4)
Implementing a Calculator	294	(17)
The infixToPostfix Class	294	(6)
The listPostfixEvaluator Class	300	(3)
The CalculatorGUI Class	303	(5)
The CalculatorDemo Class	308	(3)
Recursion	311	(24)
Recursive Thinking	312	(2)
Infinite Recursion	313	(1)
Recursion in Math	313	(1)
Recursive Programming	314	(4)
Recursion vs. Iteration	317	(1)
Direct vs. Indirect Recursion	317	(1)
Using Recursion	318	(10)
Traversing a Maze	318	(5)
The Towers of Hanoi	323	(5)
Analyzing Recursive Algorithms	328	(7)
Sorting and Searching	335	(26)
Searching	336	(5)
Linear Search	336	(2)
Binary Search	338	(2)
Comparing Search Algorithms	340	(1)
Sorting	341	(20)
Selection Sort	345	(2)
Insertion Sort	347	(1)
Bubble Sort	348	(3)
Quick Sort	351	(3)
Merge Sort	354	(7)
Trees	361	(34)
Trees	362	(3)
Tree Classifications	363	(2)
Strategies for Implementing Trees	365	(3)
Computational Strategy for Array Implementation of Trees	365	(1)
Simulated Link Strategy for Array Implementation of Trees	365	(2)
Analysis of Trees	367	(1)
Tree Traversals	368	(3)
Preorder Traversal	368	(1)
Inorder Traversal	369	(1)
Postorder Traversal	369	(1)
Level-Order Traversal	370	(1)
Implementing Binary Trees	371	(9)
The removeLeftSubtree Method	377	(1)
The find Method	378	(1)
The iteratorInOrder Method	379	(1)
Using Binary Trees: Expression Trees	380	(15)
Binary Search Trees	395	(38)
A Binary Search Tree	396	(2)
Implementing Binary Search Trees: With Links	398	(8)
The addElement Operation	398	(3)
The removeElement Operation	401	(3)
The removeAllOccurrences Operation	404	(1)
The removeMin Operation	405	(1)
Using Binary Search Trees: Implementing Ordered Lists	406	(4)
Analysis of the BinarySearchTreeList Implementation	409	(1)
Balanced Binary Search Trees	410	(4)
Right Rotation	411	(1)
Left Rotation	412	(1)
Rightleft Rotation	412	(1)
Leftright Rotation	413	(1)
Implementing Binary Search Trees: Avl Trees	414	(3)
Right Rotation in an AVL Tree	414	(1)
Left Rotation in an AVL Tree	414	(1)
Rightleft Rotation in an AVL Tree	415	(2)
Leftright Rotation in an AVL Tree	417	(1)
Implementing Binary Search Trees: Red/Black Trees	417	(6)
Insertion into a Red/Black Tree	418	(3)
Element Removal from a Red/Black Tree	421	(2)
Implementing Binary Search Trees: The Java Collections API	423	(10)
Ancestor Tree	433	(38)
Ancestor Tree	434	(1)
Initial Design	434	(5)
Implementing An Ancestor Tree	439	(32)
The Person Class	439	(1)
The AncestorTreeNode Class	439	(1)
The AncestorTree Class	439	(12)
The AncestorGUI Class	451	(16)
The AncestorDemo Class	467	(4)
Heaps	471	(26)
A Heap	472	(4)
The addElement Operation	472	(3)
The removeMin Operation	475	(1)
The findMin Operation	476	(1)
Using Heaps: Heap Sort	476	(1)
Using Heaps: Priority Queues	477	(4)
Implementing Heaps: With Links	481	(6)
The addElement Operation	481	(3)
The removeMin Operation	484	(3)
The findMin Operation	487	(1)
Implementing Heaps: With Arrays	487	(3)
The addElement Operation	487	(1)
The removeMin Operation	488	(2)
The findMin Operation	490	(1)
Analysis of Heap Implementations	490	(7)
The addElement Operation	490	(1)
The removeMin Operation	491	(1)
The findMin Operation	491	(1)
Heap Sort	491	(6)
Multi-way Search Trees	497	(18)
Combining Tree Concepts	498	(1)
2-3 Trees	498	(7)
Inserting Elements into a 2-3 Tree	499	(2)
Removing Elements from a 2-3 Tree	501	(4)
2-4 Trees	505	(1)
B-Trees	506	(1)
Motivation For B-Trees	507	(2)
B*-trees	507	(1)
B+-trees	508	(1)
Analysis of B-trees	508	(1)
Implementation Strategies For B-Trees	509	(6)
Hashing	515	(30)
A Hashing	516	(2)
Hashing Functions	518	(3)
The Division Method	519	(1)
The Folding Method	519	(1)
The Mid-square Method	520	(1)
The Radix Transformation Method	520	(1)
The Digit Analysis Method	520	(1)
The Length-Dependent Method	521	(1)
Hashing Functions in the Java Language	521	(1)
Resolving Collisions	521	(7)
Chaining	522	(2)
Open Addressing	524	(4)
Deleting Elements From A Hash Table	528	(3)
Deleting from a Chained Implementation	529	(1)
Deleting from an Open Addressing Implementation	529	(2)
Hash Tables in the Java Collections API	531	(14)
The Hashtable Class	531	(2)
The HashSet Class	533	(1)
The HashMap Class	533	(1)
The IdentityHashMap Class	534	(3)
The WeakHashMap Class	537	(1)
LinkedHashSet and LinkedHashMap	538	(7)
Graphs	545	(24)
Undirected Graphs	546	(2)
Directed Graphs	548	(1)
Networks	549	(2)
Common Graph Algorithms	551	(9)
Traversals	551	(4)
Testing for Connectivity	555	(1)
Minimum Spanning Trees	556	(3)
Determining the Shortest Path	559	(1)
Strategies for Implementing Graphs	560	(9)
Adjacency Lists	560	(1)
Adjacency Matrices	561	(8)
Web Crawler	569	(18)
Web Crawler	570	(1)
Initial Design	570	(3)
Implementing a Web Crawler	573	(14)
The WebCrawler Class	573	(7)
The WebCrawlerGUI Class	580	(4)
The WebCrawlerDemo Class	584	(3)
Index	587