Linked List MINI-LAB

---

The goal of this mini-lab is to complete a singly linked list that adds new nodes to the front or end of a list, can remove nodes from either end, and can delete any node by index. You must also ensure that your methods correctly update the size property for the list. You will primarily be modifying and completing the class K_SimpleLL, which consists of a linked list of K_LLNode nodes.

There are two common patterns for stepping through a linked list:

    for (K_LLNode curNode = first; curNode.getNext() != null;
                curNode = curNode.getNext())
    {
        // Do something with curNode
    }

or

    K_LLNode curNode = first
    while ( curNode.getNext() != null )
    {
        // Do something with curNode.

        // Advance curNode.
        curNode = curNode.getNext())
    }

The get, remove and toString methods in K_SimpleLL provide examples of variations on the first pattern, either because they have to keep track of the index number or they have to handle the last node in the list a little differently from the previous nodes (or both).

Completing a Linked List Class

• Download three files into a new folder:
  • K_SimpleLL.java
  • K_LLNode.java
  • K_SimpleLLTester.java
  Import the folder into BlueJ (or your preferred GUI). For example, in BlueJ, select "Open Non BlueJ..." in the "Project" menu and browse to locate your folder.
• Agile software development: Read the (incomplete) classes provided to you and try running the program before making any modifications to be sure that you understand its initial functionality.
•  
• Add an extra constructor to the K_LLNode class that takes 2 parameters, a data element and a reference to another K_LLNode class.
•  
• Add code to K_SimpleLL.java to complete the addFirst method. The addFirst accepts any valid object as the data for a new node in the list, constructs a new K_LLNode at the front of the list, and updates the first pointer and the size property of the list. (Hint: your new K_LLNode constructor is appropriate here.) Test your code using the K_SimpleLLTester.java class, which contains the main method
•  
• Complete the isEmpty method in the K_SimpleLL class. It returns true if the list is empty, or false otherwise.
•  
• Complete the addLast method. It takes the same parameter as addFirst, but adds the element at the end of the list. This method can use either the for pattern or while pattern illustrated above. Note that adding a "last" element to an empty list is a special case (and is actually the same as adding a "first" element to an empty list). Add code to an existing method or a new method in K_SimpleLLTester to test your new method.
•  
• Implement removeFirst and removeLast methods to remove the first and last elements from the list. Like remove, they should return the element that they are removing. (Hint: you can use the remove method!) Write code in K_SimpleLLTester to test your new methods.
•  
• Read and compare the get and remove methods. Make sure you understand why the get method can be simpler than remove. Add code to an existing method or a new method in K_SimpleLLTester to test the get method. (The test driver already has code to test the remove method.)
•  
• Implement the set(int index, T element) method. This method is similar to the get, but replaces the value at the specified location.
   

  Analysis Question:

  • What is the time complexity of each method in the K_SimpleLL class?

---

Adding a Pointer to the Last Element

• Add a new instance variable called last to the K_SimpleLL class. This new instance variable should always point to the last element in the list.
   

  Analysis Question:

  • What methods will need to change as a result of this new instance variable?
•  
• Modify the constructor and the addFirst, addLast, and remove methods, as well as any others that need to change. Can any methods be done more simply or more efficiently now that you have this new variable? Test your changes using your existing tests. (This is called regression testing.)
   

  Analysis Question:

  • Did your modifications change the time complexity of any methods in the class?

---

Optional Improvements

This mini-lab has an optional portion to add extra interest.

Submit your completed program through Kit, under LinkedList Mini-Lab.

Have fun! And if you have any questions remember my email, my office hours, and the Collaboration Center are here for you!