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

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.

For this task, you will choose your own partner!

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: Trees (individual)

Exercise: Tree Terminology

This exercise tests your understanding of some definitions for trees. Consider the following tree:

Produce a preorder traversal of this tree.
Produce an inorder traversal of this tree.
Produce a postorder traversal of this tree.
Produce a level-order traversal of this tree.
Draw an array to represent this tree using the computed links implementation strategy.
Draw an array to represent this tree using the stored links implementation strategy. For this question, place the nodes in the array in alphabetical order. Use -1 to denote the location of a child that does not exist.
What is the big-O time complexity of the find operation in the LinkedBinaryTree class?
What is the time complexity of the inorder operation in the LinkedBinaryTree class?

What to submit

Submit to gradescope a single file, TreeTerminology.pdf, containing your answers.