This is a linked list class that we have written, with JUnit tests.
/**
OurList interface is modeled after the List interface in the
Java Collections Framework. The prefix "Our" is to avoid name
clashes with the standard Java interfaces and classes.
Author: Elena Machkasova
Purpose: to be used in CSci 2101 UMM course
**/
public interface OurList<E> extends Iterable<E> {
/**
* @return true if this list contains no elements,
* false otherwise
*/
public boolean isEmpty();
/**
* Returns the number of elements in this list.
* @return the number of elements in this list
*/
public int size();
/**
* Inserts the specified element at the specified index in this list
* @param index - the index where to insert the element
* @param item - the item to be inserted
* @throws ListIndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).
*/
public void add(int index, E item) throws ListIndexOutOfBoundsException;
/**
* Returns the element at the specified position in this list.
* @param index - the index of the element to be returned
* @return - the element at the specified position in this list.
* @throws ListIndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).
*/
public E get(int index) throws ListIndexOutOfBoundsException;
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their indices).
* @param index - the index of the element to removed.
* @throws ListIndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).
*/
public void remove(int index) throws ListIndexOutOfBoundsException;
/**
* Removes all of the elements from this list (optional operation).
* This list will be empty after this call returns.
* @return
*/
public void clear();
}
public class ListIndexOutOfBoundsException extends Exception {
/**
Constructor that sets the message
**/
public ListIndexOutOfBoundsException(String message) {
// passing the message to the constructor of the superclass
super(message);
}
}
import java.util.Iterator;
public class OurLinkedList<E> implements OurList<E> {
private Node first;
private int size = 0;
public OurLinkedList() {
first = null; // list is created empty
}
/**
* @return true if this list contains no elements, false otherwise
*/
@Override
public boolean isEmpty() {
return (first == null);
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
@Override
public int size() {
return size;
}
/**
* Inserts the specified element at the specified index in this list
*
* @param index
* - the index where to insert the element
* @param item
* - the item to be inserted
* @throws ListIndexOutOfBoundsException
* - if the index is out of range (index < 0 || index > size()).
*/
@Override
public void add(int index, E item) throws ListIndexOutOfBoundsException {
Node newNode = new Node(item, null);
Node currentNode = first;
if (index < 0) {
throw new ListIndexOutOfBoundsException("Index " + index + " is invalid in a list of size " + size);
} else if(index == 0){
newNode.next = currentNode;
first = newNode;
size++;
} else {
for (int i = 0; i < index - 1; i++) {
//stops at the node before the index, so that the new node could be attached to it
if (currentNode == null){
throw new ListIndexOutOfBoundsException("Index " + index + " is invalid in a list of size " + size);
}
currentNode = currentNode.next;
}
Node nextNode = currentNode.next;
currentNode.next = newNode;
newNode.next = nextNode;
size++;
}
}
/**
* Returns the element at the specified position in this list.
*
* @param index
* - the index of the element to be returned
* @return - the element in the given position in this list.
*
* @param index
* - the index of the element to be returned
* @return - the element at the specified position in this list.
* @throws ListIndexOutOfBoundsException
* - if the index is out of range (index < 0 || index >=
* size()).
*/
@Override
public E get(int index) throws ListIndexOutOfBoundsException {
if(index >= size) {
throw new ListIndexOutOfBoundsException("Index: " + index +
" is out of bounds! The list is only " + size + " element(s) long!");
}
else if(index < 0) {
throw new ListIndexOutOfBoundsException("Index cannot be negative: " + index);
}
else {
Node currentNode = first;
for(int i = 0; i < index; i++){
currentNode = currentNode.next;
}
return currentNode.element;
}
}
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
*
* @param index
* - the index of the element to removed.
* @throws ListIndexOutOfBoundsException
* - if the index is out of range (index < 0 || index >=
* size()).
*/
@Override
public void remove(int index) throws ListIndexOutOfBoundsException {
if ((size == 0) || (size <= index)) {
throw new ListIndexOutOfBoundsException(
"Trying to remove a non-existent element.");
} if (index == 0) {
first = first.next;
size--;
} else {
Node previousNode = first;
int i = 1;
while (i < index) {
previousNode = previousNode.next;
i++;
}
previousNode.next = previousNode.next.next;
size--;
}
}
/**
* Removes all of the elements from this list (optional operation). This
* list will be empty after this call returns.
*
* @return
*/
@Override
public void clear() {
first = null;
size = 0;
}
private class Node {
private E element;
private Node next;
public Node(E element, Node next){
this.element = element;
this.next = next;
}
}
@Override
public Iterator<E> iterator() {
// TODO Auto-generated method stub
// return null;
return new ListIterator();
}
// added the iterator class
private class ListIterator implements Iterator<E> {
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
@Override
public E next() {
// TODO Auto-generated method stub
return null;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
}
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;
public class LinkedListTests {
OurList<Integer> emptyList; // a global variable, visible to all methods
OurList<Integer> threeElementsInOrder;
OurList<Integer> threeElementsNotInOrder;
@Before
public void createLists() throws ListIndexOutOfBoundsException{
emptyList = new OurLinkedList<Integer>();
threeElementsInOrder = new OurLinkedList<Integer>();
// elements added to indices 0, 1, 2, in this order
threeElementsInOrder.add(0, 5);
threeElementsInOrder.add(1, 7);
threeElementsInOrder.add(2, 3);
// elements added out of order
threeElementsNotInOrder = new OurLinkedList<Integer>();
threeElementsNotInOrder.add(0, 3);
threeElementsNotInOrder.add(0, 5);
threeElementsNotInOrder.add(1, 7);
}
@Test
public void testEmptyList() {
assertTrue(emptyList.isEmpty());
assertEquals(0,emptyList.size());
}
@Test
public void testElementsAddedInOrder() throws ListIndexOutOfBoundsException {
assertFalse(threeElementsInOrder.isEmpty());
assertEquals(3, threeElementsInOrder.size());
assertEquals(new Integer(5), threeElementsInOrder.get(0));
assertEquals(new Integer(7), threeElementsInOrder.get(1));
assertEquals(new Integer(3), threeElementsInOrder.get(2));
}
@Test
public void testRemoveLastElementsAddedInOrder() throws ListIndexOutOfBoundsException {
threeElementsInOrder.remove(2);
assertEquals(2, threeElementsInOrder.size());
assertEquals(new Integer(5), threeElementsInOrder.get(0));
assertEquals(new Integer(7), threeElementsInOrder.get(1));
}
@Test
public void testRemoveFirstElementsAddedInOrder() throws ListIndexOutOfBoundsException {
threeElementsInOrder.remove(0);
assertEquals(2, threeElementsInOrder.size());
assertEquals(new Integer(7), threeElementsInOrder.get(0));
assertEquals(new Integer(3), threeElementsInOrder.get(1));
}
@Test
public void testRemoveAllAddedInOrder() throws ListIndexOutOfBoundsException {
threeElementsInOrder.remove(2);
threeElementsInOrder.remove(0);
threeElementsInOrder.remove(0);
assertEquals(0, threeElementsInOrder.size());
assertTrue(threeElementsInOrder.isEmpty());
}
@Test
public void testElementsAddedNotInOrder() throws ListIndexOutOfBoundsException {
assertFalse(threeElementsNotInOrder.isEmpty());
assertEquals(3, threeElementsNotInOrder.size());
assertEquals(new Integer(5), threeElementsNotInOrder.get(0));
assertEquals(new Integer(7), threeElementsNotInOrder.get(1));
assertEquals(new Integer(3), threeElementsNotInOrder.get(2));
}
@Test
public void testRemoveLastElementsAddedNotInOrder() throws ListIndexOutOfBoundsException {
threeElementsNotInOrder.remove(2);
assertEquals(2, threeElementsNotInOrder.size());
assertEquals(new Integer(5), threeElementsNotInOrder.get(0));
assertEquals(new Integer(7), threeElementsNotInOrder.get(1));
}
@Test
public void testRemoveFirstElementsAddedNotInOrder() throws ListIndexOutOfBoundsException {
threeElementsNotInOrder.remove(0);
assertEquals(2, threeElementsNotInOrder.size());
assertEquals(new Integer(7), threeElementsNotInOrder.get(0));
assertEquals(new Integer(3), threeElementsNotInOrder.get(1));
}
@Test
public void testRemoveAllAddedNotInOrder() throws ListIndexOutOfBoundsException {
threeElementsNotInOrder.remove(2);
threeElementsNotInOrder.remove(0);
threeElementsNotInOrder.remove(0);
assertEquals(0, threeElementsNotInOrder.size());
assertTrue(threeElementsNotInOrder.isEmpty());
}
// Testing for exceptions (one per test)
@Test (expected=ListIndexOutOfBoundsException.class)
public void testExceptionAdd() throws ListIndexOutOfBoundsException {
threeElementsInOrder.add(5, 8);
}
// this test fails!
@Test (expected=ListIndexOutOfBoundsException.class)
public void testExceptionAddOnePastSize() throws ListIndexOutOfBoundsException {
threeElementsInOrder.add(threeElementsInOrder.size() + 1, 8);
}
@Test (expected=ListIndexOutOfBoundsException.class)
public void testExceptionGet() throws ListIndexOutOfBoundsException {
threeElementsInOrder.get(threeElementsInOrder.size());
}
@Test (expected=ListIndexOutOfBoundsException.class)
public void testExceptionGetNegative() throws ListIndexOutOfBoundsException {
threeElementsInOrder.get(-1);
}
@Test (expected=ListIndexOutOfBoundsException.class)
public void testExceptionRemove() throws ListIndexOutOfBoundsException {
threeElementsInOrder.get(threeElementsInOrder.size());
}
// add tests for iterating over the lists
@Test
public void testIterator() {
Integer[] results = {5, 7, 3};
int i = 0;
for (Integer item: threeElementsInOrder) {
assertEquals(results[i], item);
i++;
}
}
@Test
public void testIteratorSum() {
int sum = 0;
for (Integer item: threeElementsInOrder) {
sum = sum + item;
}
assertEquals(15, sum);
}
}