Java Reference
In-Depth Information
CURR
...
...
23
12
INSERT 10:
10
(A)
CURR
...
...
23
12
3
10
1
2
(B)
Figure4.9 The linked list inserti on p rocess. (a) The linked list before insertion.
(b) T he l inked list after insertion. 1 marks the element field of the new link
node. 2 marks the next field of the new link node, wh ich is set to point to what
used to be the current node (the node with value 12). 3 marks the next field of
the node preceding the current position. It used to point to the node containing 12;
now it points to the new node containing 10.
Operator new creates the new link node and calls the Link class constructor, which
takes two parameters. The first is the element. The second is the value to be placed
in the list node's next field, in this case “ curr.next .” Method setNext does
the assignment to curr 's next field. Figure 4.9 illustrates this three-step process.
Once the new node is added, tail is pushed forward if the new element was added
to the end of the list. Insertion requires (1) time.
Removing a node from the linked list requires only that the appropriate pointer
be redirected around the node to be deleted. The following lines from the remove
method of Figure 4.8 do precisely this.
Eit=curr.next().element(); //Remembervalue
curr.setNext(curr.next().next());//Removefromlist
Memory for the link will eventually be reclaimed by the garbage collector. Fig-
ure 4.10 illustrates the remove method. Removing an element requires (1) time.
Method next simply moves curr one position toward the tail of the list,
which takes (1) time. Method prev moves curr one position toward the head
of the list, but its implementation is more difficult. In a singly linked list, there is
no pointer to the previous node. Thus, the only alternative is to march down the list
from the beginning until we reach the current node (being sure always to remember
 
Search WWH ::




Custom Search