Lab 10: Linked Lists and Recursion

It this lab, you will practice manipulating linked lists and using recursion.

The following classes were defined in class:

Iterative programming

There are three different styles we can use to manipulate linked lists. The first way is the standard iterative style. In this style, we use loops to traverse the list. For example, to print out the contents of a LinkedList, we can add the following method to LinkedList.java: 
  public void print() {
    LLNode<T> listptr = head;
    while (listptr != null) {
      System.out.print(listptr.getElement() + " ");
      listptr = listptr.getNext();
    }
    System.out.println();
  }
You can type this method into the LinkedList class to help you test your code.

Try to write the following method using the iterative style:
public T last
returns the last element of the linked list.

Structural Recursion

Another style for manipulating linked lists is to use structural recursion. In this style, we call the method to process the head of the linked list, and that method continues the processing by calling the same method for the next element of the linked list. Structural recursive methods have the following structure:
if (this is the last element of the list)
    process this element
else
    do processing for this element and call the method for next

For example, we can create a toString method that creates a String representation of the linked list by adding the following method to LinkedList: 

  public String toString() {
    if (head == null)
      return null;
    return head.toString();
  }
and the following method to LLNode: 
  public String toString() {
    if (getNext() != null)
      return getElement().toString() + " " + getNext().toString();
    else
      return getElement().toString();
  }
Try entering this code into the classes and testing it.

Now your turn. Try to write the method:
T recursiveLast()
that returns the last element of the list but uses structural recursion.

Standard Recursion

A third type of style is regular recursion. In regular recursion, a method calls itself with a reduced input. The style of regular recursion is again the if statement:
if (the stopping condition of the recursion)
    return the base case
else
    call the method on a reduced input and correctly process the returned value

For example, the usual example is the factorial method that takes an int n and returns the product of 1*2*3*...*n. 

  public static int factorial(int n) {
    if (n == 0)
      return 1;
    else
      return n * factorial(n - 1);
  }
Notice that factorial calls itself on a reduced input each time until we get to the stopping condition (n = 0).

Here is the start of a method that returns the length of a linked list. 

  public int length() {
    return length(head);
  }
  
  public int length(LLNode<T> node) {
    if (node == null)
      return a base value
    else
      return processing and call length(node.getNext());
  }
Place this code into LinkedList.java and add the necessary expressions to complete the code.

Now try this one. The method append will take a LinkedList and append the LinkedList to the end of the current list. However, it will do this recursively. (You probably notice that this is not the most efficient way to write append, but try it anyway. It is a good exercise in the technique.) 

  public void append(LinkedList<T> list) {
    head = append(this.head, list.head);
  }
  
  public LLNode<T> append(LLNode<T> list1, LLNode<T> list2) {
    if (list1 == null)
      return a base value
    else
      return processing and call append(reduced list1, list2)

Something new

Now try to write the following method. merge assumes both the parameter list and the current list are sorted in increasing order, and it merges list into the current list so that the result is still in sorted order. 
public void merge(LinkedList<T> list) {
For example, suppose list1 is {2 4 6 8} and list2 is {1 3 5}, the the result of calling list1.merge(list2) should be to have list1 be {1 2 3 4 5 6 8}. It is ok to destroy list2 in the process.

What you must not do: Do not just run through the parameter list calling removeFromHead to get the next element and insertInOrder to place it into the list. While this method works, it is quite inefficient and you will notice a large slowdown on long (100,000+) lists.

What you should do: Make your method repeatedly check the first element of each list, until there are no more elements (actually you can stop a little sooner) and make the smaller of the two elements be the next element of the final list. This is a challenging task, and you can use any of the three styles described above.

At the end of lab, email your code to me.