Recursive List MINI-LAB

---

Understanding K_RecList

• Read over the K_RecList class. Without looking at the bodies of the methods, just looking at the signatures, how does it compare to K_SimpleLL and K_LLNode? What methods have been added, have different names, or do not appear?
• Why does implementing an addFirst method not make sense? Unlike K_SimpleLL, there is no wrapper class representing the list as a whole. Each node represents a node in a list, or a full list. A list is defined as:
  • an empty list
  • a list element followed by a list (the "rest of the list")

• Any "modifying" methods return a list that represents the new list.

  In a functional style, we can never modify a list, just create or create new ones that are variations on a them. All functions, therefore, are constructors, observers, or functions that return a different list (usually the tail of the current list or a new list constructed of a new element and the current list). These functions are not necessarily methods connected to the class, but are often functions outside the class. In fact, functional programs are often not object-oriented at all.

• Read over the buildTestList function in K_RecListTester.java. How does it build the list to use for test cases?

Implementation

• The following functions are provided:
  • constructors (provided)
  • head and tail (provided)
  • size (provided, but depends on isEmpty)
  • toString (provided)
• Complete the following functions:
  • isEmpty
  • getElement(int index)
    empty list and index of 0 are base cases; call getElement recursively passing a smaller index
  • newWithAppendedElt
  • newWithAppendedList
• Update buildTestList to append elements and test. Add tests for getElement, newWithAppendedElt, and newWithAppendedList.
• Optional — Add the following functions:
  • getFirst
  • getLast (empty list and list with just 1 element are base cases)
• Update buildTestList to test getFirst and getLast.

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

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