Java Reference
In-Depth Information
24.4.3.5 Implementing
removeLast()
The
removeLast()
method removes the last element from the list. It can be implemented
as follows:
1
public
E removeLast() {
2
if
(size ==
0
)
return null
;
// Nothing to remove
3
else if
(size ==
1
) {
// Only one element in the list
4 Node<E> temp = head;
5 head = tail =
null
;
// list becomes empty
6 size =
0
;
7
empty?
size 1?
head
and
tail null
size
is 0
return element
return
temp.element;
8 }
9
else
{
10 Node<E> current = head;
11
12
for
(
int
i =
0
; i < size -
2
; i++)
13 current = current.next;
14
15 Node<E> temp = tail;
16 tail = current;
17 tail.next =
null
;
18 size--;
19
7
1
size
move tail
reduce size
return element
return
temp.element;
20 }
21 }
Consider three cases:
1. If the list is empty, return
null
(line 2).
2. If the list contains only one node, this node is destroyed;
head
and
tail
both become
null
(line 5). The size becomes
0
after the deletion (line 6) and the element value of the
deleted node is returned (line 7).
3. Otherwise, the last node is destroyed (line 17) and the
tail
is repositioned to point to
the second-to-last node. Figure 24.16a and Figure 24.16b show the last node before and
after it is deleted. The size is reduced by
1
after the deletion (line 18) and the element
value of the deleted node is returned (line 19).
head
current
tail
…
e
0
next
e
1
next
e
k
-2
next
e
k
-1
next
e
k
null
Delete this node
(a) Before the node is deleted.
head
tail
…
e
0
next
e
1
next
e
k
-2
next
e
k
-1
null
e
k
null
This node is deleted
(b) After the node is deleted.
F
IGURE
24.16
The last node is deleted from the list.
Search WWH ::
Custom Search