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

head tail

… …

e 0
next

e i
next

e i +1
next

e k
null

A new node
to be inserted
here e

next

(a) Before a new node is inserted.

tail

… …

e 0
next

e i
next

e i +1
next

e k
null

head

This is
the new
node

e
next

(b) After a new node is inserted.

F IGURE 24.12

A new element is added to the beginning of the list.

If the list is empty (line 7), both head and tail will point to this new node (line 8). After
the node is created, size should be increased by 1 (line 5).
24.4.3.2 Implementing addLast(e)
The addLast(e) method creates a node to hold the element and appends the node at the end
of the list. It can be implemented as follows:

1 public void addLast(E e) {
2 Node<E> newNode = new Node<>(e); // Create a new node for e

create a node

3
4 if (tail == null ) {

5 head = tail = newNode; // The only node in list

6 }
7 else {
8 tail.next = newNode; // Link the new node with the last node
9 tail = tail.next; // tail now points to the last node
10 }
11
12 size++; // Increase size
13 }

increase size

The addLast(e) method creates a new node to store the element (line 2) and appends it to
the end of the list. Consider two cases:

1. If the list is empty (line 4), both head and tail will point to this new node (line 5);

2. Otherwise, link the node with the last node in the list (line 8). tail should now point to
this new node (line 9). Figure 24.13a and Figure 24.13b show the new node for element
e before and after the insertion.

In any case, after the node is created, the size should be increased by 1 (line 12).