/*
* Title: class LinkedList
* Description: Simple Linked List class to demonstrate the basic principles
* of implementing a linked list. This should not be taken as a production
* quality class (see the text book instead).
* Copyright: Copyright (c) 2002
* Company: Dept. of Computer Science, University College London
* @author Graham Roberts
* @version 1.0 01-Mar-02
*/
{
/**
* A list is a chain of ListElement objects. head references
* the first object in the chain or is null if the list is
* empty.
*/
private ListElement head;
/**
* Helper class used to implement list chain. As this is a private helper
* class it is acceptable to have public instance variables. Instances of
* this class are never made available to client code of the list.
*/
private static class ListElement
{
/**
* Next node in chain reference.
*/
public ListElement next;
/**
* Data object reference.
*/
public Object val;
/**
* Constructor for ListElement.
*
*@param next next node in chain reference or null
*@param val data object reference
*/
public ListElement(ListElement next, Object val)
{
this.next = next;
this.val = val;
}
/**
* Recursive helper method to copy a chain of ListElements.
*
*@return reference to copied chain of elements.
*/
public ListElement copy()
{
return new ListElement(next == null ? null : next.copy(), val);
}
}
/**
* Constructor for LinkedList.
*/
public LinkedList()
{
head = null;
}
/**
* Private helper constructor for LinkedList to quickly construct
* a new list given a chain of elements.
*
*@param e reference to element chain forming the list to be held by
* the new list object. The chain is not copied.
*/
private LinkedList(ListElement e)
{
head = e;
}
/**
* Insert a new value at the head of the list.
*
*@param val data object reference to insert.
*/
public void insertHead(Object val)
{
head = new ListElement(head, val);
}
/**
* Return object at head of list. The list is unchanged.
*
*@return reference to object at head of list or null if the
* list is empty.
*/
public Object getHead()
{
if (head == null)
{
return null;
}
else
{
return head.val;
}
}
/**
* Return tail of list - the list that is the copy of the current
* list minus the head element.
*
*@return a new list that is a copy of the current list minus the head
* element, or an empty list if there is no tail.
*/
public LinkedList getTail()
{
if ((head == null) || (head.next == null))
{
return new LinkedList();
}
return new LinkedList(head.next.copy());
}
/**
* Test to see if list is empty.
*
*@return true if list is empty, false otherwise.
*/
public boolean isEmpty()
{
return head == null;
}
/**
* Iterator class for List to allow each list element to be
* visited in sequence. The iterator class is nested in the list class
* and is non-static meaning it has access to the state of the
* list object being iterated. The iterator is also public so iterator
* objects can be used by client code. As the class is nested, clients
* need to use the name LinkedList.Iterator to refer to the iterator
* class.
*/
public class Iterator
{
/**
* Instance variable used to store the current position of the iteration.
* Note that it will be initialised to the head reference of the
* LinkedList that creates the iterator (the nested iterator class is
* in the scope of the LinkedList class, so the variable head is in scope).
*/
private ListElement current = head;
/**
* Determine if there is another element in the sequence, i.e.,
* another value in the list.
*
*@return true if another element in the sequence is available, false
* otherwise.
*/
public boolean hasNext()
{
return current != null;
}
/**
* Return the object reference of the next value in the list. The position
* is moved forward before the value is returned.
*
*@return the next object reference in the sequence or null if at the end
* of the sequence.
*/
public Object next()
{
Object temp = null;
if (current != null)
{
temp = current.val;
current = current.next;
}
return temp;
}
}
/**
* Return a new Iterator object for the current list.
*
*@return new iterator reference.
*/
public Iterator iterator()
{
return new Iterator();
}
}
JUnit test class for class LinkedList
/*
* Title: class LinkedListTest
* Description: JUnit test class for LinkedList class
* Copyright: Copyright (c) 2002
* Company: Dept. of Computer Science, University College London
* @author Graham Roberts
* @version 1.0 01-Mar-02
*/
import junit.framework.* ;
public class LinkedListTest extends TestCase
{
private LinkedList empty ;
private LinkedList one ;
private LinkedList several ;
public LinkedListTest(String s)
{
super(s) ;
}
public void setUp()
{
empty = new LinkedList() ;
one = new LinkedList() ;
one.insertHead(new Integer(0)) ;
several = new LinkedList() ;
several.insertHead(new Integer(2)) ;
several.insertHead(new Integer(1)) ;
several.insertHead(new Integer(0)) ;
}
public void testGetHead()
{
assertEquals("Check 0",new Integer(0),one.getHead()) ;
assertEquals("Check 0",new Integer(0),several.getHead()) ;
assertEquals("Check 1",new Integer(1),several.getTail().getHead()) ;
assertEquals("Check 2",new Integer(2),several.getTail().getTail().getHead()) ;
}
public void testEmpty()
{
LinkedList temp = empty.getTail() ;
assertNull("Check empty getHead null",empty.getHead()) ;
assertTrue("Check empty getTail",temp.isEmpty()) ;
assertTrue("Check one getTail",one.getTail().isEmpty()) ;
assertTrue("Check several getTail x 3",several.getTail().getTail().getTail().isEmpty()) ;
}
public void testAddRemoveAdd()
{
one = one.getTail();
assertTrue("one empty",one.isEmpty()) ;
one.insertHead(new Integer(0));
assertEquals("Check remove then add 0",new Integer(0),one.getHead()) ;
}
public void testIterator()
{
int counter = 0 ;
for (LinkedList.Iterator iterator = empty.iterator() ; iterator.hasNext(); )
{
fail("Iterating empty list and found element") ;
}
counter = 0 ;
for (LinkedList.Iterator iterator = several.iterator() ; iterator.hasNext(); )
{
assertEquals("Check several iteration",new Integer(counter++),(Integer)iterator.next()) ;
}
}
public static Test suite()
{
return new TestSuite(LinkedListTest.class) ;
}
public static void main (String[] args)
{
junit.textui.TestRunner.run(suite()) ;
}
}
Posts
No comments:
Post a Comment