Homework 7, 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;
    }

    /**
     * Returns the node at the specified position.
     *
     * If position is less than 0 or greater than or equal to the size
     * of the list, this method returns null.
     *
     * @param position the 0-indexed position of the node
     * @return the node at the specified position, or null if position
     *         is not valid
     */
    protected LinearNode<T> getNode(int position) {
        if (position < 0 || position >= this.count) {
            return null;
        }
        
        LinearNode<T> current = this.front;
        for (int i = 0; i < position; i++) {
            current = current.getNext();
        }
        
        return current;
    }
    
    /**
     * Returns the element at the specified position.
     *
     * If position is less than 0 or greater than or equal to the size
     * of the list, this method returns null and leaves the list unchanged.
     *
     * @param position the 0-indexed position of the element
     * @return the element at the specified position, or null if position
     *         is not valid
     */
    public T get(int position) {
        LinearNode<T> node = this.getNode(position);
        if (node == null) {
            return null;
        }
        
        return node.getElement();
    }
    
    /**
     * Inserts an element at the specified position.
     *
     * Valid positions range from 0 through the size of the list,
     * inclusive. Inserting at position size() adds the element to the end
     * of the list.
     *
     * If position is less than 0 or greater than the size of the list,
     * this method leaves the list unchanged.
     *
     * @param position the position at which to insert the element
     * @param element the element to insert
     */
    public void insert(int position, T element) {
        if (position < 0 || position > this.count) {
            return;
        }
        
        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++;
    }
    
    /**
     * Removes and returns the element at the specified position.
     *
     * If position is less than 0 or greater than or equal to the size
     * of the list, this method returns null and leaves the list unchanged.
     *
     * @param position the 0-indexed position of the element to remove
     * @return the removed element, or null if position is not valid
     */
    public T remove(int position) {
        if (position < 0 || position >= this.count) {
            return null;
        }
        
        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();
    }

    /**
     * Returns a String representation of the list.
     *
     * @return a String representation of the list
     */
    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 works 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 works 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 works 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);
...

Homework 7, Part B: Big-O

Consider the following method that removes a CD from a linear collection (e.g. array):

code to remove a CD from an array

Assume that the collection has N CDs to start with. Please write the Big-O of every line marked in the code. For lines inside a loop, please write the Big-O of the line, accounting for its repetition. Write your answer in a text file called BigO.txt and submit it.

Note: If you find any of the questions ambiguous (that is, if you believe there are multiple interpretations), give your answer for each interpretation.

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.