Lab:  Lists

Beware! The ListCruncher has come for your code!

Good news!! In this lab, you'll be implementing the List interface to make your very own ArrayList class! In the process, you'll learn how ArrayLists work, and when each method runs in constant or linear time.

Download and unzip listlab.zip, which contains the following files:

• List.java - This is the (simplified) List interface you'll be implementing

• MyArrayList.java - You must complete this class definition to earn up to 90%

• MyArrayListDisplay - Use this class to test MyArrayList.

• SinglyLinkedList.java - You may complete this class definition (in addition to MyArrayList) to earn additional credit.

• SinglyLinkedListDisplay.java - Use this class to test SinglyLinkedList.

• ListNode.java - You will use this if you complete the SinglyLinkedList class definition.

Reference:  List<E> interface

int size()
Returns the number of elements in the list

E get(int index)
Returns the element at position index in the list

E set(int index, E obj)
Replaces the element at position index with obj; returns the element

boolean add(E obj)
Appends obj to end of list; returns true

E remove(int index)
Removes element from position index, moving elements at position index + 1 and higher to the left (subtracts 1 from their indices) and subtracts 1 from size; returns the element formerly at position index

Background:  Using the List Interface

The following code illustrates the desired behavior of any class implementing the List interface.

List<String> fruit = new SomeClassThatImplementsTheListInterface<String>();

int n = fruit.size();  // returns 0

fruit.add("apple");

fruit.add("banana");

fruit.add("cherry");

n = fruit.size();  // returns 3

String x;

x = fruit.get(0);  //returns "apple"

x = fruit.get(1);  //returns "banana"

x = fruit.get(2);  //returns "cherry"

x = fruit.remove(1); //returns "banana"

n = fruit.size();  // returns 2

x = fruit.get(0);  //returns "apple"

x = fruit.get(1);  //returns "cherry"

x = fruit.set(0, "orange");  //returns "apple"

x = fruit.get(0);  //returns "orange"

Part 1:  MyArrayList (90%)

In this part, you will complete the MyArrayList class definition--which will work just like the real ArrayList class! MyArrayList implements the List interface shown above. From the outside, it behaves exactly like any other List (like the one shown in the "Background" section above). Inside, however, the MyArrayList class stores its data in an array. This poses a problem for us, because

• MyArrayList will need to grow (when the add method is called).

• An array cannot grow or shrink. Once the array is constructed, its length can never change.

Therefore, we will sometimes need to copy all the elements into a larger array. Unfortunately, it can take a long time to copy the elements from one array to another, and so we don't want to do this often. The solution is to store the data in an array with some extra room for adding more elements in the future. For example, the MyArrayList below stores 6 elements in an array of length 8.

Thus, the MyArrayList class will have two fields.

• data - an array that keeps track of the elements that have been added, followed by null values

• size - an int that keeps track of the number of elements in the MyArrayList (so that we don't have to count the non-null values in the array)

Whenever an element is added, it replaces the first null value, and the size variable is incremented. The following illustration shows the MyArrayList, after "G" has been added to the list.

Adding "H" to the list is not a problem, since we still have room for one more element.

However, in order to add "I" now, we must copy all the elements into a larger array. The new array will always be TWICE AS LARGE as the original array. (That way we won't need to make a larger array for a long time.)

Go ahead and complete the MyArrayList class definition, so that it works as described above. You will need to implement each of the methods in the List interface. It is recommended that you implement the easier methods (size, get, set) before moving onto the more challenging ones (add and remove). (Note that the remove method never constructs a new array.) Your code must run in the following running times.

size, get, set: constant time
add: constant time (assuming the array has room)
remove: linear time when removing elements near the beginning or middle of the list, but constant time when removing elements near the end of the list

Note: See the constructor for an example of the ridiculous Java syntax required to construct an array of type E. You'll need this for the add method.

Test your code by running MyArrayListDisplay. You can use the Fill with test data button to help you test the size, get, and set methods before you have finished writing add and remove, as long as all your methods compile.

Challenge (1%): Implement the following method in MyArrayList.

void add(int index, E obj)
inserts obj at position index (0 <= index <= size), moving elements at position index and higher to the right (adds 1 to their indices) and adjusts size

This method must run in linear time when adding elements in the beginning or middle of the list, and it must run in constant time when adding elements near the end of the list (assuming the array has room)

Part 2:  SinglyLinkedList (4%)

In this part, you will complete the SinglyLinkedList class definition. SinglyLinkedList implements the List interface shown above. From the outside, it behaves exactly like any other List (like the one shown in the "Background" section above). Inside, however, the SinglyLinkedList class stores its data in a linked list. Specifically, the SinglyLinkedList class will have two fields.

• first - the first node in a linked list of the elements in the SinglyLinkedList

• size - an int that keeps track of the number of elements in the SinglyLinkedList (so that we don't have to count the nodes in the linked list)

Whenever an element is added, it is added to the end of the linked list, and the size variable is incremented. The following illustration shows the SinglyLinkedList, after "D" has been added to the list.

Go ahead and complete the SinglyLinkedList class definition, so that it works as described above. You will need to implement each of the methods in the List interface. Your code must run in the following running times.

size: constant time
add: linear time
get, set, remove: linear time for elements in the middle or end of the list, but constant time for elements near the beginning of the list

Test your code by running SinglyLinkedListDisplay.

Challenge (1%): Implement the following method in SinglyLinkedList.

void add(int index, E obj)
inserts obj at position index (0 <= index <= size), moving elements at position index and higher to the right (adds 1 to their indices) and adjusts size

This method must run in linear time when adding elements in the middle or end of the list, and it must run in constant time for adding elements near the beginning of the list.

Part 3:  DoublyLinkedList (4%)

In this part, you will write the DoublyLinkedList class definition. DoublyLinkedList implements the List interface shown above. From the outside, it behaves exactly like any other List (like the one shown in the "Background" section above). Inside, however, the DoublyLinkedList class stores its data in a doubly-linked list, in which each node has a reference to both the next node and the previous node. Specifically, the DoublyLinkedList class will have three fields.

• first - the first node in the doubly-linked list

• last - the last node in the doubly-linked list (so we can access the end of the list in constant time)

• size - an int that keeps track of the number of elements (so that we don't have to count the nodes in the linked list)

A DoublyLinkedList with 3 elements is illustrated below.

You cannot use ListNode objects to implement the DoublyLinkedList. Instead, you must define a new class called DoubleNode. This class should work just like the ListNode class, with methods for getValue, getNext, setValue, and setNext. But DoubleNode also has methods for getPrevious and setPrevious to access and change the previous node.

Next, use the DoubleNode class to write a class definition for DoublyLinkedList<E>, which implements the List<E> interface. You will need to implement each of the methods in the List interface, AND the add(int index, E obj) method. Your code must run in the following running times.

size: constant time
add(E obj): constant time
get, set, add(int index, E obj), remove: linear time for elements in the middle, but constant time for elements near the beginning or end of the list

To access elements near the beginning or end in constant time, your methods must always traverse the nodes starting from whichever end is closest to the desired index.

Be sure to test your code thoroughly.