← back to the schedule


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, and its test driver, K_SimpleLLTester.

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: 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. 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. Note that the K_SimpleLLTester.java class already contains some code that calls this method.
    Agile software development: Test your modifications in small units, as soon as you have something you can test.
  • Complete the isEmpty method in the K_SimpleLL class. It returns true if the list is empty, or false otherwise. Add code to the test driver to test it (in the testAddSize method, for example).
  • 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.

Implement the following methods inside K_SimpleLL.java and write the appropiate tests in K_SimpleLLTester.java.

  • Implement the method public void clear() to clear the linked list, setting the size to zero. What references need to be cleared for this method? What is the time complexity of this new method?

  • Implement the method
        public void addAfter (int index, T element) throws IndexOutOfBoundsException
    which will receive an element and add it after the specified index. For example, addAfter (1, “A”) will add “A” after the element at index 1, so the “A” is at index 2. Take care of indices that are out of bounds.

    Optional Analysis Question: how would an add(int index, T element) method be implemented differently if it were to add the new element at the specified index, inserting it in front of the element that used to be at that index, instead of after?

Clean and Refactor

Follow this link to clean and refactor your comments and code.

Submission

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!



← back to the schedule