Java Reference
In-Depth Information
singly linked list,
each node consists of the data element and a link to the next
node in the list. The last node in the list has a
null next
link. In this section we
assume that the node is given by the following
ListNode
declaration, which
does not use generics:
class ListNode
{
Object element;
ListNode next;
}
The first node in the linked list is accessible by a reference, as shown in
Figure 17.1. We can print or search in the linked list by starting at the first
item and following the chain of
next
links. The two basic operations that must
be performed are insertion and deletion of an arbitrary item
x
.
For insertion we must define where the insertion is to take place. If we
have a reference to some node in the list, the easiest place to insert is immedi-
ately after that item. As an example, Figure 17.2 shows how we insert
x
after
item
a
in a linked list. We must perform the following steps:
Insertion consists
of splicing a node
into the list and can
be accomplished
with one statement.
tmp = new ListNode( ); // Create a new node
tmp.element = x; // Place x in the element member
tmp.next = current.next; // x's next node is b
current.next = tmp; // a's next node is x
As a result of these statements, the old list . . .
a
,
b
, . . . now appears as . . .
a
,
x
,
b
, . . . . We can simplify the code if the
ListNode
has a constructor that
initializes the data members directly. In that case, we obtain
figure 17.1
Basic linked list
frontOfList
a
b
c
d
figure 17.2
Insertion in a linked
list: Create new node
(
tmp
), copy in
x
, set
tmp
's next link, and set
current
's next link.
a
b
...
...
current
tmp
x
Search WWH ::
Custom Search