Data Structures Outside-In with Java,9780131986190

Data Structures Outside-In with Java

by
Edition: 1st
ISBN13: 9780131986190
ISBN10: 0131986198
Format: Paperback
Pub. Date: 2006-11-10
Publisher(s): Pearson
List Price: $179.98

Buy Used

In Stock Usually Ships in 24-48 Hours
$134.99
Add to Cart

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $6.59

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

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

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.