Input codes for ralph breaks the maze

Write A JAVA Program

DATA STRUCTURES Abstraction and Design

Using Java THIRD EDITION

ELLIOT B. KOFFMAN Temple University

PAUL A. T. WOLFGANG Temple University

Koffman-ffirs.indd 1 11/3/2015 9:04:31 PM

VICE PRESIDENT & DIRECTOR Laurie Rosatone SENIOR DIRECTOR Don Fowley EXECUTIVE EDITOR Brian Gambrel DEVELOPMENT EDITOR Jennifer Lartz ASSISTANT Jessy Moor PROJECT MANAGER Gladys Soto PROJECT SPECIALIST Nichole Urban PROJECT ASSISTANT Anna Melhorn MARKETING MANAGER Dan Sayre ASSISTANT MARKETING MANAGER Puja Katarawala ASSOCIATE DIRECTOR Kevin Holm SENIOR CONTENT SPECIALIST Nicole Repasky PRODUCTION EDITOR Rajeshkumar Nallusamy PHOTO RESEARCHER Amanda Bustard COVER PHOTO CREDIT © Robert Davies/Shutterstock

This book was set in 10/12 pt SabonLTStd-Roman by SPiGlobal and printed and bound by Lightning Source Inc.

Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/citizenship.

Copyright © 2016, 2010 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permit- ted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authori- zation through payment of the appropriate per‐copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923 (Web site: www.copyright.com). Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030‐5774, (201) 748‐6011, fax (201) 748‐6008, or online at: www.wiley.com/go/permissions.

Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return shipping label are available at: www.wiley.com/go/ returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative.

ISBN: 978-1-119-23914-7 (PBK) ISBN: 978-1-119-22307-8 (EVALC)

Library of Congress Cataloging-in-Publication Data Koffman, Elliot B. [Objects, abstraction, data structures and design using Java] Data structures : abstraction and design using Java / Elliot B. Koffman, Temple University, Paul A.T. Wolfgang, Temple University. — Third edition. pages cm Original edition published under title: Objects, abstraction, data structures and design using Java. Includes index. ISBN 978-1-119-23914-7 (pbk.) 1. Data structures (Computer science) 2. Java (Computer program language) 3. Object-oriented programming (Computer science) 4. Application program interfaces (Computer software) I. Wolfgang, Paul A. T. II. Title.

QA76.9.D35K58 2016 005.7'3—dc23

2015036861

Printing identification and country of origin will either be included on this page and/or the end of the book. In addition, if the ISBN on this page and the back cover do not match, the ISBN on the back cover should be considered the correct ISBN.

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

Koffman-ffirs.indd 2 11/4/2015 3:00:52 PM

http://www.wiley.com/go/citizenship
http://www.copyright.com
http://www.wiley.com/go/permissions
http://www.wiley.com/goreturnlabel
Preface Our goal in writing this book was to combine a strong emphasis on problem solving and software design with the study of data structures. To this end, we discuss applications of each data structure to motivate its study. After providing the specification (interface) and the implementation (a Java class), we then cover case studies that use the data structure to solve a significant problem. Examples include maintaining an ordered list, evaluating arithmetic expressions using a stack, finding the shortest path through a maze, and Huffman coding using a binary tree and a priority queue. In the implementation of each data structure and in the solutions of the case studies, we reinforce the message “Think, then code” by performing a thorough analysis of the problem and then carefully designing a solution (using pseudo‐ code and UML class diagrams) before the implementation. We also provide a performance analysis when appropriate. Readers gain an understanding of why different data structures are needed, the applications they are suited for, and the advantages and disadvantages of their possible implementations.

Intended Audience This book was written for anyone with a curiosity or need to know about data structures, those essential elements of good programs and reliable software. We hope that the text will be useful to readers with either professional or educational interests.

It is intended as a textbook for the second programming course in a computing curriculum involving the study of data structures, especially one that emphasizes Object‐Oriented Design (OOD). The text could also be used in a more‐advanced course in algorithms and data struc- tures. Besides coverage of the basic data structures and algorithms (lists, stacks, queues, trees, recursion, sorting), there are chapters on sets and maps, balanced binary search trees, graphs, and an online appendix on event‐oriented programming. Although we expect that most read- ers will have completed a first programming course in Java, there is an extensive review chapter (included as an appendix) for those who may have taken a first programming course in a different language, or for those who need a refresher in Java.

Emphasis on the Java Collections Framework The book focuses on the interfaces and classes in the Java Collections Framework. We begin the study of a new data structure by specifying an abstract data type as an interface, which we adapt from the Java API. Readers are encouraged throughout the text to use the Java Collections Framework as a resource for their programming.

Our expectation is that readers who complete this book will be familiar with the data struc- tures available in the Java Collections Framework and will be able to use them in their future programming. However, we also expect that they will want to know how the data structures are implemented, so we provide thorough discussions of classes that implement these data structures. Each class follows the approach taken by the Java designers where appropriate. However, when their industrial‐strength solutions appear to be too complicated for beginners to understand, we have provided simpler implementations but have tried to be faithful to their approach.

Koffman-preface.indd 3 10/20/2015 3:02:35 PM

iv Preface

Think, then Code To help you “Think, then code” we discuss problem solving and introduce appropriate soft- ware design tools throughout the textbook. For example, Chapter 1 focuses on OOD and Class Hierarchies. It introduces the Uniform Modeling Language (also covered in Appendix B) to document an OOD. It introduces the use of interfaces to specify abstract data types and to facilitate contract programming and describes how to document classes using Javadoc‐style comments. There is also coverage of exceptions and exception handling. Chapter 2 intro- duces the Java Collections Framework and focuses on the List interface, and it shows how to use big‐O notation to analyze program efficiency. In Chapter 3, we cover different testing strategies in some detail including a discussion of test‐driven design and the use of the JUnit program to facilitate testing.

Features of the Third Edition We had two major goals for the third edition. The first was to bring the coverage of Java up to Java 8 by introducing new features of Java where appropriate. For example, we use the Java 7 diamond operator when creating new Collection objects. We use the Java 8 StringJoiner in place of the older StringBuilder for joining strings.

A rather significant change was to introduce Java 8 lambda expressions and functional inter- faces as a way to facilitate functional programming in Java in a new Section 6.4. Using these features significantly improved the code.

The second major goal was to provide additional emphasis on testing and debugging. To facilitate this, we moved our discussion of testing and debugging from an appendix to Chapter 3 and expanded our coverage of testing including more discussion of JUnit. We also added a new section that introduced test‐driven development.

A third goal was to ease the transition to Java for Python programmers. When introducing Java data structures (for example, arrays, lists, sets, and maps), we compared them to equiva- lent Python data structures.

Other changes to the text included reorganizing the chapter on lists and moving the discussion of algorithm analysis to the beginning of the chapter so that big‐O notation could be used to compare the efficiency of different List implementations. We also combined the chapters on stacks and queues and increased our emphasis on using Deque as an alternative to the legacy Stack class. We also added a discussion of Timsort, which is used in Java 8, to the chapter on sorting algorithms. Finally, some large case studies and an appendix were moved to online supplements.

Case Studies We illustrate OOD principles in the design and implementation of new data structures and in the solution of approximately 20 case studies. Case studies follow a five‐step process (prob- lem specification, analysis, design, implementation, and testing). As is done in industry, we sometimes perform these steps in an iterative fashion rather than in strict sequence. Several case studies have extensive discussions of testing and include methods that automate the test- ing process. Some case studies are revisited in later chapters, and solutions involving different data structures are compared. We also provide additional case studies on the Web site for the textbook (www.wiley.com/college/koffman), including one that illustrates a solution to the same problem using several different data structures.

Koffman-preface.indd 4 10/20/2015 3:02:35 PM

http://www.wiley.com/college/koffman
Preface v

Prerequisites Our expectation is that the reader will be familiar with the Java primitive data types including int, boolean, char, and double; control structures including if, case, while, for, and try‐catch; the String class; the one‐dimensional array; input/output using either JOptionPane dialog win- dows or text streams (class Scanner or BufferedReader) and console input/output. For those readers who lack some of the concepts or who need some review, we provide complete coverage of these topics in Appendix A. Although labeled an Appendix, the review chapter provides full coverage of the background topics and has all the pedagogical features (discussed below) of the other chapters. We expect most readers will have some experience with Java programming, but someone who knows another programming language should be able to undertake the book after careful study of the review chapter. We do not require prior knowledge of inheritance, wrapper classes, or ArrayLists as we cover them in the book (Chapters 1 and 2).

Pedagogy The book contains the following pedagogical features to assist inexperienced programmers in learning the material.

• Learning objectives at the beginning of each chapter tell readers what skills they should develop.

• Introductions for each chapter help set the stage for what the chapter will cover and tie the chapter contents to other material that they have learned.

• Case Studies emphasize problem solving and provide complete and detailed solutions to real‐world problems using the data structures studied in the chapter.

• Chapter Summaries review the contents of the chapter. • Boxed Features emphasize and call attention to material designed to help readers become

better programmers.

Pitfall boxes help readers identify common problems and how to avoid them.

Design Concept boxes illuminate programming design decisions and trade‐offs.

Programming Style boxes discuss program features that illustrate good programming style and provide tips for writing clear and effective code.

Syntax boxes are a quick reference for the Java structures being introduced.

• Self‐Check and Programming Exercises at the end of each section provide immediate feedback and practice for readers as they work through the chapter.

• Quick‐Check, Review Exercises, and Programming Projects at the end of each chapter review chapter concepts and give readers a variety of skill‐building activities, including longer projects that integrate chapter concepts as they exercise the use of data structures.

Theoretical Rigor In Chapter 2, we discuss algorithm efficiency and big‐O notation as a measure of algorithm efficiency. We have tried to strike a balance between pure “hand waving” and extreme rigor when determining the efficiency of algorithms. Rather than provide several paragraphs of

Koffman-preface.indd 5 10/20/2015 3:02:42 PM

vi Preface

formulas, we have provided simplified derivations of algorithm efficiency using big‐O nota- tion. We feel this will give readers an appreciation of the performance of various algorithms and methods and the process one follows to determine algorithm efficiency without bogging them down in unnecessary detail.

Overview of the book Chapter 1 introduces Object Oriented Programming, inheritance, and class hierarchies including interfaces and abstract classes. We also introduce UML class diagrams and Javadoc‐ style documentation. The Exception class hierarchy is studied as an example of a Java class hierarchy.

Chapter 2 introduces the Java Collections Framework as the foundation for the traditional data structures. These are covered in separate chapters: lists (Chapter 2), stacks, queues and deques (Chapter 4), Trees (Chapters 6 and 9), Sets and Maps (Chapter 7), and Graphs (Chapter 10). Each new data structure is introduced as an abstract data type (ADT). We pro- vide a specification of each ADT in the form of a Java interface. Next, we implement the data structure as a class that implements the interface. Finally, we study applications of the data structure by solving sample problems and case studies.

Chapter 3 covers different aspects of testing (e.g. top‐down, bottom‐up, white‐box, black‐ box). It includes a section on developing a JUnit test harness and also a section on Test‐ Driven Development. It also discuses using a debugger to help find and correct errors.

Chapter 4 discusses stacks, queues, and deques. Several applications of these data structures are provided.

Chapter 5 covers recursion so that readers are prepared for the study of trees, a recursive data structure. This chapter could be studied earlier. There is an optional section on list processing applications of recursion that may be skipped if the chapter is covered earlier.

Chapter 6 discusses binary trees, including binary search trees, heaps, priority queues, and Huffman trees. It also shows how Java 8 lambda expressions and functional interfaces sup- port functional programming.

Chapter 7 covers the Set and Map interfaces. It also discusses hashing and hash tables and shows how a hash table can be used in an implementation of these interfaces. Building an index for a file and Huffman Tree encoding and decoding are two case studies covered in this chapter.

Chapter 8 covers various sorting algorithms including mergesort, heapsort, quicksort and Timsort.

Chapter 9 covers self‐balancing search trees, focusing on algorithms for manipulating them. Included are AVL and Red‐Black trees, 2‐3 trees, 2‐3‐4 trees, B‐trees, and skip‐lists.

Chapter 10 covers graphs. We provide several well‐known algorithms for graphs, including Dijkstra’s shortest path algorithm and Prim’s minimal spanning tree algorithm. In most pro- grams, the last few chapters would be covered in a second course in algorithms and data structures.

Supplements and Companion Web Sites The following supplementary materials are available on the Instructor’s Companion Web Site for this textbook at www.wiley.com/college/koffman. Items marked for students are accessi- ble on the Student Companion Web Site at the same address.

Koffman-preface.indd 6 10/20/2015 3:02:42 PM

http://www.wiley.com/college/koffman
Preface vii

• Additional homework problems with solutions • Additional case studies, including one that illustrates a solution to the same problem

using several different data structures • Source code for all classes in the book (for students and instructors) • PowerPoint slides • Electronic test bank for instructors • Solutions to end‐of‐section odd‐numbered self‐check and programming exercises (for students) • Solutions to all exercises for instructors • Solutions to chapter‐review exercises for instructors • Sample programming project solutions for instructors • Additional homework and laboratory projects, including cases studies and solutions

Acknowledgments Many individuals helped us with the preparation of this book and improved it greatly. We are grateful to all of them. These include students at Temple University who have used notes that led to the preparation of this book in their coursework, and who class‐tested early drafts of the book. We would like to thank Rolf Lakaemper and James Korsh, colleagues at Temple University, who used earlier editions in their classes. We would also like to thank a former Temple student, Michael Mayle, who provided preliminary solutions to many of the exercises.

We would also like to acknowledge support from the National Science Foundation (grant num- ber DUE‐1225742) and Principal Investigator Peter J. Clarke, Florida International University (FIU), to attend the Fifth Workshop on Integrating Software Testing into Programming Courses (WISTPC 2014) at FIU. Some of the testing methodologies discussed at the workshop were integrated into the chapter on Testing and Debugging.

We are especially grateful to our reviewers who provided invaluable comments that helped us correct errors in each version and helped us set our revision goals for the next version. The individuals who reviewed this book are listed below.

Reviewers Sheikh Iqbal Ahamed, Marquette University Justin Beck, Oklahoma State University John Bowles, University of South Carolina Mary Elaine Califf, Illinois State University Tom Cortina, SUNY Stony Brook Adrienne Decker, SUNY Buffalo Chris Dovolis, University of Minnesota Vladimir Drobot, San Jose State University Kenny Fong, Southern Illinois University, Carbondale Ralph Grayson, Oklahoma State University Allan M. Hart, Minnesota State University, Mankato James K. Huggins, Kettering University Chris Ingram, University of Waterloo Gregory Kesden, Carnegie Mellon University Sarah Matzko, Clemson University Lester McCann, University of Arizona

Koffman-preface.indd 7 10/20/2015 3:02:42 PM

viii Preface

Ron Metoyer, Oregon State University Rich Pattis, Carnegie Mellon University Thaddeus F. Pawlicki, University of Rochester Sally Peterson, University of Wisconsin—Madison Salam N. Salloum, California State Polytechnic University, Pomona Mike Scott, University of Texas—Austin Victor Shtern, Boston University Mark Stehlik, Carnegie Mellon University Ralph Tomlinson, Iowa State University Frank Tompa, University of Waterloo Renee Turban, Arizona State University Paul Tymann, Rochester Institute of Technology Karen Ward, University of Texas—El Paso Jim Weir, Marist College Lee Wittenberg, Kean University Martin Zhao, Mercer University

Although all the reviewers provided invaluable suggestions, we do want to give special thanks to Chris Ingram who reviewed every version of the first edition of the manuscript, including the preliminary pages for the book. His care, attention to detail, and dedication helped us improve this book in many ways, and we are very grateful for his efforts.

Besides the principal reviewers, there were a number of faculty members who reviewed sample pages of the first edition online and made valuable comments and criticisms of its content. We would like to thank those individuals, listed below.

Content Connections Online Review Razvan Andonie, Central Washington University Antonia Boadi, California State University Dominguez Hills Mikhail Brikman, Salem State College Robert Burton, Brigham Young University Chakib Chraibi, Barry University Teresa Cole, Boise State University Jose Cordova, University of Louisiana Monroe Joyce Crowell, Belmont University Robert Franks, Central College Barabra Gannod, Arizona State University East Wayne Goddard, Clemson University Simon Gray, College of Wooster Wei Hu, Houghton College Edward Kovach, Franciscan University of Steubenville Saeed Monemi, California Polytechnic and State University Robert Noonan, College of William and Mary

Koffman-preface.indd 8 10/20/2015 3:02:43 PM

Preface ix

Kathleen O’Brien, Foothill College Rathika Rajaravivarma, Central Connecticut State University Sam Rhoads, Honolulu Community College Vijayakumar Shanmugasundaram, Concordia College Moorhead Gene Sheppard, Perimeter College Linda Sherrell, University of Memphis Meena Srinivasan, Mary Washington College David Weaver, Sheperd University Stephen Weiss, University of North Carolina—Chapel Hill Glenn Wiggins, Mississippi College Bruce William, California State University Pomona

Finally, we want to acknowledge the participants in focus groups for the second programming course organized by John Wiley & Sons at the Annual Meeting of the SIGCSE Symposium in March 2004. They reviewed the preface, table of contents, and sample chapters and also provided valuable input on the book and future directions of the course.

Focus Group Claude Anderson, Rose-Hulman Institute of Technology Jay M. Anderson, Franklin & Marshall University John Avitabile, College of Saint Rose Cathy Bishop‐Clark, Miami University—Middletown Debra Burhans, Canisius College Michael Clancy, University of California—Berkeley Nina Cooper, University of Nevada Las Vegas Kossi Edoh, Montclair State University Robert Franks, Central College Evan Golub, University of Maryland Graciela Gonzalez, Sam Houston State University Scott Grissom, Grand Valley State University Jim Huggins, Kettering University Lester McCann, University of Wisconsin—Parkside Briana Morrison, Southern Polytechnic State University Judy Mullins, University of Missouri—Kansas City Roy Pargas, Clemson University J.P. Pretti, University of Waterloo Reza Sanati, Utah Valley State College Barbara Smith, University of Dayton Suzanne Smith, East Tennessee State University Michael Stiber, University of Washington, Bothell Jorge Vasconcelos, University of Mexico (UNAM) Lee Wittenberg, Kean University

Koffman-preface.indd 9 10/20/2015 3:02:43 PM

x Preface

We would also like to acknowledge and thank the team at John Wiley & Sons who were responsible for the management of this edition and ably assisted us with all phases of the book development and production. They were Gladys Soto, Project Manager, Nichole Urban, Project Specialist, and Rajeshkumar Nallusamy, Production Editor.

We would like to acknowledge the help and support of our colleague Frank Friedman who also read an early draft of this textbook and offered suggestions for improvement. Frank and Elliot began writing textbooks together many years ago and Frank has had substantial influ- ence on the format and content of these books. Frank also influenced Paul to begin his teach- ing career as an adjunct faculty member and then hired him as a full‐time faculty member when he retired from industry. Paul is grateful for his continued support.

Finally, we would like to thank our wives who provided us with comfort and support through this arduous process. We very much appreciate their understanding and their sacrifices that enabled us to focus on this book, often during time we would normally be spending with them. In particular, Elliot Koffman would like to thank

Caryn Koffman

and Paul Wolfgang would like to thank

Sharon Wolfgang

Koffman-preface.indd 10 10/20/2015 3:02:43 PM

Contents xi

Contents Preface iii

Chapter 1 Object-Oriented Programming and Class Hierarchies 1

1.1 ADTs, Interfaces, and the Java API 2 Interfaces 2 The implements Clause 5 Declaring a Variable of an Interface Type 6 Exercises for Section 1.1 6

1.2 Introduction to Object‐Oriented Programming (OOP) 7 A Superclass and Subclass Example 8 Use of this. 9 Initializing Data Fields in a Subclass 10 The No‐Parameter Constructor 11 Protected Visibility for Superclass Data Fields 11 Is‐a versus Has‐a Relationships 12 Exercises for Section 1.2 12

1.3 Method Overriding, Method Overloading, and Polymorphism 13 Method Overriding 13 Method Overloading 15 Polymorphism 17 Methods with Class Parameters 17 Exercises for Section 1.3 18

1.4 Abstract Classes 19 Referencing Actual Objects 21 Initializing Data Fields in an Abstract Class 21 Abstract Class Number and the Java Wrapper Classes 21 Summary of Features of Actual Classes, Abstract Classes, and Interfaces 22 Implementing Multiple Interfaces 23 Extending an Interface 23 Exercises for Section 1.4 23

1.5 Class Object and Casting 24 The Method toString 24 Operations Determined by Type of Reference Variable 25 Casting in a Class Hierarchy 26 Using instanceof to Guard a Casting Operation 27 The Class Class 29 Exercises for Section 1.5 29

1.6 A Java Inheritance Example—The Exception Class Hierarchy 29 Division by Zero 29 Array Index Out of Bounds 30 Null Pointer 31 The Exception Class Hierarchy 31

Koffman-ftoc.indd 11 10/20/2015 3:01:55 PM

xii Contents

The Class Throwable 31 Checked and Unchecked Exceptions 32 Handling Exceptions to Recover from Errors 34 Using try‐catch to Recover from an Error 34 Throwing an Exception When Recovery Is Not Obvious 35 Exercises for Section 1.6 36

1.7 Packages and Visibility 36 Packages 36 The No‐Package‐Declared Environment 37 Package Visibility 38 Visibility Supports Encapsulation 38 Exercises for Section 1.7 39

1.8 A Shape Class Hierarchy 39 Case Study: Processing Geometric Figures 40 Exercises for Section 1.8 45 Java Constructs Introduced in This Chapter 46 Java API Classes Introduced in This Chapter 46 User‐Defined Interfaces and Classes in This Chapter 47 Quick‐Check Exercises 47 Review Questions 47 Programming Projects 48 Answers to Quick-Check Exercises 51

Chapter 2 Lists and the Collections Framework 53

2.1 Algorithm Efficiency and Big-O 54 Big-O Notation 56 Formal Definition of Big-O 57 Summary of Notation 60 Comparing Performance 60 Algorithms with Exponential and Factorial Growth Rates 62 Exercises for Section 2.1 62

2.2 The List Interface and ArrayList Class 63 The ArrayList Class 64 Generic Collections 66 Exercises for Section 2.2 68

2.3 Applications of ArrayList 68 A Phone Directory Application 69 Exercises for Section 2.3 69

2.4 Implementation of an ArrayList Class 70 The Constructor for Class KWArrayList 71 The add(E anEntry) Method 72 The add(int index, E anEntry) Method 73 The set and get Methods 73 The remove Method 74 The reallocate Method 74 Performance of the KWArrayList Algorithms 74 Exercises for Section 2.4 75

2.5 Single‐Linked Lists 75 A List Node 77

Koffman-ftoc.indd 12 10/20/2015 3:01:55 PM

Contents xiii

Connecting Nodes 78 A Single-Linked List Class 79 Inserting a Node in a List 79 Removing a Node 80 Completing the SingleLinkedList Class 81 The get and set Methods 82 The add Methods 82 Exercises for Section 2.5 83

2.6 Double‐Linked Lists and Circular Lists 84 The Node Class 85 Inserting into a Double‐Linked List 86 Removing from a Double‐Linked List 86 A Double‐Linked List Class 86 Circular Lists 87 Exercises for Section 2.6 88

2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 89 The LinkedList Class 89 The Iterator 89 The Iterator Interface 90 The Enhanced for Loop 92 The ListIterator Interface 92 Comparison of Iterator and ListIterator 94 Conversion between a ListIterator and an Index 95 The Iterable Interface 95 Exercises for Section 2.7 95