The collections api - Data Structures and Problem Solving Using Java - page 254

LinkedList costs
If we look at the LinkedList operations, we can see that adding at either the
front or the end is an operation. To add at the front, we simply create a
new node and add it at the front, updating first . This operation does not
depend on knowing how many subsequent nodes are in the list. To add at the
end, we simply create a new node and add it at the end, adjusting last .
Removing the first item in the linked list is likewise an operation,
because we simply advance first to the next node in the list. Removing the
last item in the linked list appears to also be , since we need to move
last to the next-to-last node, and update a next link. However, getting to the
next-to-last node is not easy in the linked list, as drawn in Figure 6.19.
In the classic linked list, where each node stores a link to its next node,
having a link to the last node provides no information about the next-to-last
node. The obvious idea of maintaining a third link to the next-to-last node
doesn't work because it too would need to be updated during a remove.
Instead, we have every node maintain a link to its previous node in the list.
This is shown in Figure 6.20 and is know as a doubly linked list .
In a doubly linked list, add and remove operations at either end take
time. As we know, there is a trade-off, however, because get and set are no
longer efficient. Instead of direct access through an array, we have to follow
links. In some cases we can optimize by starting at the end instead of the
front, but if the get or set is to an item that is near the middle of the list, it
must take time.
contains in a linked list is the same as an ArrayList : the basic algorithm is
a sequential search that potentially examines every item, and thus is an
operation.

O ( )

O ( )

O ( )

O ( )

O ( N )

O ( N )

comparison of ArrayList and LinkedList costs
Figure 6.21 compares the running time of single operations in the ArrayList
and LinkedList .
To see the differences between using ArrayList and LinkedList in a larger
routine, we look at some methods that operate on a List . First, suppose we
construct a List by adding items at the end.

figure 6.20
A doubly linked list

a b c d

first last