Comp 271 lab 5 - simple linked lists
Goals
- dynamic allocation
- first look at linked lists
Overview
Consider my simple linked list demo, available at linkedlist.zip. You are to add the following methods to the class:
- int size(): returns the length of the list. You will have to count!
- T get(int n): retrieves contents of nth cell, with the numbering
starting at 0. It should return null if n is "out of range". I provided
a simple version that fails completely if n is out of range (ie n > size(). Your best bet is
to notice in the loop if p==null, and simply return null in that case.
- void set(int n, T val): update the value of the nth cell, if 0<=n<size(); do nothing otherwise.
- void insertAfter(int n, T val): inserts a new cell with value val following cell n. The cell formerly at position n+1 is now at position n+2.
- LinkedList reverse(): Note that this returns a new list representing the reversed list. Use clone() as a model; I recommend a reverseCells() method.
- Iterator<T> iterator(): actually, the iterator() method is
done, but you need to finish class ListIterator. As usual, this
involves making hasNext() and next() work properly. The "cursor" here
is the cell pointer current.
I have added a JUnit test class for unit testing,
which just means testing individual methods in a consistent,
reproduceable framework. For further information on this in BlueJ, see Unit Testing in BlueJ. For information on assertEquals(), etc, see junit.org/apidocs/org/junit/Assert.html.
The basic idea is New Class => Unit Test (I did this for you), and
then add tests, either automatically or manually. For the test
comparisons of calculated to expected values, you can use:
- assertEquals(val1, val2): checks if val1.equals(val2)
- assertSame(val1, val2): checks if val1 == val2, provided not null
- assertNull(val1), assertNotNull(val1)
- assertTrue(condition), assertFalse(condition)
I have added tests for all of the above (though my testing is not
complete; I didn't do much "negative" testing). Your program should
pass all the tests when it is done, unless some of the tests are
themselves broken. You are encouraged to add additional tests, though
for this assignment those will count for extra credit only.
To submit your project, create a zipfile and email it to me at
pld@cs.luc.edu.