Linked Lists - Building Java Programs: A Back to Basics Approach - page 926

Chapter 16

Linked Lists

Introduction

Working with Nodes

16.1

Constructing a List

In the previous chapter, we explored how to build a list structure using an
array as the underlying storage mechanism. In this chapter we will explore
a different structure known as a linked list . Linked lists serve as a useful
contrast to arrays because their strengths and weaknesses are completely
opposite.And just as Java has an ArrayList<E> class as part of the col-
lections framework, it also has a LinkedList<E> class.

List Basics

Manipulating Nodes

Traversing a List

A Linked List Class 16.2

Simple LinkedIntList

Appending add

The Middle of the List

Even though Java provides an off-the-shelf implementation of a linked list,
it is useful to study how it is implemented because it will give you good
insights into the properties of linked lists. It is also important for you to
understand the concept of a linked structure.Almost all data structures
are implemented using some combination of arrays or linking or both,
which means that it is important to understand each approach.

A Complex List
Operation

16.3

Inchworm Approach

An IntList Interface

16.4

16.5 LinkedList<E>

Linked List Variations

Linked List Iterators

We will once again develop a structure for storing simple int values, as
we did with the development of ArrayIntList in the last chapter. Our
new structure will be called LinkedIntList . Keeping the data simple
will allow us to focus on the data structure issues and to learn how to
manipulate linked lists in general. Then we will explore some issues
related to interfaces. Finally, at the end of the chapter we will explore
how to turn the fairly simple LinkedIntList into a more general
LinkedList<E> class.

Other Code Details

929