If data are supplied in unordered fashion, building an ordered linked list from the data becomes a harder problem. Consider the following cases for inserting a new value into the linked list:

a. Insert the new value into an empty list.

b. Insert the new value at the front of the list.

c. Insert the new value at the end of the list.

d. Insert the new value between two nodes.

Suppose the data was supplied in this order.

42 6 95 12 <eof>

The resulting ordered linked list looks like this:

Two of the cases are easy to identify and solve: the empty list case (a) and placing the new value at the front of the list (b). Adding the value to the end of the list (c) is easy to identify and solve if you maintain a marker to the last node. To assist us in our discussion of linked list algorithms, two definitions will be helpful:

1. An internal pointer is one that exists inside a node. An internal pointer joins one node to the next in the linked list.

2. An external pointer is one that points to a node from outside the list. Every linked data structure must have at least one external pointer that allows access to the data structure. The linked list in this lesson has two external pointers, first and last.

Suppose a fifth value, 61, is to be inserted into the list (d). We can see in the diagram that it will go between the 42 and 95. When inserting a value into the list, we will use helping external pointers, also called auxiliary pointers.

It is possible to find the attachment point using just one auxiliary pointer, but we will use two: temp and back. Using two external pointers makes the hookup easier. Finding the attachment point involves a search. The pointer, temp, starts at first and is moved through the list until it is just past the insertion point. The pointer, back, trails temp by one position at each step of the search.

while we haven't found the attachment point
{
   back = temp;           //move back up to temp
   temp = temp.getNext(); //advance temp one node ahead
}

The position of our pointers at the end of the search:

The new node needs to be placed between back and temp. If we call this new node newValue, then inserting it into the list would consist of the following steps.

back.setNext(newValue);
newValue.setNext(temp);