Homework 8, Part A: Merge-Sorting a Linked List

In this assignment, we will walk you through implementing merge sort for a linked list. In addition to the coding problems, we ask you to answer open-response questions and submit your answers in a file called Answers.txt.

Task 0: Creating your BlueJ project

Create a BlueJ project with the following starter code.

LinearList.java:

public interface LinearList<T> {
    public boolean isEmpty();
    public int size();
    public T get(int position);
    public void insert(int position, T element);
    public T remove(int position);
    public String toString();
}

LinearNode.java:

public class LinearNode<T> {
   private LinearNode<T> next;
   private T element;

   public LinearNode() {
      next = null;
      element = null;
   }

   public LinearNode(T elem) {
      next = null;
      element = elem;
   }

   public LinearNode<T> getNext() {
      return next;
   }

   public void setNext(LinearNode<T> node) {
      next = node;
   }

   public T getElement() {
      return element;
   }

   public void setElement(T elem) {
      element = elem;
   }
}

LinkedList.java:

public class LinkedList<T> implements LinearList<T> {
    protected LinearNode<T> front;
    protected int count;
    
    public LinkedList() {
        this.front = null;
        this.count = 0;
    }
    
    public boolean isEmpty() {
        return this.count == 0;
    }
    
    public int size() {
        return this.count;
    }

    protected LinearNode<T> getNode(int position) {
        if (position < 0 || position >= this.count) {
            throw new RuntimeException(
                "Asking for element at index " + position 
                + " in a list of size" + this.count
            );
        }
        
        LinearNode<T> current = this.front;
        for (int i = 0; i < position; i++) {
            current = current.getNext();
        }
        
        return current;
    }
    
    public T get(int position) {
        LinearNode<T> node = this.getNode(position);
        if (node == null) {
            return null;
        }
        
        return node.getElement();
    }
    
    public void insert(int position, T element) {
        LinearNode<T> node = new LinearNode<T>(element);
        
        if (position == 0) {
            node.setNext(front);
            front = node;
        } else {
            LinearNode<T> before = this.getNode(position - 1);
            node.setNext(before.getNext());
            before.setNext(node);
        }
        
        this.count++;
    }
    
    public T remove(int position) {
        LinearNode<T> current;
        if (position == 0) {
            current = front;
            front = front.getNext();
        } else {
            LinearNode<T> before = this.getNode(position - 1);
            current = before.getNext();
            before.setNext(current.getNext());
        }  
        
        this.count--;
        return current.getElement();
    }

    public String toString() {
        String s = "[ ";
        
        LinearNode<T> current = this.front;
        for (int i = 0; i < this.size(); i++) {
            s += current.getElement().toString() + ", ";
            current = current.getNext();
        }
        
        return s + "]";
    }
}

Then, answer:

• Which instance variables/methods are protected?
• Why would we choose to make them protected instead of private for this assignment?

Task 1

Instructions. Create a class, SortableLinkedList, with the following header:

public class SortableLinkedList<T extends Comparable<T>> extends LinkedList<T> {
  ...
}

This is the class in which you will implement your sortable linked list.

Answer.

• What does each part of the syntax in the class header mean?
• Why do we mention Comparable<T> in the class header?

Task 2

Instructions. Implement a helper method with the following header:

private SortableLinkedList<T> split() {
  ...
}

This method cuts this linked list into two halves. The left half should remain in this, while the right half should be returned as its own linked list. This method should take no more than O(N) time.

Tests. After implementing this method, test it in the main method of the same file. You can store the results of all of your testing in SortableLinkedlistTesting.txt. We highly recommend you do not continue without confidence this method words correctly.

Task 3

Instructions. Implement a helper method with the following header:

private void reverse() {
  ...
}

As the name suggests, this method should reverse the order of the nodes in the linked list. This method should take no more than O(N) time.

Hint. You should be able to do this with a single while loop and without any additional data structures. If you wish, you may use a Queue or Stack from the Java API (only using the appropriate methods).

Tests. As before, after implementing this method, test it in the main method of the same file. We highly recommend you do not continue without confidence this method words correctly.

Task 4

Instructions. Implement a helper method with the following header:

private void merge(SortableLinkedList<T> right) {
  ...
}

This method takes in a second linked list, right, and merges into this linked list, using merge-sort’s merge algorithm. This method should take no more than O(N) time.

Hints.

• You may want to create a new linked list to contain the merged elements. Then, you can assign its contents to this.
• You should do this without any pointer manipulation, only relying on other methods of the linked list.
• Consider using the helper methods you’ve already implemented.

Tests. As before, after implementing this method, test it in the main method of the same file. We highly recommend you do not continue without confidence this method words correctly.

Task 5

Instructions. Finally, implement merge sort:

public void sort() {
  ...
}

Hint. Every helper method above you haven’t yet used will be helpful here.

Tests. Don’t forget to test your sorting algorithm! For ease of checking your code, you may want to sort something simple, like integers, instead of strings:

SortableLinkedList<Integer> l = new SortableLinkedList<Integer>();
l.insert(0, 0);
...

Submission Checklist

• You submitted all .java files and all .txt files.
• Your files are named exactly as in the homework specification, including file extensions.
• You tested every possible pathway in your code.
• You signed every class (or file) with @author and @version, accompanied by a description of what the class does.
• You wrote javadoc for every function, which includes @param and @return.
• You wrote inline comments explaining the logic of your code.

Homework 8, Part B: Tree Recursion

Learning Goals

Practice recursive tree algorithms

Tasks

First, create a BlueJ project with the following starter code.

BTNode.java:

import java.util.LinkedList;

public class BTNode { protected T element; protected BTNode left, right;

public BTNode(T elmt) {
    element = elmt;
    left = right = null;
}

public T getElement() { 
    return element; 
}

public void setElement(T element)
{ this.element = element; }

public BTNode<T> getLeft() { 
    return left; 
}

public void setLeft(BTNode<T> left) { 
    this.left = left; 
}

public BTNode<T> getRight() { 
    return right; 
}

public void setRight(BTNode<T> right) {
    this.right = right; 
}

public BTNode<T> find(T target) {
    BTNode<T> result = null;

    if (element.equals(target)) {
        result = this;
    } else {
        if (left != null)
            result = left.find(target);
        if (result == null && right != null)
            result = right.find(target);
    }

    return result;
}

public int count() {
    int result = 1;

    if (left != null)
        result = result + left.count();

    if (right != null)
        result = result + right.count();

    return result;
}

BSTNode.java:

public class BSTNode<T extends Comparable> extends BTNode {

public BSTNode(T element) {
    super(element);
}

public void add(T item) {
    if (item.compareTo(element) < 0) {
        if (left == null)
            left = new BSTNode(item);
        else //  Add recursively 
            ((BSTNode) left).add(item);
    } else { //  item >= element, go right
        if (right == null)
            right = new BSTNode (item);
        else //  Add recursively 
            ((BSTNode) right).add (item);
    }
}

public BSTNode<T> find(T target) {
    if (target.compareTo(element) == 0)
        return this;
        
    // Since left and right are defined as BTNodes in the parent class,
    // we cast them to BSTNodes here so we can call compareTo
    BSTNode<T> l = (BSTNode<T>) left;
    BSTNode<T> r = (BSTNode<T>) right;
    
    if (target.compareTo(element) < 0 && l != null) {
        return l.find(target);
    }
        
    if (r != null) {
        return r.find(target);
    }
    
    return null;
} }

Next, implement the following instance methods:

Implement public int countLeaves() in the BTNode class. This method should return an integer counting the number of leaves in tree.
Implement public int countNodesAtLevel(int level) in the BTNode class. This method should return the number of nodes at a given level in the tree. In this method, we’ll say that level 0 represents the root.
Implement public LinkedList<T> collectOnlyChildren() in the BTNode class. This method should return a list of all elements T that belong to nodes that have no siblings.
Implement public boolean isValid() in the BSTNode class. This method should return true if the tree is a valid binary search tree.

Please test your code as you go, putting your test in a driver class called Driver.java.

Submission Checklist

You submitted all .java files and all .txt files.
Your files are named exactly as in the homework specification, including file extensions.
You tested every possible pathway in your code.
You signed every class (or file) with @author and @version, accompanied by a description of what the class does.
You wrote javadoc for every function, which includes @param and @return.
You wrote inline comments explaining the logic of your code.