Description
IMPORTANT:
This project utilizes similar concepts and java skills to Project 2. For brevity,
this write-up omits discussions of generics and interfaces. For more information, see the
instructions for Project 2.
In this project you are going to implement a list [1] interface to construct your own LinkedList
data structure. Using this you will construct an ElephantHerd to hold a family of elephants [2].
1.1 LinkedList Implementation
The first part of this project will be to implement a linked list. Create a class LinkedList that
implements all the methods in List interface. Recall that to implement the List interface and use
the generic compatibility with your code, LinkedList should have following structure:
public class LinkedList> implements List {
…
}
The underlying structure of a linked list is a node. This means you will have an instance variable
that is the first node of the list. The provided Node.java contains a generic node class that you
will use for your linked list implementation∗
.
Your LinkedList class should have a single constructor:
public LinkedList() {
…
}
that initializes the list to an empty list.
Implementation Details
• In addition to the methods described in the List interface, the LinkedList class should
contain a private class variable isSorted. This should be initialized to true in the constructor
(because it is sorted if it has no elements) and updated when the list is sorted, or more elements
∗ You may implement your linked list as a headed list, i.e., the first node in the list is a ‘dummy’ node and the
second node is the first element of the list, or a non-headed list, i.e., the first node is the first element of the list.
Depending on how you choose to implement your list, there will be some small nuances.
3
are added or set. For the purposes of this class, isSorted is only true if the list is sorted in
ascending order.
• Initially and after a call to clear(), the size should be zero and your list should be empty.
• In sort(), do not use an array or ArrayList to sort the elements. You are required to
sort the values using only the linked list data structure. You can move nodes or swap values
but you cannot use an array to store values while sorting.
• Depending on your implementation, remember that after sorting, the former first node may
not be the current first node.
After you have implemented your LinkedList class, include junit tests that test all functionality.
2 An Elephant Herd
Slightly modify your class ElephantHerd from Project 2 to use an underlying LinkedList rather
than an ArrayList. Then verify that the methods still work as intended.
If you did the previous project correctly, this step should only require the modification of one line
of code.
3 Analysis
Now that you have implemented and used both an array list and linked list, which one is better?
Which methods in List are more efficient for each implementation?
For each of the 13 methods in List, compare the runtime (Big-O) for each method and implementation. Ignore any increased efficiency caused by the flag isSorted. Include an analysis.txt
or analysis.pdf with your submission structured as follows:
Method ArrayList Runtime LinkedList Runtime Explanation
boolean add(T element) O(…) O(…) …
boolean add(int index, T element) O(…) O(…) …
.
Your explanation for each method only needs to be a couple sentences briefly justifying your
runtimes.
4
4 Iterators (Honors)
Note: This section is **required** for students in Honors section only. Optional for others but no
extra credit.
Much like in Project 2, you will create an iterator for the LinkedList class.
This section will require you to write another class, and to make modifications to the LinkedList
class.
You will write a LinkedListIterator class which will iterate over a list. This iterator should
implement java’s iterator interface in addition to the List interface. Make sure to import
java.util.Iterator. This class will have two functions and a constructor. It will also need class
variables to store a pointer to its LinkedList and the current index.
1. LinkedListIterator(LinkedList a) – the constructor. This constructor will never be directly called by the user. Instead, it will be called in the iterator() function in the LinkedList
class.
2. hasNext() – This will return true if there is another object to iterate on, and false otherwise.
3. next() – This will return the next object if there is one, and null otherwise.
The first line of the LinkedListIterator class should be as follows:
private class LinkedListIterator> implements Iterator
Note that in order for a class to be private, it must be in the same document as another class,
and within the curly braces of that class. This means that LinkedListIterator should be in
the LinkedList.java file, and should be in the curly braces of LinkedList, with the methods of
LinkedList.
You will also need to make some modification to the LinkedList class. First, the class now needs
to implement Iterable.
public class LinkedList> implements Iterable, List
Secondly, you will need to add the method public Iterator iterator(). This method should
return a LinkedListIterator object by calling the LinkedListIterator constructor and passing
itself to the constructor (via the this keyword).
Make sure to create junit tests to ensure that your iterator functions as desired.
5
