WIXLIB

Robert LaforeData Structures& Algorithmsin JavaSecond Edition800 East 96th Street, Indianapolis, Indiana 46240

Data Structures and Algorithms in Java,Second EditionExecutive EditorCopyright 2003 by Sams PublishingAcquisitions EditorAll rights reserved. No part of this book shall be reproduced, storedin a retrieval system, or transmitted by any means, electronic,mechanical, photocopying, recording, or otherwise, withoutwritten permission from the publisher. No patent liability isassumed with respect to the use of the information containedherein. Although every precaution has been taken in the preparation of this book, the publisher and author assume no responsibility for errors or omissions. Nor is any liability assumed for damagesresulting from the use of the information contained herein.Carol AckermanMichael StephensDevelopment EditorSonglin QiuManaging EditorCharlotte ClappProject EditorMatt PurcellInternational Standard Book Number: 0-672-32453-9Library of Congress Catalog Card Number: 2002106907Copy EditorChuck HutchinsonPrinted in the United States of AmericaFirst Printing: December 20020504034IndexerJohnna Dinse3ProofreaderTrademarksAll terms mentioned in this book that are known to be trademarksor service marks have been appropriately capitalized. SamsPublishing cannot attest to the accuracy of this information. Use ofa term in this book should not be regarded as affecting the validityof any trademark or service mark.Warning and DisclaimerEvery effort has been made to make this book as complete and asaccurate as possible, but no warranty or fitness is implied. Theinformation provided is on an “as is” basis. The author and thepublisher shall have neither liability nor responsibility to anyperson or entity with respect to any loss or damages arising fromthe information contained in this book.Cindy LongTechnical EditorMike KopackTeam CoordinatorLynne WilliamsMultimedia DeveloperDan ScherfInterior DesignerGary AdairCover DesignerAlan ClementsBulk SalesProductionSams Publishing offers excellent discounts on this book whenordered in quantity for bulk purchases or special sales. For moreinformation, please contactPlan-it PublishingU.S. Corporate and Government or sales outside of the U.S., please contactInternational com

Contents at a GlanceIntroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333Simple Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1796Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2517Advanced Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3158Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3659Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429102-3-4 Trees and External Storage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46311Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51912Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57913Graphs14Weighted Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66915When to Use What . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615AppendixesARunning the Workshop Applets and Example Programs . . . . . . . . . . . . . . . . . . . . 729BFurther ReadingCAnswers to Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749

Table of ContentsIntroduction1What’s New in the Second Edition .1Additional Topics .1End-of-Chapter Questions .2Experiments .2Programming Projects .2What This Book Is About .2What’s Different About This Book .3Easy to Understand .3Workshop Applets .4Java Example Code .5Who This Book Is For .5What You Need to Know Before You Read This Book .5The Software You Need to Use This Book .6How This Book Is Organized .6Enjoy Yourself! .81Overview9What Are Data Structures and Algorithms Good For? .9Real-World Data Storage .10Programmer’s Tools .11Real-World Modeling .11Overview of Data Structures .11Overview of Algorithms .12Some Definitions .13Database .13Record .13Field .13Key .14Object-Oriented Programming .14Problems with Procedural Languages .14Objects in a Nutshell .15A Runnable Object-Oriented Program .18Inheritance and Polymorphism .21Software Engineering .21

Java for C Programmers .22No Pointers .22Overloaded Operators .25Primitive Variable Types .25Input/Output .26Java Library Data Structures .29Summary .30Questions .302Arrays33The Array Workshop Applet .33Insertion .35Searching .36Deletion .36The Duplicates Issue .37Not Too Swift .39The Basics of Arrays in Java .39Creating an Array .40Accessing Array Elements .40Initialization .41An Array Example .41Dividing a Program into Classes .44Classes LowArray and LowArrayApp .46Class Interfaces .46Not So Convenient .47Who’s Responsible for What? .48The highArray.java Example .48The User’s Life Made Easier .52Abstraction .52The Ordered Workshop Applet .52Linear Search .53Binary Search .54Java Code for an Ordered Array .56Binary Search with the find() Method .56The OrdArray Class .58Advantages of Ordered Arrays .61Logarithms .62The Equation .63The Opposite of Raising Two to a Power .64

viData Structures & Algorithms in Java, Second EditionStoring Objects .64The Person Class .65The classDataArray.java Program .65Big O Notation .70Insertion in an Unordered Array: Constant .70Linear Search: Proportional to N .70Binary Search: Proportional to log(N) .71Don’t Need the Constant .71Why Not Use Arrays for Everything? .72Summary .73Questions .74Experiments .75Programming Projects .763Simple Sorting77How Would You Do It? .78Bubble Sort .79Bubble Sort on the Baseball Players .79The BubbleSort Workshop Applet .81Java Code for a Bubble Sort .85Invariants .88Efficiency of the Bubble Sort .88Selection Sort .89Selection Sort on the Baseball Players .89The SelectSort Workshop Applet .90Java Code for Selection Sort .92Invariant .95Efficiency of the Selection Sort .95Insertion Sort .95Insertion Sort on the Baseball Players .95The InsertSort Workshop Applet .97Java Code for Insertion Sort .99Invariants in the Insertion Sort .103Efficiency of the Insertion Sort .103Sorting Objects .103Java Code for Sorting Objects .104Lexicographical Comparisons .107Stability .107Comparing the Simple Sorts .108Summary .108

ContentsQuestions .109Experiments .111Programming Projects .1124Stacks and Queues115A Different Kind of Structure .115Programmer’s Tools .115Restricted Access .116More Abstract .116Stacks .116The Postal Analogy .117The Stack Workshop Applet .118Java Code for a Stack .120Stack Example 1: Reversing a Word .124Stack Example 2: Delimiter Matching .127Efficiency of Stacks .132Queues .132The Queue Workshop Applet .133A Circular Queue .136Java Code for a Queue .137Efficiency of Queues .142Deques .143Priority Queues .143The PriorityQ Workshop Applet .144Java Code for a Priority Queue .147Efficiency of Priority Queues .149Parsing Arithmetic Expressions .149Postfix Notation .150Translating Infix to Postfix .151Evaluating Postfix Expressions .167Summary .173Questions .174Experiments .176Programming Projects .1765Linked Lists179Links .179References and Basic Types .180Relationship, Not Position .182vii

viiiData Structures & Algorithms in Java, Second EditionThe LinkList Workshop Applet .183The Insert Button .183The Find Button .184The Delete Button .184A Simple Linked List .185The Link Class .185The LinkList Class .186The insertFirst() Method .187The deleteFirst() Method .188The displayList() Method .189The linkList.java Program .190Finding and Deleting Specified Links .193The find() Method .196The delete() Method .196Other Methods .197Double-Ended Lists .198Linked-List Efficiency .202Abstract Data Types .202A Stack Implemented by a Linked List .203A Queue Implemented by a Linked List .206Data Types and Abstraction .210ADT Lists .211ADTs as a Design Tool .212Sorted Lists .212Java Code to Insert an Item in a Sorted List .213The sortedList.java Program .215Efficiency of Sorted Linked Lists .218List Insertion Sort .218Doubly Linked Lists .221Traversal .222Insertion .223Deletion .225The doublyLinked.java Program .226Doubly Linked List as Basis for Deques .231Iterators .231A Reference in the List Itself? .232An Iterator Class .232Additional Iterator Features .233Iterator Methods .234The interIterator.java Program .235

ContentsWhere Does the Iterator Point? .242The atEnd() Method .242Iterative Operations .243Other Methods .244Summary .244Questions .245Experiments .247Programming Projects .2476Recursion251Triangular Numbers .251Finding the nth Term Using a Loop .252Finding the nth Term Using Recursion .253The triangle.java Program .255What’s Really Happening? .257Characteristics of Recursive Methods .259Is Recursion Efficient? .259Mathematical Induction .259Factorials .260Anagrams .262A Recursive Binary Search .268Recursion Replaces the Loop .268Divide-and-Conquer Algorithms .272The Towers of Hanoi .273The Towers Workshop Applet .274Moving Subtrees .275The Recursive Algorithm .276The towers.java Program .277mergesort .279Merging Two Sorted Arrays .280Sorting by Merging .283The MergeSort Workshop Applet .285The mergeSort.java Program .287Efficiency of the mergesort .291Eliminating Recursion .294Recursion and Stacks .294Simulating a Recursive Method .294What Does This Prove? .301Some Interesting Recursive Applications .303Raising a Number to a Power .303ix