Public boolean record int score

Write A JAVA Program

Reserved Words Reserved words are also called keywords. You may not redefine any of these reserved words. Their meanings are determined by the Java language and cannot be changed. In particular, you cannot use any of these reserved words for variable names, method names, or class names.

abstract false package void

assert final private volatile

finally protected

boolean float public while

break for

byte return

goto

case short

catch if static

char implements strictfp

class import super

const instanceof switch

continue int synchronized

interface

default this

do long throw

double throws

native transient

else new true

enum null try

extends

This page intentionally left blank

Operator Precedence In the following list, operators on the same line are of equal precedence. As you move down the list, each line is of lower precedence. When the order of operations is not dictated by parenthe- ses, the operator of higher precedence executes before an operator of lower precedence. When operators have equal precedence, binary operators execute in left-to-right order, and unary oper- ators execute in right-to-left order.

Highest Precedence The unary operators +, -, ++, --, !, ~ The unary operators new and (type) The binary operators *, /, % The binary operators +, - The binary (shift) operators <<, >>, >>> The binary operators <, >, <=, >= The binary operators ==, != The binary operator & The binary operator ^ The binary operator | The binary operator && The binary operator || The ternary (conditional) operator ? : Assignment operators =, *=, /=, %=, +=, -=, <<=, >>=, >>>=, &=, ^=, |= Lowest Precedence

Primitive Data Types

Type Size Values

Integer

byte 1 byte -128 to 127

short 2 bytes -32,768 to 32,767

int 4 bytes -2,147,483,648 to 2,147,483,647

long 8 bytes -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

Real

float 4 bytes -3.402824 x 1038 to 3.402824 x 1038

double 8 bytes -1.79769313486232 x 10308 to 1.79769313486232 x 10308

Character (Unicode)

char 2 bytes All Unicode values between 0 and 65,535

Boolean

boolean 1 bit true, false

Unicode Character Codes The printable characters shown are a subset of the Unicode character set known as the ASCII character set. The numbering is the same whether the characters are considered to be members of the Unicode character set or members of the ASCII character set. (Character number 32 is the blank.)

32 56 8 80 P 104 h

33 ! 57 9 81 Q 105 i

34 " 58 : 82 R 106 j

35 # 59 ; 83 S 107 k

36 $ 60 < 84 T 108 l

37 % 61 = 85 U 109 m

38 & 62 > 86 V 110 n

39 ' 63 ? 87 W 111 o

40 ( 64 @ 88 X 112 p

41 ) 65 A 89 Y 113 q

42 * 66 B 90 Z 114 r

43 + 67 C 91 [ 115 s

44 , 68 D 92 \ 116 t

45 - 69 E 93 ] 117 u

46 . 70 F 94 ^ 118 v

47 / 71 G 95 _ 119 w

48 0 72 H 96 ‘ 120 x

49 1 73 I 97 a 121 y

50 2 74 J 98 b 122 z

51 3 75 K 99 c 123 {

52 4 76 L 100 d 124 |

53 5 77 M 101 e 125 }

54 6 78 N 102 f 126 ~

55 7 79 O 103 g

Data Structures and Abstractions with Java™

Third Edition

\

Frank M. Carrano University of Rhode Island

Prentice Hall Boston Columbus Indianpolis New York San Francisco Upper Saddle River

Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo

Editorial Director: Marcia Horton Editor in Chief: Michael Hirsch Acquisitions Editor: Tracy Dunkelberger Editorial Assistant: Stephanie Sellinger Director of Marketing: Patrice Jones Marketing Manager: Yezan Alayan Marketing Coordinator: Kathryn Ferranti Vice President, Production: Vince O’Brien Managing Editor: Jeff Holcomb Associate Managing Editor: Robert Engelhardt Manufacturing Manager: Nick Sklitsis Operations Specialist: Lisa McDowell

Cover Designer: Anthony Gemmellaro Photo Researcher: AV Manager, Rights and

Permissions: Karen Sanatar Cover Image Credit: © Color Symphony/

Shutterstock Media Editor: Dan Sandin Full-Service Project Management: GEX

Publishing Services Composition: GEX Publishing Services Printer/Binder: Edwards Brothers Cover Printer: Lehigh-Phoenix Color, Hagerstown

Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on the appropriate page within text.

Java is a trademark of the Oracle Corporation, 500 Oracle Parkway, Redwood Shores, CA 94065.

Copyright © 2012, 2007 and 2003 by Pearson Education, Inc., publishing as Prentice Hall. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290.

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data Carrano, Frank M. Data structures and abstractions with Java / Frank M. Carrano. -- 3rd ed. p. cm. Includes bibliographical references and index. ISBN-13: 978-0-13-610091-1 (alk. paper) ISBN-10: 0-13-610091-0 (alk. paper) 1. Data structures (Computer science) 2. Java (Computer program language) I. Title. QA76.9.D33C37 2012 005.13'3--dc23 2011029581

10 9 8 7 6 5 4 3 2 1

ISBN-10: 0-13-610091-0 ISBN-13: 978-0-13-610091-1

Welcome to the third edition of Data Structures and Abstractions with Java, a book for an introductory course in data structures, typically known as CS-2. Readers of my book Imagine! Java can consider this one as a sequel.

I wrote this book with you in mind—whether you are an instructor or a student—based upon my experi- ences during more than three decades of teaching undergraduate computer science. I wanted my book to be reader friendly so that students could learn more easily and instructors could teach more effectively. To this end, you will find the material covered in small pieces—I call them “segments”—that are easy to digest and facilitate learning. Numerous examples that mimic real-world situations provide a context for the new material and help to make it easier for students to learn and retain abstract concepts. Many simple figures illustrate and clarify com- plicated ideas. Included are over 60 video tutorials to supplement the instruction and help students when their instructor is unavailable.

I hope that you enjoy reading this book. Like many others before you, you can learn—or teach—data structures in an effective and sustainable way.

Warm regards, Frank M. Carrano

P. S. I am always available to connect with instructors and students who use my books. Here are a few ways you can reach me:

Find me on Facebook: www.facebook.com/makingitreal

Follow me on Twitter: twitter.com/Frank_M_Carrano

Send me an e-mail: carrano@acm.org

Post on my blog: frank-m-carrano.com/makingitreal

Fr om

th e

A ut

ho r

iii

www.facebook.com/makingitreal
iv

The topics that we cover in this book deal with the various ways of organizing data so that a given appli- cation can access and manipulate data in an efficient way. These topics are fundamental to your future study of computer science, as they provide you with the foundation of knowledge required to create com- plex and reliable software. Whether you are interested in designing video games or software for robotic- controlled surgery, the study of data structures is vital to your success. Even if you do not study all of the topics in this book now, you are likely to encounter them later. I hope that you will enjoy reading the book, and that it will serve as a useful reference tool for your future courses.

After looking over this preface, you should read the Introduction. There you will quickly see what this book is about and what you need to know about Java before you begin. Appendices A through G review Java basics, classes, inheritance, exceptions, files, and javadoc comments. Note that inside the front and back cov- ers you will find Java’s reserved words, its primitive data types, the precedence of its operators, and a list of Unicode characters.

Please be sure to browse the rest of this preface to see the features that will help you in your studies.

A N

ot e

to S

tu de

nt s

Organization and Structure

This book’s organization, sequencing, and pace of topic coverage make learning and teaching easier by focusing your attention on one concept at a time, by providing flexibility in the order in which you can cover topics, and by clearly distinguishing between the specification and implementation of abstract data types, or ADTs. To accomplish these goals, I have organized the material into 30 chapters, composed of small, numbered segments that deal with one concept at a time. Each chapter focuses on either the specifi- cation and use of an ADT or its various implementations. You can choose to cover the specification of an ADT followed by its implementations, or you can treat the specification and use of several ADTs before you consider any implementation issues. The book’s organization makes it easy for you to choose the topic order that you prefer.

Table of Contents at a Glance

The following list of chapter titles shows the overall composition of the book. A further chapter-by-chapter description appears later. Note that highlighted sections are available online.

Introduction 21. Introducing Hashing 1. Bags 22. Hashing as a Dictionary Implementation 2. Bag Implementations That Use Arrays 23. Trees 3. A Bag Implementation That Links Data 24. Tree Implementations 4. The Efficiency of Algorithms 25. A Binary Search Tree Implementation 5. Stacks 26. A Heap Implementation 6. Stack Implementations 27. Balanced Search Trees 7. Recursion 28. Graphs 8. An Introduction to Sorting 29. Graph Implementations 9. Faster Sorting Methods 30. Mutable, Immutable, and Cloneable Objects 10. Queues, Deques, and Priority Queues 11. Queue, Deque, and Priority Queue Implementations Appendices 12. Lists A. Java Essentials 13. List Implementations That Use Arrays B. Java Classes 14. A List Implementation That Links Data C. Creating Classes from Other Classes 15. Iterators D. Designing Classes 16. Sorted Lists E. Handling Exceptions 17. Inheritance and Lists F. File Input and Output 18. Searching G. Documentation and Programming Style 19. Dictionaries Glossary 20. Dictionary Implementations Index

B ri

ef T

ab le

o f C

on te

nt s

v

vi

What’s New?

Based on comments from readers and reviewers, I have reorganized some of the material. Many students are familiar with stacks and queues, and so the coverage of these data organizations is much earlier in this edition. Moreover, the reorganization makes the difficult topic of linked data more accessible to students. Adding or removing the first node in a chain of linked nodes is the easiest operation. By introducing the bag, the book uses these simple operations on a linked chain in the bag’s implementation. That data collec- tion is followed by the stack, a more useful organization that has the same simple chain in one of its defini- tions. Queue implementations provide the opportunity to discuss adding and removing the last node in a chain. Finally, the treatment of lists looks at the more involved operations of adding and removing a node that lies between existing nodes.

You will notice that algorithm efficiency—including improved motivation—recursion, and sorting also are covered earlier in this edition than in the previous one. To maintain the focus on data structures, I have moved the first three chapters—Java Classes, Creating Classes from Other Classes, and Designing Classes— to the appendices. The presentation now moves from the introduction immediately to the first data collection, the bag. However, readers who need to study Java classes before embarking on the main topic of this book will find the original coverage intact in the appendices.

Finally, I have added some new features. Extensive examples are presented in the form of “A Problem Solved,” in which a problem is posed and its solution is discussed and implemented. An occasional “Design Decision” explores various design choices of a solution. These two new elements help students to think about important aspects of program design and to consider concepts in a situational context. Another new feature is the availability online of over 60 VideoNotes that provide additional instruction in a more dynamic form than a static textbook. The Notes, Programming Tips, and Questions—with answers—that were featured in the previous edition have been retained. And you will find an introduction to the interface Deque and the class ArrayDeque, as well as additional programming projects.

Here is a summary of what is new:

• Earlier introduction of abstract data types, resizable arrays, and linked data. • More gradual coverage of linked data. • Earlier coverage of algorithm efficiency, stacks, recursion, sorting, and queues. • Better motivation of the need for algorithm efficiency. • Chapters 1 through 3—Bags, Bag Implementations That Use Arrays, and A Bag Implementation That

Links Data—introduce and implement the ADT bag. • New elements, including A Problem Solved and Design Decision. • Review of Java classes that appeared in the initial chapters of the second edition is now in the appendices. • VideoNotes—short instructional tutorials—reinforce key concepts presented in the book. • Coverage of the standard interface Deque and the class ArrayDeque. • Additional Programming Projects. • Answers to Self-Test Questions appear at the end of each chapter instead of an appendix.

N ew

to T

hi s E

di tio

n

N ew

to th

is E

di tio

n

Features to Enhance Learning

Each chapter begins with a table of contents, a list of prerequisite chapters or appendices that students should have read, and the learning objectives for the material to be covered. Other pedagogical elements appear throughout the book, as follows:

Notes Important ideas are presented or summarized in highlighted paragraphs and are meant to be read in line with the surrounding text.

Programming Tips Suggestions to improve or facilitate programming are featured as soon as they become relevant.

Examples Numerous examples illuminate new concepts.

A Problem Solved Large examples are presented in the form of “A Problem Solved,” in which a problem is posed and its solution is discussed, designed, and implemented.

Design Decisions To give readers insight into the design choices that one could make when formulating a solution, “Design Decision” elements lay out such options, along with the ration- ale behind the choice made for a particular example. These discussions are often in the context of one of the A Problem Solved examples.

Self-Test Questions Questions are posed throughout each chapter, integrated within the text, that reinforce the concept just presented. These “self-test” questions help readers to understand the material, since answering them requires pause and reflection. Solutions to these questions are provided at the end of each chapter.

VideoNotes Online tutorials are a Pearson feature that provides visual and audio support to the presentation given throughout the book. They offer students another way to recap and reinforce key concepts. VideoNotes allow for self-paced instruction with easy navigation, including the ability to select, play, rewind, fast-forward, and stop within each video. Unique VideoNote icons appear throughout this book whenever a video is available for a particular concept or problem. A detailed list of the VideoNotes for this text and their associated loca- tions in the book can be found on page xxiv. VideoNotes are free with the purchase of a new textbook. To purchase access to VideoNotes, please go to

pearsonhighered.com/carrano

Exercises and Programming Projects Further practice is available by solving the exercises and programming projects at the end of each chapter. Unfortunately, we cannot give readers the answers to these exercises and programming projects, even if they are not enrolled in a class. Only instructors who adopt the book can receive selected answers from the publisher. For help with these exercises and projects, you will have to contact your instructor.

VideoNote

Pe da

go gi

ca l E

le m

en ts

vii

viii

Accessing Instructor and Student Resource Materials

The following items are available on the publisher’s website at pearsonhighered.com/carrano: • Java code as it appears in the book • A link to any misprints that have been discovered since the book was published • Links to additional online content, which is described next

Instructor Resources The following protected material is available to instructors who adopt this book by logging onto Pearson’s Instructor Resource Center, accessible from pearsonhighered.com/carrano:

• PowerPoint lecture slides • Instructor solutions manual • Figures from the book

Additionally, instructors can access the book’s Companion Website for the following online premium con- tent, also accessible from pearsonhighered.com/carrano:

• Instructional VideoNotes • Chapter 30 • A glossary of terms • Exercises and projects for Appendices B, C, and D

Please contact your Pearson sales representative for an instructor access code. Contact information is avail- able at pearsonhighered.com/replocator.

Student Resources The following material is available to students by logging onto the Companion Website accessible from pearsonhighered.com/carrano:

• Instructional VideoNotes • Chapter 30 • A glossary of terms • Exercises and projects for Appendices B, C, and D

Students must use the access card located in the front of the book to register for and then enter the Com- panion Website. Students without an access code can purchase access from the Companion Website by following the instructions listed there.

Note that the Java Class Library is available at download.oracle.com/javase/7/docs/api/.

R es

ou rc

es

Chapter Overview

Readers of this book should have completed a programming course, preferably in Java. The appendices cover the essentials of Java that we assume readers will know. You can use these appendices as a review or as the basis for making the transition to Java from another programming language. The book itself begins with the Introduction, which sets the stage for the data organizations that we will study.

• Chapters 1 through 3: We introduce the bag as an abstract data type (ADT). By dividing the material across several chapters, we clearly separate the specification, use, and implementation of the bag. For example, Chapter 1 specifies the bag and provides several examples of its use. Chapter 2 covers imple- mentations that use arrays and vectors, while Chapter 3 introduces chains of linked nodes and uses one in the definition of a class of bags.

In a similar fashion, we separate specification from implementation throughout the book when we discuss various other ADTs. You can choose to cover the chapters that specify and use the ADTs and then later cover the chapters that implement them. Or you can cover the chapters as they appear, imple- menting each ADT right after studying its specification and use. A list of chapter prerequisites appears later in this preface to help you plan your path through the book.

Chapter 2 does more than simply implement the ADT bag. It shows how to approach the imple- mentation of a class by initially focusing on core methods. When defining a class, it is often useful to implement and test these core methods first and to leave definitions of the other methods for later.

• Chapter 4: Here we introduce the complexity of algorithms, a topic that we integrate into future chapters.

• Chapters 5 and 6: Chapter 5 discusses stacks, giving examples of their use, and Chapter 6 implements the stack using an array, a vector, and a chain.

• Chapters 7 through 9: Next, we present recursion as a problem-solving tool and its relationship to stacks. Recursion, along with algorithm efficiency, is a topic that is revisited throughout the book. For example, Chapters 8 and 9 discuss various sorting techniques and their relative complexities. We con- sider both iterative and recursive versions of these algorithms.

• Chapters 10 and 11: Chapter 10 discusses queues, deques, and priority queues, and Chapter 11 consid- ers their implementations. It is in this latter chapter that we introduce circularly linked and doubly linked chains.

• Chapters 12, 13, and 14: The next three chapters introduce the ADT list. We discuss this collection abstractly and then implement it by using an array, a vector, and finally a chain of linked nodes.

• Chapter 15: Next, we discuss iterators in the context of a list. This chapter considers and imple- ments Java’s iterator interfaces Iterator and ListIterator. The chapter also introduces the inter- face Iterable.

• Chapters 16 and 17: Continuing the discussion of a list, Chapter 16 introduces the sorted list, looking at two possible implementations and their efficiencies. Chapter 17 shows how to use the list as a super- class for the sorted list and discusses the general design of a superclass.

• Chapter 18: We then examine some strategies for searching an array or a chain in the context of a list or a sorted list. This discussion is a good basis for the sequence of chapters that follows.

• Chapters 19 through 22: Chapter 19 covers the specification and use of the ADT dictionary. Chapter 20 presents implementations of the dictionary that are linked or that use arrays. Chapter 21 introduces hash- ing, and Chapter 22 uses it as a dictionary implementation.

• Chapters 23 through 27: Chapter 23 discusses trees and their possible uses. Included among the sev- eral examples of trees is an introduction to the binary search tree and the heap. Chapter 24 considers implementations of the binary tree and the general tree, and Chapter 25 focuses on the implementation of the binary search tree. Chapter 26 shows how to use an array to implement the heap. Chapter 27

D et

ai le

d C

on te

nt D

es cr

ip tio

n

ix

x

introduces balanced search trees. Included in this chapter are the AVL, 2-3, 2-4, and red-black trees, as well as B-trees.

• Chapters 28 and 29: Next, we discuss graphs and look at several applications and two implementations. • Chapter 30: The final chapter expands on the notion of mutable objects and immutable objects, and

introduces cloning. If a client can maintain a reference to the data within an ADT, it can change that data without using the class’s public methods, if the data is mutable. We consider steps that you can take to prevent the client from doing so.

• Appendices A through G: The appendices provide supplemental coverage of Java. As we mentioned earlier, Appendix A reviews Java up to but not including classes. However, this appendix also covers the Scanner class, enumerations, boxing and unboxing, and the for-each loop. Appendix B discusses Java classes, Appendix C expands this topic by looking at composition and inheritance, and Appendix D focuses on class design. Appendix E covers exception handling, and Appendix F discusses files. Appendix G considers pro- gramming style and comments. It introduces javadoc comments and defines the tags that we use in this book.

Acknowledgments My sincere appreciation and thanks go to the following reviewers for carefully reading the previous edition and making candid comments and suggestions that greatly improved the work.

Steven Andrianoff—St. Bonaventure University Brent Baas—LeTourneau University Timothy Henry—University of Rhode Island Ken Martin—University of North Florida Bill Siever—Northwest Missouri State University Lydia Sinapova—Simpson College Lubomir Stanchev—Indiana University Judy Walters—North Central College Xiaohui Yuan—University of North Texas

Special thanks go to my support team during the lengthy process of revising this book. My editor, Tracy Dunkelberger, gave me her constant enthusiasm, encouragement, wisdom, and guidance. Melinda Haggerty and Allison Michael coordinated the review process, and Stephanie Sellinger oversaw the development of the book and its supplements. My long-time copy editor, Rebecca Pepper, ensured that my presentation is clear, correct, and grammatical. Jeff Holcomb, Bob Engelhardt, and Louise Capulli directed the production of the book. This team was there for me whenever I needed them at a moment’s notice. Thank you so much!

My gratitude for the previously mentioned people does not diminish my appreciation for the help pro- vided by many others. Tim Henry, my colleague at URI, created over 60 VideoNotes that provide extra instruction for every chapter of the book. Steve Armstrong produced the lecture slides for this edition and pre- vious editions of the book. Thank you again to the reviewers of the first two editions of the book:

Reviewers for the second edition: Harold Anderson—Marist College Razvan Andonie—Central Washington University Tom Blough—Rensselaer Polytechnic Institute

A ck

no w

le dg

m en

ts

Chris Brooks—University of San Francisco Adrienne Decker—University at Buffalo, SUNY Henry Etlinger—Rochester Institute of Technology Derek Harter—Texas A&M University Timothy Henry—University of Rhode Island Robert Holloway—University of Wisconsin, Madison Charles Hoot—Oklahoma City University Teresa Leyk—Texas A&M University Robert McGlinn—Southern Illinois University, Carbondale Edward Medvid—Marymount University Charles Metzler—City College of San Francisco Daniel Zeng—University of Arizona

Reviewers for the first edition: David Boyd—Valdosta State University Dennis Brylow—Purdue University Michael Croswell—Industry trainer/consultant Matthew Dickerson—Middlebury College Robert Holloway—University of Wisconsin, Madison John Motil—California State University, Northridge Bina Ramamurthy—University at Buffalo, SUNY David Surma—Valparaiso University

I continue to appreciate the many others who helped during previous editions. They include Alan Apt, James Blanding, Lianne Dunn, Mike Giacobbe, Toni Holm, Charles Hoot, Brian Jepson, Rose Kernan, Chris- tianna Lee, Patrick Lindner, John Lovell, Vince O’Brien, Patty Roy, Walt Savitch, Ben Schomp, Heather Scott, Carole Snyder, Chirag Thakkar, Camille Trentacoste, Nate Walker, and Xiaohong Zhu.

Finally, I thank my family and friends—Doug, Ted, Vandee, Nancy, Sue, Tom, Maybeth, Marge, and Lorraine—for giving me a life away from computers.

Thank you, everyone, for your expertise and good cheer. Frank M. Carrano

A ck

no w

le dg

m en

ts

xi

This page intentionally left blank

xiii

Ta bl

e of

C on

te nt

sContents Introduction 1

Chapter 1 Bags 5 The Bag 6

A Bag’s Behaviors 6 Specifying a Bag 7

An Interface 13 Using the ADT Bag 15 Using an ADT Is Like Using a Vending Machine 20 Java Class Library: The Interface Set 21

Chapter 2 Bag Implementations That Use Arrays 27 Using a Fixed-Size Array to Implement the ADT Bag 28

An Analogy 28 A Group of Core Methods 29 Implementing the Core Methods 30 Testing the Core Methods 37 Implementing More Methods 40 Methods That Remove Entries 42

Using Array Resizing to Implement the ADT Bag 50 Resizing an Array 50 A New Implementation of a Bag 53

The Pros and Cons of Using an Array to Implement the ADT Bag 55

Chapter 3 A Bag Implementation That Links Data 61 Linked Data 62

Forming a Chain by Adding to Its Beginning 63 A Linked Implementation of the ADT Bag 65

The Private Class Node 65 An Outline of the Class LinkedBag 66 Defining Some Core Methods 67 Testing the Core Methods 71 The Method getFrequencyOf 72 The Method contains 73

Removing an Item from a Linked Chain 74 The Methods remove and clear 75

A Class Node That Has Set and Get Methods 78 The Pros and Cons of Using a Chain to Implement the ADT Bag 81

Chapter 4 The Efficiency of Algorithms 87 Motivation 88 Measuring an Algorithm’s Efficiency 89

Counting Basic Operations 91 Best, Worst, and Average Cases 93

Big Oh Notation 94 The Complexities of Program Constructs 97

Picturing Efficiency 98 The Efficiency of Implementations of the ADT Bag 102

An Array-Based Implementation 102 A Linked Implementation 103 Comparing the Implementations 104

xiv

Ta bl

e of

C on

te nt

s Chapter 5 Stacks 113 Specifications of the ADT Stack 114 Using a Stack to Process Algebraic Expressions 118

A Problem Solved: Checking for Balanced Delimiters in an Infix Algebraic Expression 119

A Problem Solved: Transforming an Infix Expression to a Postfix Expression 123

A Problem Solved: Evaluating Postfix Expressions 128 A Problem Solved: Evaluating Infix Expressions 130

The Program Stack 132 Java Class Library: The Class Stack 133

Chapter 6 Stack Implementations 141 A Linked Implementation 141 An Array-Based Implementation 145 A Vector-Based Implementation 149

Java Class Library: The Class Vector 150 Using a Vector to Implement the ADT Stack 150

Chapter 7 Recursion 157 What Is Recursion? 158 Tracing a Recursive Method 162 Recursive Methods That Return a Value 166 Recursively Processing an Array 168 Recursively Processing a Linked Chain 171 The Time Efficiency of Recursive Methods 172

The Time Efficiency of countDown 172 The Time Efficiency of Computing xn 174

A Simple Solution to a Difficult Problem 175 A Poor Solution to a Simple Problem 180 Tail Recursion 182 Indirect Recursion 184 Using a Stack Instead of Recursion 185

Chapter 8 An Introduction to Sorting 195 Organizing Java Methods That Sort an Array 196 Selection Sort 198

Iterative Selection Sort 199 Recursive Selection Sort 201 The Efficiency of Selection Sort 202

Insertion Sort 203 Iterative Insertion Sort 204 Recursive Insertion Sort 206 The Efficiency of Insertion Sort 208 Insertion Sort of a Chain of Linked Nodes 208

Shell Sort 211 The Java Code 213 The Efficiency of Shell Sort 214

Comparing the Algorithms 214

xv

Ta bl

e of

C on

te nt

sChapter 9 Faster Sorting Methods 221 Merge Sort 222

Merging Arrays 222 Recursive Merge Sort 223 The Efficiency of Merge Sort 225 Iterative Merge Sort 227 Merge Sort in the Java Class Library 227

Quick Sort 228 The Efficiency of Quick Sort 228 Creating the Partition 229 Java Code for Quick Sort 232 Quick Sort in the Java Class Library 234

Radix Sort 235 Pseudocode for Radix Sort 236 The Efficiency of Radix Sort 237

Comparing the Algorithms 237

Chapter 10 Queues, Deques, and Priority Queues 245 The ADT Queue 246

A Problem Solved: Simulating a Waiting Line 250 A Problem Solved: Computing the Capital Gain in a Sale of Stock 256 Java Class Library: The Interface Queue 259

The ADT Deque 260 A Problem Solved: Computing the Capital Gain in a Sale of Stock 262 Java Class Library: The Interface Deque 263 Java Class Library: The Class ArrayDeque 264

The ADT Priority Queue 265 A Problem Solved: Tracking Your Assignments 266 Java Class Library: The Class PriorityQueue 268

Chapter 11 Queue, Deque, and Priority Queue Implementations 273 A Linked Implementation of a Queue 274 An Array-Based Implementation of a Queue 278

A Circular Array 278 A Circular Array with One Unused Location 281

A Vector-Based Implementation of a Queue 286 Circular Linked Implementations of a Queue 288

A Two-Part Circular Linked Chain 289 Java Class Library: The Class AbstractQueue 294 A Doubly Linked Implementation of a Deque 295 Possible Implementations of a Priority Queue 299

Chapter 12 Lists 305 Specifications for the ADT List 306 Using the ADT List 312 Java Class Library: The Interface List 316 Java Class Library: The Class ArrayList 316

xvi

Ta bl

e of

C on

te nt

s Chapter 13 List Implementations That Use Arrays 321 Using an Array to Implement the ADT List 322

An Analogy 322 The Java Implementation 324 The Efficiency of Using an Array to Implement the ADT List 331

Using a Vector to Implement the ADT List 332

Chapter 14 A List Implementation That Links Data 339 Operations on a Chain of Linked Nodes 340

Adding a Node at Various Positions 340 Removing a Node from Various Positions 344 The Private Method getNodeAt 345

Beginning the Implementation 346 The Data Fields and Constructor 347 Adding to the End of the List 348 Adding at a Given Position Within the List 349 The Methods isEmpty and toArray 350 Testing the Core Methods 353

Continuing the Implementation 354 A Refined Implementation 356

The Tail Reference 357 The Efficiency of Using a Chain to Implement the ADT List 360 Java Class Library: The Class LinkedList 362

Chapter 15 Iterators 369 What Is an Iterator? 370 The Interface Iterator 371

Using the Interface Iterator 372 A Separate Class Iterator 377 An Inner Class Iterator 381

A Linked Implementation 381 An Array-Based Implementation 385

Why Are Iterator Methods in Their Own Class? 388 The Interface ListIterator 390

Using the Interface ListIterator 393 An Array-Based Implementation of the Interface ListIterator 395

The Inner Class 397 Java Class Library: The Interface Iterable 402

Iterable and for-each loops 403 The Interface List Revisited 403

Chapter 16 Sorted Lists 411 Specifications for the ADT Sorted List 412

Using the ADT Sorted List 415 A Linked Implementation 416

The Method add 417 The Efficiency of the Linked Implementation 424

An Implementation That Uses the ADT List 424 Efficiency Issues 427

xvii

Ta bl

e of

C on

te nt

sChapter 17 Inheritance and Lists 433 Using Inheritance to Implement a Sorted List 434 Designing a Base Class 436

Creating an Abstract Base Class 441 An Efficient Implementation of a Sorted List 443

The Method add 443

Chapter 18 Searching 447 The Problem 448 Searching an Unsorted Array 448

An Iterative Sequential Search of an Unsorted Array 449 A Recursive Sequential Search of an Unsorted Array 450 The Efficiency of a Sequential Search of an Array 452

Searching a Sorted Array 452 A Sequential Search of a Sorted Array 452 A Binary Search of a Sorted Array 453 Java Class Library: The Method binarySearch 458 The Efficiency of a Binary Search of an Array 458

Searching an Unsorted Chain 460 An Iterative Sequential Search of an Unsorted Chain 460 A Recursive Sequential Search of an Unsorted Chain 461 The Efficiency of a Sequential Search of a Chain 462

Searching a Sorted Chain 462 A Sequential Search of a Sorted Chain 462 A Binary Search of a Sorted Chain 462

Choosing a Search Method 463

Chapter 19 Dictionaries 471 Specifications for the ADT Dictionary 472

A Java Interface 476 Iterators 477

Using the ADT Dictionary 478 A Problem Solved: A Directory of Telephone Numbers 479 A Problem Solved: The Frequency of Words 484 A Problem Solved: A Concordance of Words 488

Java Class Library: The Interface Map 490

Chapter 20 Dictionary Implementations 497 Array-Based Implementations 498

An Unsorted Array-Based Dictionary 498 A Sorted Array-Based Dictionary 503

Vector-Based Implementations 508 Linked Implementations 512

An Unsorted Linked Dictionary 514 A Sorted Linked Dictionary 514

Chapter 21 Introducing Hashing 523 What Is Hashing? 524 Hash Functions 527

Computing Hash Codes 527 Compressing a Hash Code into an Index for the Hash Table 530

xviii

Ta bl

e of

C on

te nt

s Resolving Collisions 531 Open Addressing with Linear Probing 531 Open Addressing with Quadratic Probing 537 Open Addressing with Double Hashing 537 A Potential Problem with Open Addressing 539 Separate Chaining 539

Chapter 22 Hashing as a Dictionary Implementation 547 The Efficiency of Hashing 548

The Load Factor 548 The Cost of Open Addressing 549 The Cost of Separate Chaining 551

Rehashing 552 Comparing Schemes for Collision Resolution 553 A Dictionary Implementation That Uses Hashing 554

Entries in the Hash Table 554 Data Fields and Constructors 555 The Methods getValue, remove, and add 557 Iterators 562

Java Class Library: The Class HashMap 564 Java Class Library: The Class HashSet 564

Chapter 23 Trees 569 Tree Concepts 570

Hierarchical Organizations 570 Tree Terminology 572

Traversals of a Tree 576 Traversals of a Binary Tree 576 Traversals of a General Tree 579

Java Interfaces for Trees 579 Interfaces for All Trees 580 An Interface for Binary Trees 580

Examples of Binary Trees 582 Expression Trees 582 Decision Trees 584 Binary Search Trees 588 Heaps 590

Examples of General Trees 593 Parse Trees 593 Game Trees 593

Chapter 24 Tree Implementations 603 The Nodes in a Binary Tree 604

An Interface for a Node 605 An Implementation of BinaryNode 606

An Implementation of the ADT Binary Tree 607 Creating a Basic Binary Tree 608 The Method privateSetTree 609 Accessor and Mutator Methods 612 Computing the Height and Counting Nodes 613 Traversals 614

xix

Ta bl

e of

C on

te nt

sAn Implementation of an Expression Tree 619 General Trees 621

A Node for a General Tree 621 Using a Binary Tree to Represent a General Tree 622

Chapter 25 A Binary Search Tree Implementation 629 Getting Started 630

An Interface for the Binary Search Tree 631 Duplicate Entries 633 Beginning the Class Definition 634

Searching and Retrieving 635 Traversing 637 Adding an Entry 637

A Recursive Implementation 638 An Iterative Implementation 642

Removing an Entry 643 Removing an Entry Whose Node Is a Leaf 644 Removing an Entry Whose Node Has One Child 644 Removing an Entry Whose Node Has Two Children 645 Removing an Entry in the Root 648 A Recursive Implementation 649 An Iterative Implementation 652

The Efficiency of Operations 656 The Importance of Balance 657 The Order in Which Nodes Are Added 658

An Implementation of the ADT Dictionary 659

Chapter 26 A Heap Implementation 673 Reprise: The ADT Heap 674 Using an Array to Represent a Heap 674 Adding an Entry 677 Removing the Root 680 Creating a Heap 683 Heap Sort 686

Chapter 27 Balanced Search Trees 695 AVL Trees 696

Single Rotations 696 Double Rotations 699 Implementation Details 703

2-3 Trees 707 Searching a 2-3 Tree 708 Adding Entries to a 2-3 Tree 709 Splitting Nodes During Addition 711

2-4 Trees 712 Adding Entries to a 2-4 Tree 713 Comparing AVL, 2-3, and 2-4 Trees 715

Red-Black Trees 716 Properties of a Red-Black Tree 717 Adding Entries to a Red-Black Tree 718 Java Class Library: The Class TreeMap 724

B-Trees 724