Java Collections An Introduction to Abstract Data Types, Data Structures and Algorithms

by Watt, David A.; Brown, Deryck F.

• ISBN13: 9780471899785
• ISBN10: 047189978X
• Edition: 1st
• Format: Paperback
• Copyright: 2001-03-30
• Publisher: WILEY

Summary

A unique, practical approach to working with collection classes in Java 2 Software developers new to Java will find the practical, software-engineering based approach taken by this book extremely refreshing. With an emphasis more on software design and less on theory, Java Collections explores in detail Java 2 collection classes, helping programmers choose the best collection classes for each application they work on. Watt and Brown explore abstract data types (ADTs) that turn up again and again in software design, using them to provide context for the data structures required for their implementation and the algorithms associated with the data structures. Numerous worked examples, several large case studies, and end-of-chapter exercises are also provided.

Author Biography

<B>David Watt</B> is a Professor of Computing Science at the University of Glasgow. <BR> <B>Deryck Brown</B> is a Senior Lecturer in Computing Science at the Robert Gordon University, Aberdeen.

Table of Contents

Preface	xi
Introduction	1	(10)
Historical background	1	(5)
Algorithms and programs	6	(1)
Abstract data types and data structures	7	(4)
Summary	9	(1)
Exercises	9	(2)
Algorithms	11	(23)
Principles of algorithms	11	(3)
Efficiency of algorithms	14	(3)
Complexity of algonthms	17	(7)
Recursive algorithms	24	(10)
Summary	31	(1)
Exercises	31	(3)
The Array Data Structure	34	(33)
Arrays	34	(4)
Insertion	38	(1)
Deletion	39	(1)
Searching	40	(6)
Merging	46	(3)
Sorting	49	(18)
Summary	62	(1)
Exercises	62	(5)
Linked-List Data Structures	67	(30)
Linked lists	67	(11)
Insertion	78	(3)
Deletion	81	(5)
Searching	86	(2)
Merging	88	(3)
Sorting	91	(6)
Summary	94	(1)
Exercises	95	(2)
Abstract Data Types	97	(28)
Data types	97	(6)
Abstract data types	103	(8)
Abstract data type design	111	(3)
String abstract data types	114	(6)
Collection abstract data types	120	(1)
Abstract data types in the Java class library	120	(5)
Summary	122	(1)
Exercises	123	(2)
Stack Abstract Data Types	125	(24)
The concept of a stack	125	(1)
Applications of stacks	125	(4)
A stack abstract data type	129	(1)
Implementation of bounded stacks using arrays	130	(2)
Implementation of unbounded stacks using linked lists	132	(3)
Case study: solving and generating mazes	135	(14)
Summary	146	(1)
Exercises	146	(3)
Queue Abstract Data Types	149	(21)
The concept of a queue	149	(1)
Applications of queues	149	(2)
A queue abstract data type	151	(1)
Implementation of bounded queues using arrays	152	(4)
Implementation of unbounded queues using linked lists	156	(1)
Case study: a traffic simulator	157	(13)
Summary	166	(1)
Exercises	167	(3)
List Abstract Data Types	170	(32)
The concept of a list	170	(1)
Applications of lists	171	(1)
A list abstract data type	172	(3)
Iterators	175	(4)
Implementation of bounded lists using arrays	179	(6)
Implementation of unbounded lists using linked lists	185	(6)
Lists in the Java class library	191	(1)
Case study: a videotape manager	192	(10)
Summary	199	(1)
Exercises	199	(3)
Set Abstract Data Types	202	(34)
The concept of a set	202	(2)
Applications of sets	204	(1)
A set abstract data type	205	(4)
Implementation of bounded sets using arrays	209	(2)
Implementation of unbounded sets using linked lists	211	(6)
Implementation of small-integer sets using boolean arrays	217	(3)
Sets in the Java class library	220	(3)
Case study: an interactive spell-checker	223	(13)
Summary	230	(2)
Exercises	232	(4)
Binary Tree Data Structures	236	(38)
Binary trees	236	(6)
Searching	242	(3)
Insertion	245	(2)
Deletion	247	(9)
Traversal	256	(5)
Merging	261	(1)
Implementation of unbounded sets using binary search trees	262	(12)
Summary	270	(1)
Exercises	270	(4)
Map Abstract Data Types	274	(33)
The concept of a map	274	(2)
Applications of maps	276	(1)
A map abstract data type	277	(4)
Implementation of small-integer-key maps using key-indexed arrays	281	(2)
Implementation of bounded maps using arrays	283	(4)
Implementation of unbounded maps using linked lists	287	(1)
Implementation of unbounded maps using binary search trees	288	(2)
Maps in the Java class library	290	(3)
Case study a student record system	293	(14)
Summary	303	(1)
Exercises	304	(3)
Hash-Table Data Structures	307	(30)
Hash tables	307	(2)
Closed-bucket hash tables	309	(7)
Open-bucket hash tables	316	(15)
Implementations of sets using hash tables	331	(1)
Implementations of maps using hash tables	332	(5)
Summary	334	(1)
Exercises	334	(3)
Priority-Queue Abstract Data Types	337	(29)
The concept of a priority queues	337	(1)
Applications of priority queues	338	(1)
A priority-queue abstract data type	339	(2)
Implementations of priority queues using linked lists	341	(3)
The heap data structure	344	(11)
Implementation of priority queues using heaps	355	(1)
Case study: an improved traffic simulator	355	(11)
Summary	361	(2)
Exercises	363	(3)
Tree Abstract Data Types	366	(31)
The concept of a tree	366	(1)
Applications of trees	367	(2)
A tree abstract data type	369	(1)
A linked implementation of trees	369	(9)
Specialized tree abstract data types	378	(3)
Case study: game playing	381	(16)
Summary	394	(1)
Exercises	395	(2)
Graph Abstract Data Types	397	(38)
The concept of a graph	397	(2)
Applications of graphs	399	(1)
Graph abstract data types	400	(3)
Edge-set representation of graphs	403	(5)
Adjacency-set representation of graphs	408	(5)
Adjacency-matrix representation of graphs	413	(2)
Graph traversal	415	(5)
Topological sort	420	(2)
Case study: material requirements planning	422	(13)
Summary	431	(1)
Exercises	431	(4)
Balanced Search Tree Data Structures	435	(34)
AVL-trees	435	(12)
B-trees	447	(22)
Summary	466	(1)
Exercises	467	(2)
Conclusion	469	(15)
Abstract data types and object-oriented design	469	(2)
Abstract data types as reusable software components	471	(1)
Homogeneous and heterogeneous collections	472	(4)
Extending Java with parameterized classes	476	(1)
Case study: a student record system revisited	477	(7)
Summary	482	(1)
Exercises	482	(2)
A Summary of Mathematics for Algorithm Analysis	484	(11)
Powers	484	(2)
Loganthms	486	(1)
Senes summations	487	(1)
Recurrences	488	(2)
O-notation	490	(5)
B Summary of Java	495	(22)
Basics	495	(3)
Classes	498	(8)
Interfaces	506	(3)
Packages	509	(1)
Exceptions	510	(4)
Inner classes and inner interfaces	514	(3)
C Summary of the Java Collections Framework	517	(20)
Collections	517	(3)
Lists	520	(4)
Sets	524	(4)
Maps	528	(5)
Orderings	533	(1)
Iterators	534	(3)
Further reading	537	(3)
Bibliographic notes	537	(2)
Bibliography	539	(1)
Index	540