Linked Data Structures (continued)

Step 5: Testing

   public class LinkedList {
      Node head;

      public void insert(int key) {
          Node current = head;
          Node previous = null;
          Node temp = new Node();
          temp.key = key;
          temp.link = null;

          while(current != null && current.key < key) {
              previous = current;
              current = current.link;
          }
          previous.link = temp;
          temp.link = current;
      }
   }

Does it work?

Show the state of the linked list and all pointers at the end of each iteration of the while loop.

What is the end result?

This test case (inserting 18) is interesting and different from the case of inserting 15 because it tests something new: what happens when we try to insert a value that is already in the linked list.

There are several other cases that we should test to see if the code works on all cases:

Inserting at the front of the list

What happens when we call insert when key = 2? Trace the code on paper before trying to answer the question.

Inserting at the end of the list.

What happens when we call insert when key = 30? Trace the code on paper before trying to answer the question.

Inserting into an empty list.

What happens when we call insert(30) and head = null?

These test cases have exposed some problems with the code. Before going on to the next page, try to figure out on paper how to fix these problems. Be sure to trace your fixes carefully to make sure you have not introduced new problems.

Click here to compare your new code to the corrected version of the insert method.

Previous    |   Home   |   Next