Case 4: First Attempt

Case 4 is inserting into the middle of the list (because the new value fits between two existing nodes)

The next few pages show a first attempt at handling case 4. Later on case 3 and case 4 will be combined into a better method. But for now, let's look at case 4 in isolation. The goal is to set up the blue pointers and shown, and then set the green pointers.

Case 4: The newNode contains a value that should be linked between two others. The previous cases have ruled out the possibility that it should be placed first or last or into an empty list, so the only possibility left is that it fits between two nodes.

To do this, set up two pointers that surround the gap that newNode should fill.

• current: points to the node that newNode potentially follows
• next: points to the node that potentially follows newNode

In other words:

• the current node: contains a value less than that of newNode
• the next node: contains a value greater than or equal to that of newNode

headPtr as always points to the head of the list. We know that there are at least two nodes in the list because otherwise one of cases I, II, or III would have happened. So it is safe to initialize current and next:

    current = headPtr;
    Node next = headPtr.getNext();

In the picture, current would point at 5 and next would point at 8. Now the gap between current and next is inspected to see if the new node should go there. If not, move current and next together down the list until the correct gap is found. In the picture, this means keep moving the pointers until next points at a node that holds a value greater or equal to data.

    while ( data > next.getValue() )
    {
      current = next;
      next = next.getNext();
    }

When the correct gap is found, link in the new node:

    while ( data > next.getValue() )
    {
      current = next;
      next = next.getNext();
    }
    newNode.setNext(   );
    current.setNext(  );

If data is equal to the node pointed to by next, then then new node will be linked in front of next.