Java Reference
In-Depth Information
When a new number is read, it is inserted in the existing list (which is initially empty) in its proper place. The first
number is simply added to the empty list.
Each subsequent number is compared with the numbers in the existing list. As long as the new number is greater
than a number in the list, we move down the list until the new number is smaller than, or equal to, an existing number
or we come to the end of the list.
To facilitate the insertion of the new number, before we leave a node and move on to the next one, we must save
the pointer to it in case the new number must be inserted after this node. However, we can know this only when we
compare the new number with the number in the next node.
To illustrate these ideas, consider the following sorted list, and suppose we want to add a new number (
30
, say) to
the list so that it remains sorted:
top
400
200
800
600
15
23
36
52
Assume the number above a node is the address of the node. Thus, the value of
top
is
400
.
First, we compare
30
with
15
. It is bigger, so we move on to the next number,
23
, remembering
the address (
400
) of
15
.
Next, we compare
30
with
23
. It is bigger, so we move on to the next number,
36
, remembering the
address (
200
) of
23
. We no longer need to remember the address (
400
) of
15
.
Next, we compare
30
with
36
. It is smaller, so we have found the number
before
which we must insert
30
. This is
the same as inserting
30
after
23
. Since we have remembered the address of
23
, we can now perform the insertion.
We will use the following code to process the new number,
n
:
prev = null;
curr = top;
while (curr != null && n > curr.num) {
prev = curr;
curr = curr.next;
}
Initially,
prev
is
null
and
curr
is
400
. The insertion of 30 proceeds as follows:
30
is compared with
curr.num
,
15
. It is bigger, so we set
prev
to
curr
(
400
) and set
curr
to
curr.next
,
200
;
curr
is not
null
.
•
30
is compared with
curr.num
,
23
. It is bigger, so we set
prev
to
curr
(
200
) and set
curr
to
curr.next
,
800
;
curr
is not
null
.
•
30
is compared with
curr.num
,
36
. It is smaller, so we exit the
while
loop with
prev
being
200
and
curr
being
800
.
•
We have the following situation:
top
400
200
800
600
15
23
36
52
prev
curr
If the new number is stored in a node pointed to by
np
, we can now add it to the list (except at the head;
see the next section) with the following code:
Search WWH ::
Custom Search