Java Reference
In-Depth Information
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
Search WWH ::
Custom Search