University of Toronto
Department of Computer Science
csc 148: Introduction to Computer Science

Linked Data Structures (continued)

Step 2: Finding the spot to insert

Okay, so far we have

   public class LinkedList {
      Node head;

      public void insert(int key) {
          Node current = head;

          while(current != null) {
              current = current.link;
          }
      }
   }

Now let's extend the code to stop when we have found the spot to insert the new element. For example, if we are inserting a 15 into the following list, it must go between 11 and 18.

Now we can't know when current points to the 11 node that we must insert immediately afterward -- there could be a 12 in the next node. But as soon as we get to the 18 node, we know that the new node should be inserted before that node. We need a second condition to add to our while loop so that it will stop at this point.

What condition will be true until we reach the stopping node -- the node before which the new one must be inserted? (The condition will become false when we do reach the stopping node, causing the loop to stop.)

How should we join the two conditions? (Remember that && means "and" in Java, and || means "or".

Now we can stop in the following situation. (Again, assume that we are inserting 15.)

To move on to the next step, click here.

Previous | Home | Next