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

tail

tail.next = new Node<>( "Denver" ); head

"Chicago"
next

"Denver"
next: null

(a)

tail

tail = tail.next; head

"Denver"
next: null

"Chicago"
next

(b)

F IGURE 24.9

Append the second node to the list. Tail now points to this new node.

Step 4: Create the third node and append it to the list, as shown in Figure 24.10a. To
append the new node to the list, link the last node in the list with the new node. The
new node is now the tail node, so you should move tail to point to this new node, as
shown in Figure 24.10b.

tail

tail.next = new Node<>( "Dallas" ); head "Chicago"

next

"Denver"
next

"Dallas"
next: null

(a)

tail

tail = tail.next; head "Chicago"

next

"Denver"
next

"Dallas"
next: null

(b)

F IGURE 24.10

Append the third node to the list.

Each node contains the element and a data field named next that points to the next element. If
the node is the last in the list, its pointer data field next contains the value null . You can use
this property to detect the last node. For example, you can write the following loop to traverse
all the nodes in the list.

current pointer
check last node

1 Node current = head;
2 while (current != null ) {
3 System.out.println(current.element);
4 current = current.next; next node

5 }

The variable current points initially to the first node in the list (line 1). In the loop, the
element of the current node is retrieved (line 3), and then current points to the next node
(line 4). The loop continues until the current node is null .

24.4.2 The MyLinkedList Class
The MyLinkedList class uses a linked structure to implement a dynamic list. It extends
MyAbstractList . In addition, it provides the methods addFirst , addLast , removeFirst ,
removeLast , getFirst , and getLast , as shown in Figure 24.11.