Java Reference
In-Depth Information
to this:
top
23
52
15
Of course, before we delete, we should check that there
is
something to delete, in other words, that
top
is not
null
.
If there is only one node in the list, deleting it will result in the empty list;
top
will become
null
.
Deleting an arbitrary node from a linked list requires more information. Suppose
curr
(for “current”) points to
the node to be deleted. Deleting this node requires that we change the
next
field of the
previous
node. This means we
must know the pointer to the previous node; suppose it is
prev
(for “previous”). Then deletion of node
curr
can be
accomplished by this statement:
prev.next = curr.next;
This changes the following:
top
prev
curr
23
52
15
36
to this:
top
prev
curr
23
52
15
36
Effectively, the node pointed to by
curr
is no longer in the list—it has been deleted.
One may wonder what happens to nodes that have been deleted. In our discussion,
deletion
meant “logical
deletion.” That is, as far as processing the list is concerned, the deleted nodes are not present. But the nodes are still in
memory, occupying storage, even though we may have lost the pointers to them.
If we have a large list in which many deletions have occurred, then there will be a lot of “deleted” nodes scattered
all over memory. These nodes occupy storage even though they will never, and cannot, be processed.
Java's solution to this problem is
automatic garbage collection
. From time to time, Java checks for these
“unreachable” nodes and removes them, reclaiming the storage they occupy. The programmer never has to worry
about these “deleted” nodes.
3.7 Building a Sorted Linked List
As a third possibility, suppose we want to build the list so that the numbers are always sorted in ascending order.
Suppose the incoming numbers are as follows (
0
terminates the data):
36 15 52 23 0
We would like to build the following linked list:
top
15
23
36
52
Search WWH ::
Custom Search