Linked lists - Data Structures and Problem Solving Using Java - page 619

chapter 17

linked lists

I n Chapter 16 we demonstrated that linked lists can be used to store items
noncontiguously. The linked lists used in that chapter were simplified, with all
the accesses performed at one of the list's two ends.
In this chapter, we show

How to allow access to any item by using a general linked list

n

The general algorithms for the linked list operations

n

How the iterator class provides a safe mechanism for traversing and
accessing linked lists

n

List variations, such as doubly linked lists and circularly linked lists

n

How to use inheritance to derive a sorted linked list class

n

How to implement the Collections API LinkedList class

n

basic ideas

17.1

In this chapter we implement the linked list and allow general access (arbi-
trary insertion, deletion, and find operations) through the list. The basic linked
list consists of a collection of connected, dynamically allocated nodes. In a