Implementing Data Structures

When calling remove() the index must be between 0 and listSize-1. However, when calling add(), the allowable range for the index is between 0 and listSize, since the caller may be trying to add a new entry to the end of the ArrayList. When the index is out of range throw anIndexOutOfBoundsException.

Implementing a LinkedList

The underlying data structure for a LinkedList uses the inner class Node:

The Node class consists of an element of type E, and a reference to the next Node for a singly-linked list

The Node class can also hold a second reference to the previous Node for doubly-linked list.

A constructor that takes the element and makes a Node with a null reference is useful.

Because you had the opportunity to implement a singly-linked list is lab, we encourage you to make a doubly-linked list. Either one will work, but the extra credit depends on a doubly-linked list data structure.

A number of corner cases exist with LinkedList. These are the most important:

Adding an element to an empty list.

Removing an element from a list with one element

Iterating through the LinkedList when the LinkedList is empty.

Use the javadoc to implement all of the methods inherited from ListInterface and LinkedListInterface in the MyLinkedList class. Some automated grading will also be supplied. Test using the supplied (but incomplete) test program and your own test code. Your code should behave exactly like Javas implementation of a LinkedList.

In order to return a ListIterator, you must implement the hasNext(), next(), nextIndex(), hasPrevious(), previous(), and previousIndex() methods. This is extra credit, and while not required, encouraged. We have provided a visual aid to help you gain a better understanding of the problem.

public class MyArrayList implements IArrayList {

/**

* Declare underlying array

*/

private E[] underlyingArray;

/**

* Current size

*/

private int listSize;

public final static double CAPACITY_INCREASE = 0.5;

/**

* Constructs an empty list with the specified initial capacity.

* @param initialCapacity the initial capacity of the list

*/

public MyArrayList(int initialCapacity) {

// YOUR CODE HERE

}

/**

* Constructs an empty list with an initial capacity of ten.

* Because we are using generics you will have to create a new

* array of type Object and cast it to type E.

*

* Think about constructor chaining.

*/

public MyArrayList() {

// YOUR CODE HERE

}

/**

* Special debug method

*/

public void printDebug() {

Debug.printf("ArrayList.size() = %d ", listSize);

Debug.printf("ArrayList.capacity() = %d ", underlyingArray.length);

for (int index = 0; index < listSize; index++) {

E e = (E)underlyingArray[index];

String sElement = e.getClass().getName() + "@" + Integer.toHexString(e.hashCode());

System.err.printf("ArrayList[%d]: %s: %s ", index, sElement, e.toString());

}

}

// If the array is full, expand its capacity by an additional 50% (defined through

// CAPACITY_INCREASE), using integer math. For example, if the current capacity is 15

// the new capacity will be 22, and if the current capacity is 22 the new capacity

// will be 33.

@Override

public boolean add(E e) {

// YOUR CODE HERE

return true;

}

// If the array is full, expand its capacity by an additional 50% (defined through

// CAPACITY_INCREASE), using integer math. For example, if the current capacity is 15

// the new capacity will be 22, and if the current capacity is 22 the new capacity

// will be 33.

@Override

public void add(int index, E e) {

// YOUR CODE HERE

}

@Override

public boolean remove(Object o) {

// YOUR CODE HERE

return false;

}

@Override

public E remove(int index) {

// YOUR CODE HERE

return null;

}

@Override

public void removeRange(int fromIndex, int toIndex) {

// YOUR CODE HERE

}

@Override

public E get(int index) {

// YOUR CODE HERE

return null;

}

@Override

public E set(int index, E e) {

// YOUR CODE HERE

return null;

}

@Override

public boolean contains(Object o) {

// YOUR CODE HERE

return false;

}

@Override

public int indexOf(Object o) {

// YOUR CODE HERE

return -1;

}

@Override

public int lastIndexOf(Object o) {

// YOUR CODE HERE

return -1;

}

@Override

public void clear() {

// YOUR CODE HERE

}

@Override

public int size() {

// YOUR CODE HERE

return -1;

}

@Override

public boolean isEmpty() {

// YOUR CODE HERE

return false;

}

// use the reallocateArray method

public void trimToSize() {

// YOUR CODE HERE

}

private void reallocateArray(int capacity) {

// YOUR CODE HERE

}

}

-------------------------------------------------------------------------------------------------------

import java.util.Arrays; import java.util.LinkedList; import java.util.ListIterator; import java.util.NoSuchElementException;

/** * CoolLinkedList.java - student implementation of LinkedList * * @param the type of elements in this list */ public class MyLinkedList implements ILinkedList {

// Node data structure public class Node { // YOUR CODE HERE }

// Head (first) pointer private Node listHead;

// Tail (last) pointer private Node listTail;

// Current size private int listSize;

// Default constructor public MyLinkedList() { // YOUR CODE HERE }

/** * Special debug method. Uncomment this method after completing the Node class. */ public void printDebug() { /* Debug.printf("LinkedList.size() = %d ", listSize); int index = 0; for (Node c = listHead; c != null; c = c.next) { String sNode = c.getClass().getSimpleName() + "@" + Integer.toHexString(c.hashCode()); String sNext; if (c.next == null) sNext = "null"; else sNext = c.next.getClass().getSimpleName() + "@" + Integer.toHexString(c.hashCode()); Debug.printf("LinkedList[%d]: element %s, next %s ", index++, sNode, sNext); } */ }

// Possible helper method? Delete if you don't want to use it. private Node getNode(int index){ return null; }

public boolean add(E e) { // YOUR CODE HERE

return true; }

public void add(int index, E e) { // YOUR CODE HERE }

public boolean remove(Object o) { // YOUR CODE HERE

return true; }

public E remove(int index) { // YOUR CODE HERE

return null; }

@Override public void removeRange(int fromIndex, int toIndex) { // YOUR CODE HERE

}

public E get(int index) { // YOUR CODE HERE

return null; }

public E set(int index, E e) { // YOUR CODE HERE

return null; }

public boolean contains(Object o) { // YOUR CODE HERE

return false; }

public int indexOf(Object o) { // YOUR CODE HERE

return -1; }

public int lastIndexOf(Object o) { // YOUR CODE HERE

return -1; }

public void clear() { // YOUR CODE HERE

}

public int size() { // YOUR CODE HERE

return 0; }

public boolean isEmpty() { // YOUR CODE HERE

return false; }

public void addFirst(E e) { // YOUR CODE HERE

}

public void addLast(E e) { // YOUR CODE HERE

}

public E removeFirst() { // YOUR CODE HERE

return null; }

public E removeLast() { // YOUR CODE HERE

return null; }

public void push(E e) { // YOUR CODE HERE

}

public E pop() { // YOUR CODE HERE

return null; }

public E peek() { // YOUR CODE HERE

return null; }

// Extra credit public class MyLinkedListIterator implements ListIterator { // declare and initialize member variables

@Override public boolean hasNext() { // YOUR CODE HERE

return false; }

@Override public E next() { // YOUR CODE HERE

return null; }

@Override public boolean hasPrevious() { // YOUR CODE HERE

return false; }

@Override public E previous() { // YOUR CODE HERE

return null; }

@Override public int nextIndex() { // YOUR CODE HERE

return 0; }

@Override public int previousIndex() { // YOUR CODE HERE

return 0; }

@Override public void remove() { throw new UnsupportedOperationException(); }

@Override public void set(E e) { throw new UnsupportedOperationException(); }

@Override public void add(E e) { throw new UnsupportedOperationException(); } }

public MyLinkedListIterator listIterator() { // YOUR CODE HERE

return null; }

}