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

add(E e) method for adding an element at the end of the list are efficient. However, the
methods add(int index, E e) and remove(int index) are inefficient, because they
require shifting a potentially large number of elements. You can use a linked structure to
implement a list to improve efficiency for adding and removing an element at the beginning
of a list.

24.4.1 Nodes
In a linked list, each element is contained in an object, called the node . When a new element
is added to the list, a node is created to contain it. Each node is linked to its next neighbor, as
shown in Figure 24.7.
A node can be created from a class defined as follows:

class Node<E> {
E element;
Node<E> next;

public Node(E e) {
element = e;
}
}

tail

Node 1 Node 2 Node n

…

head element 1 element 2

next

element n
null

next

F IGURE 24.7

A linked list consists of any number of nodes chained together.

We use the variable head to refer to the first node in the list, and the variable tail to the last
node. If the list is empty, both head and tail are null . Here is an example that creates a
linked list to hold three nodes. Each node stores a string element.

Step 1: Declare head and tail .

Node<String> head = null ; The list is empty now

Node<String> tail = null ;

head and tail are both null . The list is empty.

Step 2: Create the first node and append it to the list, as shown in Figure 24.8. After the
first node is inserted in the list, head and tail point to this node.

head = new Node<>( "Chicago" );

After the first node is inserted
head

tail = head;

"Chicago"
next: null

tail

F IGURE 24.8

Append the first node to the list. Both head and tail point to this node.

Step 3: Create the second node and append it into the list, as shown in Figure 24.9a. To
append the second node to the list, link the first node 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.9b.