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