Isei

Robert Lafore

Data Structures & Algorithms in Java
Second Edition

800 East 96th Street, Indianapolis, Indiana 46240

Data Structures and Algorithms in Java, Second Edition
Copyright © 2003 by Sams Publishing All rights reserved. No part of this book shall be reproduced, stored in a retrieval system, or transmitted by any means, electronic, mechanical, photocopying, recording, orotherwise, without written permission from the publisher. No patent liability is assumed with respect to the use of the information contained herein. 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 damages resulting from the use of the information contained herein.International Standard Book Number: 0-672-32453-9 Library of Congress Catalog Card Number: 2002106907 Printed in the United States of America First Printing: December 2002 05 04 03 4 3

Executive Editor Michael Stephens Acquisitions Editor Carol Ackerman Development Editor Songlin Qiu Managing Editor Charlotte Clapp Project Editor Matt Purcell Copy Editor Chuck Hutchinson Indexer Johnna DinseProofreader

Trademarks
All terms mentioned in this book that are known to be trademarks or service marks have been appropriately capitalized. Sams Publishing cannot attest to the accuracy of this information. Use of a term in this book should not be regarded as affecting the validity of any trademark or service mark.

Cindy Long Technical Editor Mike Kopack Team Coordinator Lynne WilliamsMultimedia Developer Dan Scherf Interior Designer Gary Adair Cover Designer Alan Clements Production Plan-it Publishing

Warning and Disclaimer
Every effort has been made to make this book as complete and as accurate as possible, but no warranty or fitness is implied. The information provided is on an “as is” basis. The author and the publisher shall have neither liability nor responsibility to anyperson or entity with respect to any loss or damages arising from the information contained in this book.

Bulk Sales
Sams Publishing offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales. For more information, please contact U.S. Corporate and Government Sales 1-800-382-3419 corpsales@pearsontechgroup.com For sales outside of the U.S., please contactInternational Sales 1-317-428-3341 international@pearsontechgroup.com

Contents at a Glance
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Simple Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 77 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Recursion . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 Advanced Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....