Wellesley College
CS230: Data Structures in Java
Spring 2025

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

    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:


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.


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.

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);
...


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