LinkedList

LinkedList.java

package org.metareal;
import java.util.NoSuchElementException;


public class LinkedList <E> {

	private final Node<E> head;
	private Node<E> tail;

	public LinkedList() {
		head = new Node<E>(null);
	}
	
	public int size() {
		int n = 0;
		for (Node<E> node = head.next; node != null; node = node.next) n++;
		return n;
	}

	public void add(E element) {
		final Node<E> node = new Node<E>(element);
		final Node<E> prev = (this.tail != null) ? tail : this.head;

		prev.next = node;
		this.tail = node;
	}

	public void addFirst(E element) {
		final Node<E> node = new Node<E>(element);
		node.next = head.next;
		head.next = node;
	}
	
	public E get(int index) {
		Node<E> node = head.next;
		for (int i = 0; i < index; i++) node = node.next;
		if (node == null) throw new IndexOutOfBoundsException(); 
		return node.element;
	}

	public boolean isEmpty() {
		return head.next == null;
	}
	
	public E removeFirst() {
		if (isEmpty()) throw new NoSuchElementException();
		final Node<E> node = head.next;
		head.next = node.next;
		node.next = null;
		if (tail == node) tail = null;
		return node.element;
	}
	
	private static final class Node <E> {
		public Node<E> next;
		public E element;
		
		public Node(E element) {
			this.element = element;
		}
	}
}

LinkedListTest.java

package org.metareal;
import junit.framework.TestCase;


public class LinkedListTest extends TestCase {

	public void test_empty() {
		LinkedList<?> list = new LinkedList<Object>();
		assertNotNull(list);
		assertTrue(list.isEmpty());
		assertEquals(0, list.size());
	}

	public void test_add() {
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		list.add(1);
		list.add(2);
		list.add(3);
		assertEquals(3, list.size());
		assertEquals(new Integer(1), list.get(0));
		assertEquals(new Integer(2), list.get(1));
		assertEquals(new Integer(3), list.get(2));
	}
	
	public void test_addFirst() {
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		list.addFirst(1);
		list.addFirst(2);
		list.addFirst(3);
		assertEquals(3, list.size());
		assertEquals(new Integer(1), list.get(2));
		assertEquals(new Integer(2), list.get(1));
		assertEquals(new Integer(3), list.get(0));
	}
	
	public void test_isEmpty() {
		LinkedList<Integer> list = new LinkedList<Integer>();

		assertTrue(list.isEmpty());
		list.add(123);
		assertFalse(list.isEmpty());
		list.removeFirst();
		assertTrue(list.isEmpty());
		list.add(123);
		assertFalse(list.isEmpty());
	}
	
	public void test_removeFirst() {
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		list.add(1);
		list.add(2);
		list.add(3);
		assertEquals(3, list.size());
		assertEquals(new Integer(1), list.removeFirst());
		assertEquals(new Integer(2), list.removeFirst());
		assertEquals(new Integer(3), list.removeFirst());
		assertEquals(0, list.size());
	}

}