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

For the linked implementation LList2 , which maintains both a head reference and a tail refer-
ence to the chain of nodes, the first add method is O(1), and toArray is O( n ). The second add
method is O( n ), unless it adds to either the beginning or the end of the list, in which case it is O(1).
As you can see, some of the operations have the same time complexity for each implementation.
However, operations that add to the end of a list, replace an entry, or retrieve an entry take less time
when you use an array to represent a list than when you use a chain of linked nodes. If your applica-
tion uses these particular operations frequently, an array-based implementation could be attractive.
The operations that add or remove an entry at a given position have time requirements that
depend on this position regardless of their implementation. If your application primarily adds and
removes entries at or near the beginning of a list, use a linked implementation. If these operations
are mostly at or near the end of the list, use an array-based implementation. The operations that you
use the most in an application should influence your choice of implementation for an ADT.

Design Decision: Which implementation of an ADT should you use?
Even small changes to an ADT's underlying data structure can increase or decrease the time
efficiency of the ADT's operations. When choosing an implementation for an ADT, you should
consider the operations that your application requires. If you use a particular operation fre-
quently, you want its implementation to be efficient. Conversely, if you rarely use an opera-
tion, you can afford to use a class that has an inefficient implementation of that operation.
Like the linked implementations you have seen in previous chapters, the classes LList and
LList2 enable their instances to grow as large as necessary. You can add as many nodes to a
chain—and, therefore, entries to a list—as computer memory allows. Although resizing the array in
an array-based implementation gives you the same advantage, it comes with the cost of copying
data from one array to another. No such copying occurs in a linked implementation.
In addition, a chain enables you to add and remove nodes without moving any existing entries
that are already in the list. With an array, adding and removing entries usually requires that other
entries be moved within the array. However, you must traverse a chain from its beginning to deter-
mine where to make the addition or deletion.
Retrieving an existing entry from a chain requires a similar traversal to locate the desired entry.
When you use an array instead of a chain, you can access any element directly by position, without
searching the array. However, a method such as contains that does not have the position of an
entry must perform a search regardless of whether an array or a chain represents the list.
Finally, as you have seen before, a chain stores additional references compared to an array. For
each entry in a list, a chain stores two references, compared to an array's one. This additional mem-
ory requirement is somewhat offset by the fact that a chain uses memory only as needed for each
list entry, whereas an array often is larger than necessary, thereby wasting memory.
Any implementation of an ADT has its advantages and disadvantages. You should choose the
implementation that best suits your particular application.

Java Class Library: The Class LinkedList

14.28

Recall from Chapter 12 that the Java Class Library contains the interface java.util.List .
This interface is like our ListInterface , but it declares more methods. Also, some methods
have different names or specifications, and the list entries begin at position 0 instead of 1. Seg-
ment 12.12 of Chapter 12 summarized these differences.
The same package java.util contains the class LinkedList . This class implements the inter-
face List , as well as the interfaces Queue and Deque that are described in Chapter 10. Thus,
LinkedList defines more methods than are in the interface List . Furthermore, you can use the
class LinkedList as an implementation of the ADT queue, deque, or list.