Data Structures Outside-In with Java

by Venugopal, Sesh

• ISBN13: 9780131986190
• ISBN10: 0131986198
• Edition: 1st
• Format: Paperback
• Copyright: 2006-11-10
• Publisher: Pearson

Summary

This innovative new book encourages readers to utilize the "Outside-In" approach to learning the use, design and implementation of data structures. The author introduces every data structure by first narrating its properties and use in applications (the "outside" view). This provides a clear introduction to data structures with realistic context where it is used. Venugopal then details how to build data structures (the "inside" view); readers learn how to evaluate usability, flexibility, extensibility, and performance in designing and implementing classic data structures.

Table of Contents

Preface	v
List of Class Files	xi
Object-Oriented Programming in Java	1	(87)
Objects and Encapsulation	2	(1)
Objects	2	(1)
Lifetime, State, and Messages	2	(1)
Clients of an Object	3	(1)
Separation of Interface from Implementation	3	(1)
Classes	3	(10)
State and Behavior	5	(1)
Method Overloading	5	(1)
Object Creation, Constructors, Garbage Collection	6	(3)
Method Invocation	9	(1)
Static Fields and Methods	9	(3)
Object References	12	(1)
Inheritance	13	(5)
Superclass and Subclass	13	(2)
Inherited and Specialized Fields	15	(1)
Constructors	16	(1)
Object Creation	16	(1)
Inherited and Specialized Methods	17	(1)
Method Overriding	18	(1)
The Object Class	18	(4)
The equals Method	19	(2)
The toString Method	21	(1)
The clone Method	21	(1)
Exceptions	22	(18)
Interpreting an Exception Message	23	(3)
Homegrown Error Handling	26	(5)
Throwing an Exception	31	(2)
Catching an Exception	33	(5)
Exception Class	38	(2)
Input and Output	40	(8)
Terminal-Driven IO	40	(2)
File-Based IO	42	(4)
String Tokenizing	46	(2)
Writing an Exception Class	48	(1)
Class Packages	48	(7)
Java Packages	49	(1)
Organizing Packages	50	(4)
Name Conflict Resolution	54	(1)
Access Control	55	(2)
Private Access	55	(1)
Package Access	56	(1)
Protected Access	56	(1)
Public Access	56	(1)
An Example	57	(1)
Polymorphism	57	(5)
Polymorphic Reference	58	(1)
Casting up the Class Hierarchy	59	(1)
Casting Down the Class Hierarchy	60	(1)
The instanceof Operator	61	(1)
Abstract Classes	62	(2)
Abstract Class Shape	62	(1)
Abstract Class Properties	63	(1)
A Game Park Example	64	(3)
Interfaces	67	(3)
The Java interface Construct	67	(1)
Implementing an Interface	67	(1)
Interface as a Type	68	(1)
The Need for Interfaces	68	(2)
Extending Interfaces	70	(1)
Generics	70	(10)
Using java.util.ArrayList for Collections	72	(1)
The java.util.ArrayList Public Interface	73	(1)
Implementing a Generic Class	74	(1)
Implementing a Generic Interface	75	(3)
Static Template Methods	78	(2)
Summary	80	(2)
Exercises	82	(2)
Programming Problems	84	(4)
The Big Picture	88	(11)
What Are Data Structures?	89	(1)
What Data Structures Do We Study?	89	(3)
What Are Abstract Data Types?	92	(2)
Why OOP and Java for Data Structures?	94	(2)
How Do I choose the Right Data Structures?	96	(3)
Efficiency of Algorithms	99	(20)
Polynomial Arithmetic: A Running Example	99	(2)
Basic Operations	101	(2)
Input Size	103	(1)
Asymptotic Growth of Functions	104	(2)
Order and Big Oh	106	(6)
Typical Running-Time Orders	108	(2)
Multi-Variable Order	110	(1)
Relative Order	111	(1)
Order Arithmetic	112	(1)
Worst-Case and Average	112	(3)
Summary	115	(1)
Exercises	116	(3)
Unordered List	119	(40)
Unordered List Properties	120	(1)
Sequential Search	121	(4)
Average Case Analysis	122	(2)
Rearranging Data Based on Search Patterns	124	(1)
A List Class	125	(2)
An ExpenseList Class Using List	127	(10)
Expense Class Interface	128	(1)
Expense Class	128	(2)
ExpenseList Class Interface	130	(1)
ExpenseList Class Implementation	131	(2)
Equality of Objects and Searching	133	(4)
Linked List	137	(8)
Node	138	(1)
Insertion	139	(1)
Deletion	140	(1)
Access	141	(1)
Circular Linked List	142	(3)
A LinkedList Class	145	(5)
List Class Implementation	150	(2)
Summary	152	(1)
Exercises	153	(2)
Programming Problems	155	(4)
Ordered List	159	(30)
Introduction	160	(1)
Binary Search	161	(3)
Divide in Half	161	(1)
Algorithm	162	(2)
Ordering: Interface java.lang.Comparable	164	(2)
An OrderedList Class	166	(4)
Merging Ordered Lists	170	(4)
Two-Finger Merge Algorithm	171	(3)
List Consolidation Using OrderedList	174	(5)
Merger: A Utility Class	175	(2)
A Consolidation Class	177	(2)
OrderedList Class Implementation	179	(3)
Summary	182	(1)
Exercises	183	(4)
Programming Problems	187	(2)
Queue	189	(18)
Queue Properties	189	(2)
UNIX Print Queue	191	(1)
A Queue Class	192	(1)
A PrintQueue Class Using Queue	193	(5)
Queue Class Implementation	198	(5)
Design 1: Using Array-Based Storage	198	(3)
Design 2: Using LinkedList	201	(2)
Summary	203	(1)
Exercises	203	(2)
Programming Problems	205	(2)
Stack	207	(22)
Stack Properties	207	(1)
Stack Applications	208	(5)
Parentheses Matching	209	(1)
Postfix Expression Evaluation	209	(3)
Infix to Postfix Conversion	212	(1)
A Stack Class	213	(1)
A Postfix Expression Evaluation Package	213	(9)
Class PostfixEvaluator	214	(2)
Class StatusKeeper	216	(1)
Class StackKeeper	217	(2)
Class PostfixEvaluator Implementation	219	(3)
Stack Class Implementation	222	(2)
Design 1: Array List for Storage	222	(1)
Design 2: Linked List for Storage	222	(2)
Summary	224	(1)
Exercises	224	(2)
Programming Problems	226	(3)
Recursion	229	(25)
Recursive Definitions	230	(4)
List	230	(2)
Ordered List	232	(1)
Factorial Function	232	(1)
Fibonacci Sequence	233	(1)
Recursive Programs and Backing Out	234	(6)
Computing the Factorial	234	(3)
Computing the Fibonacci Sequence	237	(1)
Recursion with Linked Lists	237	(3)
Recursion on an Array: Binary Search	240	(1)
Towers of Hanoi: An Application	241	(3)
A Recursive Definition	241	(3)
A Recursive Program	244	(1)
Recursion and Stacks	244	(2)
Drawbacks of Recursion	246	(1)
Tail Recursion	246	(3)
Summary	249	(1)
Exercises	249	(2)
Programming Problems	251	(3)
Binary Tree and General Tree	254	(47)
Binary Tree Properties	255	(6)
Components	255	(1)
Position as Meaning	256	(1)
Structure	257	(2)
Recursive Definitions	259	(2)
Binary Tree Traversals	261	(3)
A BinaryTree Class	264	(3)
Storing and Recreating a Binary Tree	267	(4)
Signature of a Binary Tree	268	(1)
Building a Binary Tree from its Signature	269	(2)
Huffman Coding	271	(11)
Statistical and Dictionary Coding	271	(1)
Algorithm	272	(2)
Average Code Length and Prefix Property	274	(1)
A Huffman Class Using BinaryTree	275	(7)
BinaryTree Class Implementation	282	(3)
Stack-Based Traversals	285	(2)
Inorder Traversal of Binary Tree	285	(2)
A Visitor Class	287	(1)
General Tree	287	(5)
Example: Hierarchy in a University	288	(1)
Example: UNIX Filesystem	288	(2)
Space Issues in Implementation	290	(1)
Correspondence with Binary Tree	290	(1)
Signature of General Tree	291	(1)
Summary	292	(2)
Exercises	294	(3)
Programming Problems	297	(4)
Binary Search Tree and AVL Tree	301	(46)
Comparison Tree	302	(4)
Search Time Using Comparison Tree	303	(2)
Height of Comparison Tree	305	(1)
Binary Search Tree Properties	306	(2)
Binary Search Tree Operations	308	(3)
Search	308	(1)
Insert	308	(1)
Delete	308	(3)
A BinarySearchTree Class	311	(2)
Using Class BinarySearchTree	313	(3)
Example: Treesort	313	(1)
Example: Counting Keys	314	(2)
BinarySearchTree Class Implementation	316	(6)
Search Implementation	317	(1)
Insert Implementation	317	(1)
Delete Implementation	318	(3)
Convenience Methods and Traversals	321	(1)
AVL Tree	322	(16)
AVL Tree Structure	322	(2)
Search, Insert, Delete Overview	324	(1)
Rotation	324	(1)
Insertion	325	(3)
Deletion	328	(6)
Running Times of AVL Tree Operations	334	(1)
AVL Insert and Delete: Generalization	334	(4)
Binary Search: Average Number of Comparisons	338	(2)
Summary	340	(1)
Exercises	341	(3)
Programming Problems	344	(3)
Heap	347	(29)
Heap as Priority Queue	347	(1)
Heap Properties	348	(2)
Max and Min Heaps	349	(1)
Heap Operations	350	(2)
Insert	350	(1)
Delete	351	(1)
A Heap Class	352	(1)
Priority Scheduling with Heap	352	(10)
Overview	352	(3)
A Scheduling Package Using Heap	355	(7)
Sorting with the Heap Class	362	(1)
Example: Sorting Integers	362	(1)
Heap Class Implementation	363	(5)
Array Storage	363	(3)
Implementation Using ArrayList	366	(2)
Updatable Heap	368	(3)
Designing an Updatable Heap	368	(1)
Handles to Heap Entries	369	(1)
Shared Handle Array	369	(1)
Encapsulating Handles within a Heap	370	(1)
Recycling Free Handle Space	371	(1)
Summary	371	(1)
Exercises	372	(1)
Programming Problems	373	(3)
Hash Table	376	(20)
Motivation	376	(2)
Hashing	378	(1)
Collision Resolution	379	(5)
Linear Probing	380	(1)
Quadratic Probing	381	(1)
Chaining	382	(1)
Comparison of Running Times	383	(1)
The java.util.HashMap Class	384	(7)
Table and Load Factor	385	(1)
Storage of Entries	386	(1)
Adding an Entry	387	(2)
Rehashing	389	(2)
Searching	391	(1)
Quadratic Probing: Repetition of Probe Locations	391	(1)
Summary	392	(1)
Exercises	393	(1)
Programming Problems	394	(2)
Sorting	396	(27)
Insertion Sort	396	(4)
Sorting by Divide and Conquer	400	(8)
Quicksort	400	(6)
Mergesort	406	(2)
Heapsort	408	(4)
Building a Heap in Linear Time	409	(2)
Sorting a Heap	411	(1)
Radix Sort	412	(2)
Implementation: A Quicksort Class	414	(3)
Heap Build: Linear Running Time	417	(1)
Summary	418	(1)
Exercises	419	(2)
Programming Problems	421	(2)
Graphs I: Algorithms	423	(32)
Modeling Relationships Using Graphs	423	(6)
Undirected Graphs	424	(1)
Directed Graphs	425	(3)
Weighted Graphs	428	(1)
Graph Representation	429	(2)
Graph Traversals	431	(6)
Depth-First Search for Undirected Graphs	431	(2)
Breadth-First Search for Undirected Graphs	433	(1)
Traversal Driver	434	(2)
Traversals for Directed Graphs	436	(1)
Topological Sort on a Directed Graph	437	(5)
Partial and Total Order	437	(1)
Topological Numbering	438	(1)
Topological Sorting Using Depth-First Search	439	(2)
Topological Sorting Using Breadth-First Search	441	(1)
Connected Components of an Undirected Graph	442	(1)
Shortest Paths in a Weighted Directed Graph	443	(8)
Dijkstra's Single-Source Algorithm	443	(8)
Summary	451	(1)
Exercises	451	(4)
Graphs II: Implementation	455	(30)
A Directed Graph Class: DirGraph	456	(5)
Vertex Numbering	457	(1)
Neighbor Class	458	(1)
Exercising the DirGraph Class	459	(2)
An Undirected Graph Class: UndirGraph	461	(2)
A Depth-First Search Class: DFS	463	(4)
Design and Interface	463	(1)
Visitor Class	464	(1)
DFS Implementation	465	(2)
A Topological Sort Class: DFSTopsort	467	(2)
TopVisitor: Extending the Visitor Class	467	(1)
DFSTopsort Implementation	468	(1)
A Connected Components Class: DFSConncomp	469	(1)
ConnVisitor: Extending the Visitor Class	469	(1)
DFSConncomp Implementation	470	(1)
A Shortest-Paths Class: ShortestPaths	470	(6)
WeightedNeighbor: Extending the Neighbor Class	471	(1)
ShortestPaths Implementation	472	(4)
Graph Implementation	476	(6)
DirGraph Implementation	477	(3)
UndirGraph Class Implementation	480	(1)
Implementation of Weighted Graphs	481	(1)
Summary	482	(1)
Programming Problems	483	(2)
Index	485