LinkedListImplementation — Your own implementation of a linked list
CSSE 221 – Fundamentals of Software Development Honors
Fall 2008–2009

This is an individual exercise. However, don't hesitate to ask questions of your instructor, student assistants and classmates as desired.

Goals

The goals of this exercise are to apply and hence reinforce your understanding of the use of:

• What a linked list is
• How a linked list is/contains a recursive data structure
• How to implement operations on a linked list, especially recursively

Overview

You will checkout a project that has stubs for a class called MyLinkedList that implements List.

• We will implement some of the methods together.
• You will implement others on your own.

I have supplied JUnit tests for your code.

Instructions

1. Checkout your LinkedListImplementation project from your individual respository. It has two classes:
   • Main -- use this for your informal testing. (I have supplied JUnit tests.)
   • MyLinkedList -- it has stubs that you will implement (see next step).
2. Implement the stubbed methods, testing each as you complete it. Important notes:

   • Implement the methods in the order that they appear (top to bottom).
   • Implement the stubs per the online documentation for List at

     	http://java.sun.com/javase/6/docs/api/java/util/List.html
     

     You do not need to throw any exceptions except DO throw IndexOutOfBoundsException wherever it is specified by the List interface.

   • We will implement the first several methods together.
   • You should obtain Node and MyLinkedListIterator classes as a result of our work together.
   • You are not required to implement all the methods -- you receive full credit if you (correctly) implement all the methods through and including toArray()
     • Thus, you do NOT have to do toArray(T[]) or anything past it.
   • The following methods (plus possibly other methods) should be implemented by having corresponding recursive methods in your Node class:
     • add(E element)
     • contains(Object o)
     • get(int index)
     • remove(int index)
     • add(int index, E element)
     • set(int index, E element)
     • indexOf(Object o)
     • addAll(Collection collection)
     • addAll(int index, Collection collection)
     • lastIndexOf(Object o)
     • remove(Object o)
   • Some of them methods are trickier than others. Just skip over those you are struggling with and bring your questions to class.
   • There is no report associated with this exercise.

3. When you are done, commit your LinkedListImplementationproject to turn it in.
   • Make sure that it obeys our code conventions -- use Source ~ Format if needed.
   • You need not supply ANY documentation -- it is all inherited from the List interface documentation or is private to your classes.