A List Implementation That Links Data - Data Structures and Abstractions with Java - page 336

U sing an array to implement the ADT list has both advantages and disadvantages, as you saw in
the previous chapter. An array can either have a fixed size or be moved to a larger array when it
becomes full. Since a fixed-size array can lead to a full list, our class AList uses a resizable array to
provide as much space as the list needs. This strategy, however, requires data to move each time the
array expands. In addition, any array requires you to move data either to make room for a new entry
or to close up a gap after a deletion.
This chapter describes a linked implementation of the list. Like our previous linked implemen-
tations, this one uses memory only as needed for a new entry and returns any unneeded memory to
the system after an entry is removed. Moreover, it avoids moving data when adding or removing
list entries. These features make this way of implementing a list an important alternative to array-
based approaches.

Operations on a Chain of Linked Nodes

We used a chain of linked nodes in Chapter 2 to implement the ADT bag and in Chapter 6 to imple-
ment the ADT stack. In both of those cases, we added a node to and removed a node from the
beginning of the chain. We added a node to the end of a chain in Chapter 11 for one implementation
of the ADT queue. While those operations are still needed for a list, we also must be able to add
a node between existing nodes and to delete a node from positions other than the beginning or
end. Let's talk about these operations. We use the same class, Node , that appears in Listing 3-4 of
Chapter 3.

Adding a Node at Various Positions
To add a node to a chain at a specified position, we must consider the following cases:
• Case 1: The chain is empty

•

Case 2: Adding a node at the chain's beginning

•

Case 3: Adding a node between adjacent nodes

•

Case 4: Adding a node to the chain's end
As you will see, we will be able to combine these four cases into two. To that end, we examine each
case, even though some of the detail will be familiar to you.

14.1

Case 1: Adding a node to an empty chain. Although we have added nodes to an empty chain
before, let's recall the necessary steps. If firstNode is the head reference to the chain, it will con-
tain null when the chain is empty. Figure 14-1a illustrates this state, along with a node that we
want to add to the chain.

FIGURE 14-1

(a) An empty chain and a new node; (b) after adding the new
node to a chain that was empty

(a) (b)

firstNode firstNode

newNode newNode

newEntry newEntry