Wellesley College
CS230: Data Structures in Java
Fall 2025

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:

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 (0-indexed) 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 (0-indexed) 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:

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?


Part 5: LinkedStack (Extra/Time Dependent)

We can also use LinkedLists to implement other data structures. Consider the Stack interface below.

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

  1. It “has-a” LinkedList<T> (which you implemented above). (Question: why would you not want to use an “is-a” relationship here?)
  2. It implements the Stack<T> interface below.

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

The Stack Interface.

public interface Stack<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();

    /**
     * Pushes the given element onto the stack
     *
     * @param the element to be added
     */
    public void push(T element);

    /**
     * Removes (and returns) the element on the top of the stack.
     * 
     * @return the top element from the stack (which was removed) 
     */
    public T pop();
    
    /**
     * Returns the element on the top of the stack.
     * 
     * @return the top element from the stack (which was NOT removed) 
     */
    public T peek();

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