Java Reference
In-Depth Information
CURR
...
...
23
10
12
(A)
CURR
2
...
...
23
10
12
IT
1
(B)
Figure4.10
The linked list removal process. (a) The link
ed
list before removing
the node with value 10. (b) The linked list after rem
ova
l.
1
marks the list node
being removed.
it
is set to point to the element.
2
marks the
next
field of
the preceding list node, which is set to point to the node following the one being
deleted.
the node before it, because that is what we really want). This takes (n) time in
the average and worst cases. Implementation of method
moveToPos
is similar in
that finding the ith position requires marching down i positions from the head of
the list, taking (i) time.
Implementations for the remaining operations each require (1) time.
Freelists
The
new
operator is relatively expensive to use. Garbage collection is also expen-
sive. Section 12.3 discusses how general-purpose memory managers are imple-
mented. The expense comes from the fact that free-store routines must be capable
of handling requests to and from free store with no particular pattern, as well as
memory requests of vastly different sizes. This, combined with unpredictable free-
ing of space by the garbage collector, makes them inefficient compared to what
might be implemented for more controlled patterns of memory access.
List nodes are created and deleted in a linked list implementation in a way
that allows the
Link
class programmer to provide simple but efficient memory
management routines. Instead of making repeated calls to
new
, the
Link
class
can handle its own freelist. A freelist holds those list nodes that are not currently
being used. When a node is deleted from a linked list, it is placed at the head of the
freelist. When a new element is to be added to a linked list, the freelist is checked
to see if a list node is available. If so, the node is taken from the freelist. If the
freelist is empty, the standard
new
operator must then be called.
Freelists are particularly useful for linked lists that periodically grow and then
shrink. The freelist will never grow larger than the largest size yet reached by the
