Java Reference
In-Depth Information
To summarize, the following two lines insert a new node with
newData
as its data.
The new node is inserted between the nodes named by
previous
and
position
.
temp =
new
Node(newData, position);
previous.link = temp;
previous
,
position
, and
temp
are all variables of type
Node
. (When we use this code,
previous
and
position
will be instance variables of an iterator and
temp
will be a local
variable.)
Just like deletion, special cases exist for insertion that must be handled. If the list is
empty, then addition is done by adding to the front of the list. If the
position
variable
is
null
, then the new node should be added to the end of the list.
Self-Test Exercises
11. Consider a variant of the class in Display 15.17 with no
previous
local variable.
In other words, there is no reference kept to the node that links to the current
node position. How could we modify the
delete
method to delete the
position
node and still maintain a correct list? The solution is less efficient than the ver-
sion that uses
previous
.
12. Consider a variant of the class in Display 15.17 with no
previous
local variable.
In other words, there is no reference kept to the node that links to the current
node
position
. Write a method
addAfterHere(String newData)
that adds a
new node after the node in
position
.
13. Complete the definition of the method
changeHere
in the inner class
List2Iterator
in Display 15.17.
14. Given an iterator pointing somewhere in a linked list, does
i.next( )
return the
value that
i
is referencing prior to the invocation of
i.next( )
or does it return
the value of the next node in the list?
15.4
Variations on a Linked List
I have called this principle, by which each slight variation, if useful, is
preserved, by the term Natural Selection.
CHARLES DARWIN, The Origin of Species
In this section, we discuss some variations on linked lists, including the two data struc-
tures known as stacks and queues. Stacks and queues need not involve linked lists, but
one common way to implement a stack or a queue is to use a linked list.
