Linked List Written in Class and Unit Tests

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

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.