Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 84

np.next = curr; //we could also use prev.next for curr
prev.next = np;

This will change the following:

np

top

30

15 23 36 52

prev curr

to this:

top

15 23 30 36 52

prev np curr

As an exercise, verify that this code will work if the number to be added is bigger than all the numbers in the list.
Hint: when will the while loop exit?
If the number to be added is smaller than all the numbers in the list, it must be added at the head of the list and
becomes the new first node in the list. This means that the value of top has to be changed to the new node.
The while loop shown earlier will work in this case as well. The while condition will be false on the very first test
(since n will be smaller than curr.num ). On exit, we simply test whether prev is still null ; if it is, the new node must be
inserted at the top of the list.
If the list were initially empty, the while loop will exit immediately (since curr will be null ). In this case also, the
new node must be inserted at the top of the list, becoming the only node in the list.
Program P3.3 contains all the details. The insertion of a new node in its proper position in the list is delegated to
the function addInPlace . This function returns a pointer to the top of the modified list.

Program P3.3

import java.util.*;
public class BuildList3 {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Node top, np, last = null;

top = null;
System.out.printf("Enter some integers ending with 0\n");
int n = in.nextInt();
while (n != 0) {
top = addInPlace(top, n);
n = in.nextInt();
}
printList(top);
} //end main

public static Node addInPlace(Node top, int n) {
// This functions inserts n in its ordered position in a (possibly empty)
// list pointed to by top, and returns a pointer to the new list