Data Structures and the Java Collections Framework, Third Edition

CHAPTER 7

Linked Lists

In this chapter we continue our study of collection classes by introducing the LinkedList class, part of the Java Collections Framework. Like the ArrayList class, the LinkedList class implements the List interface, so you are already familiar with most of the LinkedList method headings. There are some significant performance differences between the two classes. For example, LinkedList objects lack the random-access feature of ArrayList objects: to access a LinkedList 's element from an index requires a loop. But LinkedList objects allow constant-time insertions and deletions, once the insertion-point or deletion-point has been accessed.

We will start with a general discussion of linked lists, and then introduce a simple linked structure, the singlyLinkedList class. This toy class serves mainly to prepare you for the more powerful, and more complicated, LinkedList class. The application of the LinkedList class, a line editor, takes advantage of a LinkedList iterator's ability to insert or remove in constant time.

CHAPTER OBJECTIVES

1. Be able to develop new methods for the singlyLinkedList class.
2. Understand the LinkedList class from a user's perspective.
3. Given an application that requires a list, be able to decide whether an ArrayList or a LinkedList would be more appropriate.
4. Compare several choices of fields for the LinkedList class and, for each choice, be able to create a LinkedList object.

7.1 What is a Linked List?

Before we start investigating the ...