← 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 delete any node by index. You must also insure that your methods correctly update the size property for the list. You will primarily be modifying the class K_SimpleLL which stores objects (in this case String objects) as the data portion of the nodes.

You might find it useful to write a toString() method to print the linked list, which is the first bullet under Optional Improvements.

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.
  • Agile software development: Read the 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 addElement method. The addElement 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. Test your code using the K_SimpleLLTester.java class, which contains the main method
  •  
  • Implement an addLast method that takes the same parameter as addFirst, but adds the element at the end of the list. Note that adding a "last" element to an empty list is a special case. 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 removeElement, they should return the element that they are removing. (Hint: you can use the removeElement method!) Write code in K_SimpleLLTester to test your new methods.
     

    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 removeElement 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 String toString() which, when invoked, will return a String containing all the elements of the linked list. For example [Z, Y, X] for a list with 3 elements Z, Y, and X or [] for an empty list.
  • Implement the method public void addElementAfter (T element, int index) throws NoSuchElementException which will receive an element and add it after the specified index. For example, addElement (“A”, 1) will add “A” after the element at index 1, so the “A” is at index 2. Take care of indexes that are out of bounds.
  • Implement the method public void clear() which will clear the linked list, setting the size to zero. Question: What references need to be cleared for this method?

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

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