6.20 warm up online shopping cart java

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

xx

Ta bl

e of

C on

te nt

s Chapter 28 Graphs 731 Some Examples and Terminology 732

Road Maps 732 Airline Routes 735 Mazes 736 Course Prerequisites 736 Trees 737

Traversals 737 Breadth-First Traversal 738 Depth-First Traversal 740

Topological Order 741 Paths 744

Finding a Path 744 The Shortest Path in an Unweighted Graph 744 The Shortest Path in a Weighted Graph 747

Java Interfaces for the ADT Graph 751

Chapter 29 Graph Implementations 761 An Overview of Two Implementations 762

The Adjacency Matrix 762 The Adjacency List 763

Vertices and Edges 764 Specifying the Class Vertex 765 The Inner Class Edge 767 Implementing the Class Vertex 768

An Implementation of the ADT Graph 772 Basic Operations 772 Graph Algorithms 775

Chapter 30 Mutable, Immutable, and Cloneable Objects Online Mutable and Immutable Objects 30-2

Creating a Read-Only Class 30-4 Companion Classes 30-6

Cloneable Objects 30-8 Cloning an Array 30-14 Cloning a Chain 30-16 A Sorted List of Clones 30-19

Appendices A. Java Essentials A-1 Introduction A-2

Applications and Applets A-2 Objects and Classes A-3 A First Java Application Program A-3

Java Basics A-5 Identifiers A-5 Reserved Words A-6 Variables A-6 Primitive Types A-7 Constants A-7

xx

Ta bl

e of

C on

te nt

s

xxi

Ta bl

e of

C on

te nt

sAssignment Statements A-8 Assignment Compatibilities A-9 Type Casting A-9 Arithmetic Operators and Expressions A-10 Parentheses and Precedence Rules A-11 Increment and Decrement Operators A-12 Special Assignment Operators A-13 Named Constants A-14 The Class Math A-15

Simple Input and Output Using the Keyboard and Screen A-15 Screen Output A-15 Keyboard Input Using the Class Scanner A-17

The if-else Statement A-19 Boolean Expressions A-20 Nested Statements A-23 Multiway if-else Statements A-24 The Conditional Operator (Optional) A-25

The switch Statement A-26 Enumerations A-28 Scope A-30 Loops A-30

The while Statement A-31 The for Statement A-32 The do-while Statement A-34 Additional Loop Information A-35

The Class String A-36 Characters Within Strings A-36 Concatenation of Strings A-37 String Methods A-38

The Class StringBuilder A-40 Using Scanner to Extract Pieces of a String A-42 Arrays A-44

Array Parameters and Returned Values A-46 Initializing Arrays A-47 Array Index Out of Bounds A-47 Use of = and == with Arrays A-47 Arrays and the For-Each Loop A-48 Multidimensional Arrays A-49

Wrapper Classes A-51

B. Java Classes B-1 Objects and Classes B-1 Using the Methods in a Java Class B-3

References and Aliases B-4 Defining a Java Class B-5

Method Definitions B-7 Arguments and Parameters B-9 Passing Arguments B-9 A Definition of the Class Name B-13

xxii

Ta bl

e of

C on

te nt

s Constructors B-15 The Method toString B-17 Methods That Call Other Methods B-17 Methods That Return an Instance of Their Class B-19 Static Fields and Methods B-19 Overloading Methods B-21

Enumeration as a Class B-22 Packages B-25

The Java Class Library B-25 Generic Data Types B-26

C. Creating Classes from Other Classes C-1 Composition C-2

Adapters C-4 Inheritance C-5

Invoking Constructors from Within Constructors C-9 Private Fields and Methods of the Superclass C-10 Protected Access C-11 Overriding and Overloading Methods C-11 Multiple Inheritance C-16

Type Compatibility and Superclasses C-16 The Class Object C-18 Abstract Classes and Methods C-19

Polymorphism C-21

D. Designing Classes D-1 Encapsulation D-2 Specifying Methods D-4

Comments D-4 Preconditions and Postconditions D-5 Assertions D-6

Java Interfaces D-7 Writing an Interface D-8 Implementing an Interface D-10 An Interface as a Data Type D-11 Generic Types Within an Interface D-12 Extending an Interface D-14 Interfaces Versus Abstract Classes D-15 Named Constants Within an Interface D-17

Choosing Classes D-18 Identifying Classes D-20 CRC Cards D-20 The Unified Modeling Language D-21

Reusing Classes D-23

E. Handling Exceptions E-1 The Basics E-2 Handling an Exception E-4

Postpone Handling: The throws Clause E-4 Handle It Now: The try-catch Blocks E-5 Multiple catch Blocks E-6

xxiii

Ta bl

e of

C on

te nt

sThrowing an Exception E-8 Programmer-Defined Exception Classes E-9 Inheritance and Exceptions E-14 The finally Block E-15

F. File Input and Output F-1 Preliminaries F-2

Why Files? F-2 Streams F-2 The Kinds of Files F-3 File Names F-3

Text Files F-3 Creating a Text File F-3 Reading a Text File F-8 Changing Existing Data in a Text File F-12 Defining a Method to Open a Stream F-13

Binary Files F-13 Creating a Binary File of Primitive Data F-14 Reading a Binary File of Primitive Data F-18 Strings in a Binary File F-20 Object Serialization F-23

G. Documentation and Programming Style G-1 Naming Variables and Classes G-1 Indenting G-2 Comments G-2

Single-Line Comments G-3 Comment Blocks G-3 When to Write Comments G-3 Java Documentation Comments G-3 Running javadoc G-5

Glossary Online Index I-1

xxiv

VideoNotes Directory This table lists the VideoNotes that are available online. The page numbers indicate where in the book each VideoNote has relevance.

Chapter 1 Bags Designing an ADT 7 Designing a test for an ADT 16

Chapter 2 Bag Implementations That Use Arrays An array-based bag 29 A resizable bag 53

Chapter 3 A Bag Implementation That Links Data Linked data 62 Beginning the class LinkedBag 67 Completing the class LinkedBag 72

Chapter 4 The Efficiency of Algorithms Measuring efficiency 89 Comparing ADT bag implementations 102

Chapter 5 Stacks The ADT stack 114 Using the ADT stack 128

Chapter 6 Stack Implementations The class LinkedStack 142 The class ArrayStack 145

Chapter 7 Recursion Introducing recursion 158 Using recursion to solve problems 168

Chapter 8 An Introduction to Sorting Selection sort 198 Insertion sort 203

Chapter 9 Faster Sorting Methods Merge sort 222 Quick sort 228

Chapter 10 Queues, Deques, and Priority Queues The ADT queue 246 The ADTs deque and priority queue 265

Chapter 11 Queue, Deque, and Priority Queue Implementations The class LinkedQueue 274 The class ArrayQueue 281 Other queue implementations 288

Chapter 12 Lists The ADT list 306 Using the ADT list 312

Chapter 13 List Implementations That Use Arrays The class AList 324 Completing the class AList 329

VideoNote

V id

eo N

ot es

xxv

Chapter 14 A List Implementation That Links Data The class LList 348 Completing the class LList 354

Chapter 15 Iterators Iterators and their use 370 Alternative iterator implementations 381

Chapter 16 Sorted Lists The class SortedLinkedList 416 An array-based sorted list 424

Chapter 17 Inheritance and Lists Inheritance and ADT implementations 434 Creating a base class 441

Chapter 18 Searching Searching an array 449 Searching a linked chain 460

Chapter 19 Dictionaries The ADT dictionary 472 Using the ADT dictionary 478

Chapter 20 Dictionary Implementations Array-based dictionaries 498 Linked-chain dictionaries 512

Chapter 21 Introducing Hashing Hashing 524 Resolving collisions 531

Chapter 22 Hashing as a Dictionary Implementation Hashing efficiency 548 Implementing a dictionary 554

Chapter 23 Trees The ADT Tree 576 Using the ADT tree 582

Chapter 24 Tree Implementations Creating a binary tree 608 Binary tree operations 612

Chapter 25 A Binary Search Tree Implementation Creating a binary search tree 634 Binary search tree additions and removals 637

Chapter 26 A Heap Implementation Implementing the ADT heap 674 The heap sort 686

Chapter 27 Balanced Search Trees AVL trees 696 2-3 trees 707 2-4 and red-black trees 713

V id

eo N

ot es

xxvi

Chapter 28 Graphs Graph concepts and terminology 733 Graph operations 738

Chapter 29 Graph Implementations The adjacency matrix 762 Implementing graph operations 772

Chapter 30 Mutable, Immutable, and Cloneable Objects Mutable and immutable objects 30-2 Cloneable objects 30-8

V id

eo N

ot es

xxvii

Chapter Prerequisites Each chapter and appendix assumes that the reader has studied certain previous material. This list indicates those prerequisites. Numbers represent chapter num- bers, and letters reference appendices. You can use this information to plan a path through the book.

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

This page intentionally left blank

Introduction

Look around and you will see ways that people organize things. When you stopped at the store this morning, you went to the back of a line to wait for the cashier. The line organized people chronologically. The first person in the line was the first to be served and to leave the line. Eventually, you reached the front of the line and left the store with a bag containing your purchases. The items in the bag were in no particular order, and some of them were the same.

Do you see a stack of books or a pile of papers on your desk? It’s easy to look at or remove the top item of the stack or to add a new item to the top of the stack. The items in a stack also are organized chronologically, with the item added most recently on top and the item added first on the bottom.

At your desk, you see your to-do list. Each entry in the list has a position that might or might not be important to you. You may have written them either as you thought of them, in their order of importance, or in alphabetical order. You decide the order; the list simply provides places for your entries.

Your dictionary is an alphabetical list of words and their definitions. You search for a word and get its definition. If your dictionary is printed, the alphabetical organization helps you to locate a word quickly. If your dictionary is computerized, its alphabetical organization is hidden, but it still speeds the search.

Speaking of your computer, you have organized your files into folders, or directories. Each folder contains several other folders or files. This type of organization is hierarchical. If you drew a picture of it, you would get something like a family tree or a chart of a company’s internal depart- ments. These data organizations are similar and are called trees.

Finally, notice the road map that you are using to plan your weekend trip. The diagram of roads and towns shows you how to get from one place to another. Often, several ways are possible. One way might be shorter, another faster. The road map has an organization known as a graph.

2 Introduction

Computer programs also need to organize their data. They do so in ways that parallel the examples we just cited. That is, programs can use a list, a stack, a dictionary, and so on. These ways of organizing data are represented by abstract data types. An abstract data type, or ADT, is a spec- ification that describes a data set and the operations on that data. Each ADT specifies what data is stored and what the operations on the data do. Since an ADT does not indicate how to store the data or how to implement the operations, we can talk about ADTs independently of any programming language. In contrast, a data structure is an implementation of an ADT within a pro- gramming language.

A collection is a general term for an ADT that contains a group of objects. Some collections allow duplicate items, some do not. Some collections arrange their contents in a certain order, while others do not. A container is a class that implements a collection. Some people use the terms “container” and “collection” interchangeably.

We might create an ADT bag consisting of an unordered collection that allows duplicates. It is like a grocery bag, a lunch bag, or a bag of potato chips. Suppose you remove one chip from a bag of chips. You don’t know when the chip was placed into the bag. You don’t know whether the bag contains another chip shaped exactly like the one you just removed. But you don’t really care. If you did, you wouldn’t store your chips in a bag!

A bag does not order its contents, but sometimes you do want to order things. ADTs can order their items in a variety of ways. The ADT list, for example, simply numbers its items. A list, then, has a first item, a second item, and so on. Although you can add an item to the end of a list, you can also insert an item at the beginning of the list or between existing items. Doing so renumbers the items after the new item. Additionally, you can remove an item at a particular position within a list.

Examples of everday data organizations

Introduction 3

Thus, the position of an item in the list does not necessarily indicate when it was added. Notice that the list does not decide where an item is placed; you make this decision.

In contrast, the ADTs stack and queue order their items chronologically. When you remove an item from a stack, you remove the one that was added most recently. When you remove an item from a queue, you remove the one that was added the earliest. Thus, a stack is like a pile of books. You can remove the top book or add another book to the top of the pile. A queue is like a line of people. People leave a line from its front and join it at its end.

Some ADTs maintain their entries in sorted order, if the items can be compared. For instance, strings can be organized in alphabetical order. When you add an item to the ADT sorted list, for example, the ADT determines where to place the item in the list. You do not indicate a position for the item, as you would with the ADT list.

The ADT dictionary contains pairs of items, much as a language dictionary contains a word and its definition. In this example, the word serves as a key that is used to locate the entries. Some dictionaries sort their entries and some do not.

The ADT tree organizes its entries according to some hierarchy. For example, in a family tree, people are associated with their children and their parents. The ADT binary search tree has a com- bined hierarchical and sorted organization that makes locating a particular entry easier.

The ADT graph is a generalization of the ADT tree that focuses on the relationship among its entries instead of any hierarchical organization. For example, a road map is a graph that shows the existing roads and distances between towns.

This book shows you how to use and implement these data organizations. Before we begin, you need to know Java. Appendix A reviews the basic statements in Java. Appendix B discusses the basic construction of classes and methods. You can choose to glance at this material, read it carefully, or come back to it as necessary. Appendices C and D also focus on Java, but some or all of the material might be new to you. Appendix C covers techniques, including composition and inheritance, for creating new classes from existing classes. Appendix D discusses how to design classes, specify methods, and write Java interfaces. Using interfaces and writing comments to spec- ify methods are essential to our presentation of ADTs. Appendix E reviews how to handle excep- tions, Appendix F presents reading and writings external files, and Appendix G gives an overview of writing comments suitable for javadoc.

This page intentionally left blank

Chapter

1Bags Contents The Bag

A Bag’s Behaviors Specifying a Bag

An Interface Using the ADT Bag Using an ADT Is Like Using a Vending Machine

Prerequisites Appendix C Creating Classes from Other Classes Appendix D Designing Classes

Objectives After studying this chapter, you should be able to • Describe the concept of an abstract data type (ADT) • Describe the ADT bag • Use the ADT bag in a Java program

This chapter builds on the concepts of encapsulation and data abstraction presented in Appendix D, and it develops the notion of an abstract data type. As you probably know, a data type such as int or double is a group of values and operations on those values that is defined within a specific programming language. In contrast, an abstract data type, or ADT, is a specification for a group of values and the operations on those values that is defined conceptually and independently of any programming language. A data structure is an implementation of an ADT within a programming language.

This chapter also begins to generalize the idea of grouping objects. A collection is an object that groups other objects and provides various services to its client. In particular, a typical collection enables a client to add, remove, retrieve, and query the objects it represents. Various collections exist for different purposes. Their behaviors

6 CHAPTER 1 Bags

are specified abstractly and can differ in purpose according to the collection. Thus, a collection is an abstraction and is an abstract data type. However, an ADT is not necessarily a collection.

To provide an example of a collection and of an abstract data type, we will specify and use the ADT bag. In doing so we will provide a Java interface for our bag. Knowing just this interface, you will be able to use a bag in a Java program. You do not need to know how the entries in the bag are represented or how the bag operations are implemented. Indeed, your program will not depend on these specifics. As you will see, this important program characteristic is what data abstraction is all about.

The Bag

1.1 Imagine a paper bag, a reusable cloth bag, or even a plastic bag. People use bags when they shop, pack a lunch, or eat potato chips. Bags contain things. In everyday language, a bag is a kind of container. In Java, however, a container is an object whose class extends the standard class Container. Such containers are used in graphics programs. Rather than being considered a container, a bag in Java is a kind of collection.

What distinguishes a bag from other collections? A bag doesn’t do much more than contain its items. It doesn’t order them in a particular way, nor does it prevent duplicate items. Most of its behaviors could be performed by other kinds of collections. While describing the behaviors for the collection that we’ll design in this chapter, let’s keep in mind that we are specifying an abstraction inspired by an actual physical bag. For example, a paper bag holds things of various dimensions and shapes in no particular order and without regard for duplicates. Our abstract bag will hold unordered and possibly duplicate objects, but let’s insist that these objects have the same or related types.

A Bag’s Behaviors 1.2 Since a bag contains a finite number of objects, reporting how many objects it contains could be

one of a bag’s behaviors:

Get the number of items currently in the bag

Two related behaviors detect whether a bag is full or empty: See whether the bag is full See whether the bag is empty

1.3 We should be able to add and remove objects: Add a given object to the bag Remove an unspecified object from the bag Remove an occurrence of a particular object from the bag, if possible Remove all objects from the bag

While you hope that the bagger at the grocery store does not toss six cans of soup into a bag on top of your bread and eggs, our add operation does not indicate where in the bag an object should go. Remember that a bag does not order its contents. Likewise, the first remove operation just removes any object it can. This operation is like reaching into a grab bag and pulling something out. On the other hand, the second remove operation looks for a particular item in the bag. If you find it, you take it out. If the bag contains several equal objects that satisfy your search, you remove any one of

Note: A bag is a finite collection of objects in no particular order. A bag can contain dupli- cate items.