Linked List Exercise

In this exercise, you will implement a Linked List. We will build up to this in parts.

Part 1: Familiarize Yourself with the Code

The LinearNode Class. Recall the LinearNode class from lecture:

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

For this class:

• What does element represent?
• What does next represent?
• Why is the type of next also a LinearNode<T>?
• What is T used for?

The LinearList Interface. Next, consider the interface below:

public interface LinearList<T> {
    /**
     * Checks if the list is empty
     * 
     * @return true if the list is empty, false otherwise
     */
    public boolean isEmpty();
    
    /**
     * Returns the size of the list
     * 
     * @return the size (or length) of the list
     */
    public int size();

    /**
     * Returns the element at the specified position from the list
     *
     * @param index of the element in the list
     * @return the element to be returned
     */
    public T get(int position);

    /**
     * Inserts an element at the given position in the list.
     * 
     * @param the index of the element to be added
     * @param the element to be added
     */
    public void insert(int position, T element);
    
    /**
     * Removes the element at the specified position from the list
     * 
     * @return the element to be returned
     */
    public T remove(int position);

    /**
     * Generates a String representation of list; 
     * first element in the representation is the front
     * 
     * @return a String representation of the list
     */
    public String toString();
}

Then, answer:

• What are interfaces used for?
• What does it mean to create an object that implements this interface?

The InvalidOperationException. Below is a class that implements an exception that should be thrown when a client tries to do something invalid with your list:

public class InvalidOperationException extends RuntimeException {
   public InvalidOperationException(String message) {
      super(message);
   }
}

Answer: which methods in the LinearList interface should throw this exception? Why?

Part 2: Creating a BlueJ Project

Create a new BlueJ project and create a .java file for each of the above code snippets.

Part 3: Implement a Linked List

Create a new class, LinkedList<T> that satisfies the following:

1. It uses the LinearNode<T> class above.
2. It implements the LinearList<T> interface above.

For brevity, we won’t ask you to thoroughly test your code. However, we do recommend that you:

1. Implement the toString method early on.
2. Use the toString method to check your other methods work.

Please write pseudo-code on the whiteboards for all methods before implementing them in Java.

Part 4: Concatenation

Although your LinkedList<T> must implement the LinearList<T> interface, it can additionally have other methods. Please implement an instance method, concatenate, that takes in a LinkedList<T> other as argument and:

1. Appends other to the end of the linked list.
2. Empties out other.

As before, please write pseudo-code on the whiteboards before writing code on the computer.

After implementing this method, answer: what would concatenate look like for an array-based list? And is it more or less efficient than your linked-based implementation? Why?