IMPLEMENTING LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 913

head current temp tail

… …

e 0
next

e i
next

e i +1
next

e k
null

A new node
to be inserted
here

e
null

(a) Before a new node is inserted.

current temp tail

head

… …

e 0
next

e i
next

e i +1
next

e k
null

A new node
is inserted in
the list

e
next

(b) After a new node is inserted.

F IGURE 24.14

A new element is inserted in the middle of the list.

4 Node<E> temp = head; // Keep the first node temporarily
5

keep old head
new head
decrease size
destroy the node

head = head.next; // Move head to point to next node

6 size--; // Reduce size by 1

7 if (head == null ) tail = null ; // List becomes empty

8 return temp.element; // Return the deleted element

9 }
10 }

Consider two cases:

1. If the list is empty, there is nothing to delete, so return null (line 2).

2. Otherwise, remove the first node from the list by pointing head to the second node.
Figure 24.15a and Figure 24.15b show the linked list before and after the deletion. The
size is reduced by 1 after the deletion (line 6). If the list becomes empty, after removing
the element, tail should be set to null (line 7).

head tail

… …

e 0
next

e 1
next

e i
next

e i +1
next

e k
null

Delete this node

(a) Before the node is deleted.

head tail

… …

e 0
next

e 1
next

e i
next

e i +1
next

e k
null

This node is deleted

(b) After the node is deleted.

F IGURE 24.15

The first node is deleted from the list.