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

head tail

A new node
to be inserted
here

… …

e 0
next

e i
next

e i +1
next

e k
null

e
null

(a) Before a new node is inserted.

head

A new node
is appended
in the list

… …

e 0
next

e i
next

e i +1
next

e k
next

tail

e
null

(b) After a new node is inserted.

F IGURE 24.13

A new element is added at the end of the list.

24.4.3.3 Implementing add(index, e)
The add(index, e) method inserts an element into the list at the specified index. It can be
implemented as follows:

1 public void add( int index, E e) {
2 if (index == 0 ) addFirst(e); // Insert first
3 else if (index >= size) addLast(e); // Insert last
4 else { // Insert in the middle
5 Node<E> current = head;
6 for ( int i = 1 ; i < index; i++)
7 current = current.next;
8 Node<E> temp = current.next;
9 current.next = new Node<E>(e);
10 (current.next).next = temp;
11 size++;
12 }
13 }

insert first
insert last

create a node

increase size

There are three cases when inserting an element into the list:

1. If index is 0 , invoke addFirst(e) (line 2) to insert the element at the beginning of the list.

2. If index is greater than or equal to size , invoke addLast(e) (line 3) to insert the ele-
ment at the end of the list.

3. Otherwise, create a new node to store the new element and locate where to insert it. As
shown in Figure 24.14a, the new node is to be inserted between the nodes current and
temp . The method assigns the new node to current.next and assigns temp to the
new node's next , as shown in Figure 24.14b. The size is now increased by 1 (line 11).

24.4.3.4 Implementing removeFirst()
The removeFirst() method removes the first element from the list. It can be implemented
as follows:

1 public E removeFirst() {
2 if (size == 0 ) return null ; // Nothing to delete nothing to remove

3 else {