CS1331 Linked List

Solution Description

You will be given an interface List representing the List ADT, which extends Iterable. Your LinkedList class will have to implement this interface. To create the LinkedList, you will also need to create a Node class and a custom iterator class, LinkedListIterator.

Important: Do NOT return objects of type Object or use raw types instead of generic types. An example of a raw type is ArrayList as opposed to ArrayList< String >.

List.java (provided)

This interface defines the List ADT and will contain methods that your LinkedList class must implement. The JavaDocs in this file will contain more information on the following methods you must implement:

• add(E element)
• add(int index, E element)
• remove(int index)
• remove(E element)
• remove()
• get(int index)
• contains(E element)
• set(int index, E element)
• clear()
• isEmpty()
• size()

Make sure you read the JavaDocs to see information on when to throw exceptions and what to return for edge cases.

This interface also extends the Iterable interface, so you must also implement the iterator() method. Refer to the Java API documentation for more information on this interface.

Note: You do NOT need to implement the forEach() and spliterator() methods of the Iterable interface for this assignment.

Node.java

This class will represent an individual node in your LinkedList. Most implementations of a LinkedList node only have two instance variables:

• data
  • This holds the actual data stored within a node
  • Since your LinkedList needs to be able to be created for any data type, your Node class needs to be generic, and the type of data should be the generic type T
  • Note: You can technically use any letter to denote your generic type. As a convention, we use T for "type" in most contexts and E for element when we are storing objects of a generic type in some sort of collection (such as an array, an ArrayList, or even your LinkedList)
• next
  • This will hold a reference to the next node in the LinkedList
  • These references are how the nodes in a LinkedList are connected, each node is connected to only one other node.
  • Since we are implementing a singly linked LinkedList, we don't need a reference to the previous node.

Ensure that you follow the principle of encapsulation and write getters and setters where necessary. You may write constructors to make your code more concise.

LinkedListIterator.java

In order to successfully implement the Iterable interface (which the provided List interface extends from), your LinkedList class must provide an implementation for the iterator() method. This method returns an instance of an Iterator for your data type. To successfully do this, we will create our own Iterator, LinkedListIterator, which implements the Iterator interface. An iterator is an object that allows you to loop over objects in a custom collection you create, such as our LinkedList. Note that this also needs to be a generic class, since it should iterate over a LinkedList of any type. This class will need to implement the following methods:

• hasNext()
  • Returns a boolean value specifying whether there are more elements to iterate over
• next()
  • Returns the next element in the LinkedList
  • This should return the data in the next node of the LinkedList, not the node itself
  • This method should return an object of the generic type
  • The first time you call next(), it should return the data of the first node of the LinkedList
  • Needs to throw a NoSuchElementException if there is no next element (already iterated through all of the elements).

Hint: What instance variables are needed? What arguments may the constructor take in to be able to iterate over a LinkedList?

LinkedList.java

This is the main file for your LinkedList and will utilize the previous two classes to satisfy the requirements of the List ADT. This class will implement all the methods from the List interface (including the iterator() method inherited from the Iterable interface). This class also needs to be generic.

Instance variables:

• size
• The number of nodes in your LinkedList=head
  • A reference to the head node of the LinkedList
  • Recall that the Node class is generic. What should the type of this instance variable be?

Methods:

In addition to the methods from the List interface, implement the following methods:

• Constructors:
  • A no-arguments constructor that initializes an empty LinkedList
  • A constructor that takes in an array of elements of the generic type and creates a LinkedList from those elements
• removeDuplicates()
  • This method should go through the list and remove any duplicate nodes (nodes with the same data).
  • After this method is called, each node in the list should have unique data.
  • This method will not return anything
• toArray()
  • Return the elements of the LinkedList as an array.
  • Note: The head of your LinkedList should be the first element of the array (index 0 of the array) that is returned.
  • Note: You must be careful when trying to create a generic array in Java. The intuitive approach of E[] arr = new E[size] causes a compile error (the details of why exactly that happens are out of the scope of this homework). Instead, to create a generic array you must create an array of objects and cast that to a generic array, like E[] arr = (E[]) new Object[size]

List.java

import java.util.NoSuchElementException;

/**
* List Abstract Data Type.
*/
public interface List< E > extends Iterable< E > {

/**
* Inserts the element at the front of the list.
*
* @param element data we are adding to the list
* @throws IllegalArgumentException if the passed in element is null
*/
void add(E element) throws IllegalArgumentException;

/**
* Inserts the element at the specified index.
*
* @param index index to add the element
* @param element data we are adding to the list
* @throws IllegalArgumentException if the passed in element is null
* @throws IndexOutOfBoundsException if the passed in index is invalid. index == list.size() is valid
*/
void add(int index, E element) throws IllegalArgumentException, IndexOutOfBoundsException;

/**
* Removes the element at the specified index and returns it.
*
* @param index index of element to be removed
* @return the removed element at the specified index
* @throws IndexOutOfBoundsException if the passed in index is invalid
*/
E remove(int index) throws IndexOutOfBoundsException;

/**
* Removes the specified element from the list and returns it.
*
* @param element data to be removed
* @return the removed element from the list
* @throws NoSuchElementException if the passed in element is not in the list
*/
E remove(E element) throws NoSuchElementException;

/**
* Removes the head (first element) from the list and returns it.
*
* @return the removed element from the head of the list, null if the list is empty
*/
E remove();

/**
* Returns the element at the specified index.
*
* @param index index of the element to return
* @return element at the specified index
* @throws IndexOutOfBoundsException if the passed in index is invalid
*/
E get(int index) throws IndexOutOfBoundsException;

/**
* Checks if a list contains a specific element.
*
* @param element data to check for in list
* @return boolean representing if the list has the element or not
*/
boolean contains(E element);

/**
* Replaces the element at a specific index with the passed in data.
*
* @param index index of the element to replace
* @param element the element to set
* @return element that has been replaced
* @throws IndexOutOfBoundsException if the passed in index is invalid
* @throws IllegalArgumentException if the passed in element is null
*/
E set(int index, E element) throws IndexOutOfBoundsException, IllegalArgumentException;

/**
* Clears the list.
*/
void clear();

/**
* Checks if the list is empty.
*
* @return true if the list is empty, false otherwise
*/
boolean isEmpty();

/**
* Returns the number of elements in the list.
*
* @return int representing size of list
*/
int size();
}