Question: Implementing Data Structures ONLY CHANGE CODE IN MYARRAYLIST AND MYLINKEDLIST DO NOT ADD CUSTOM CODE AND DO NOT MODIFY CODE THAT DOES NOT SAY ADD
| Implementing Data Structures ONLY CHANGE CODE IN MYARRAYLIST AND MYLINKEDLIST DO NOT ADD CUSTOM CODE AND DO NOT MODIFY CODE THAT DOES NOT SAY "ADD CODE HERE" 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.
import java.util.Collection;
/**
* @param the type of elements in this list
*/
public interface IList {
/**
* Appends the specified element to the end of this list.
* @param e element to be appended to this list
* @return true (as specified by {@link Collection#add(Object)}
*/
public abstract boolean add(E e);
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
* @param index index at which the specified element is to be inserted
* @param e element to be inserted
* @throws IndexOutOfBoundsException if the index is out of range {@code (index size())}
*/
public abstract void add(int index, E e);
/**
* Removes the first occurrence of the specified element from this list, if it is present.
* If the list does not contain the element, it is unchanged. More formally, removes the
* element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i)))
* (if such an element exists). Returns true if this list contained the specified element
* (or equivalently, if this list changed as a result of the call).
* @param o element to be removed from this list, if present
* @return true if this list contained the specified element
*/
public abstract boolean remove(Object o);
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one
* from their indices).
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException if the index is out of range {@code (index size())}
*/
public abstract E remove(int index);
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive, and toIndex, exclusive. Shifts any succeeding elements to the left
* (reduces their index). This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
* @param fromIndex index of first element to be removed
* @param toIndex index after last element to be removed
* @throws IndexOutOfBoundsException if fromIndex or toIndex is out of range:
* {@code fromIndex = size() ||
* toIndex > size() || toIndex
*/
public abstract void removeRange(int fromIndex, int toIndex);
/**
* Returns the element at the specified position in this list.
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException if the index is out of range {@code (index size()) }
*/
public abstract E get(int index);
/**
*
* @param index index of the element to replace
* @param e element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException if the index is out of range {@code (index size())}
*/
public abstract E set(int index, E e);
/**
* Returns true if this list contains the specified element.
* More formally, returns true if and only if this list contains at
* least one element e such that {@code (o==null ? e==null : o.equals(e))}.
* @param o element whose presence in this list is to be tested
* @return true if this list contains the specified element
*/
public abstract boolean contains(Object o);
/**
* Returns the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element. More
* formally, returns the lowest index i such that
* {@code (o==null ? get(i)==null : o.equals(get(i)))}, or {@code -1} if there is no such index.
* @param o element to search for
* @return the index of the first occurrence of the specified element in this list,
* or -1 if this list does not contain the element
*/
public abstract int indexOf(Object o);
/**
* Returns the index of the last occurrence of the specified element in this list, or -1 if
* this list does not contain the element. More formally, returns the highest index i such
* that {@code (o==null ? get(i)==null : o.equals(get(i)))}, or {@code -1} if there is no such index.
* @param o element to search for
* @return the index of the last occurrence of the specified element in this list, or -1
* if this list does not contain the element
*/
public abstract int lastIndexOf(Object o);
/**
* Removes all of the elements from this list. The list will be empty after this call returns.
*/
public abstract void clear();
/**
* @return Returns the number of elements in this list.
*/
public abstract int size();
// Returns whether list is empty
/**
* @return Returns true if this list contains no elements.
*/
public abstract boolean isEmpty();
}
-------------------------------------------------------------------------------------------------------
public interface IArrayList extends IList {
/**
* Trims the capacity to the size of the existing array
*/
public abstract void trimToSize();
}
-------------------------------------------------------------------------------------------------------
import java.util.Iterator; import java.util.ListIterator;
/** * ILinkedList.java - LinkedList interface for data structure assignment * @param the type of elements in this list */ public interface ILinkedList extends IList {
/** * Adds element to head (first) of list * @param e the new element */ public abstract void addFirst(E e);
/** * Adds element to tail (last) of list * @param e the new element */ public abstract void addLast(E e);
/** * Removes element from head (first) of list * @return the element that was just removed */ public abstract E removeFirst();
/** * Removes element from tail (last) of list * @return the element that was just removed */ public abstract E removeLast();
/** * Pushes element onto head (first) of list * @param e the new element */ public abstract void push(E e);
/** * Pops element from head (first) of list * @return the element that was just removed */ public abstract E pop();
/** * Peeks at element at head (first) of list * @return the element at the head (first) of the list */ public abstract E peek();
/** * Return a {@code ListIterator} for the list * @return a {@code ListIterator} for the list */ public abstract ListIterator listIterator(); }
-------------------------------------------------------------------------------------------------------
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
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; }
}
> IList +boolean add(E e) + void add(int index, E e) + boolean remove (Object o) + E remove (int index) + E removeRange(int toIndex, int fromIndex) + E get(int index) + E set(int index, E e) + boolean contains() + int indexOf (0bject o) +int lastIndex0f (0bject o) + void clear( + int size() + String isEmpty( > ILinkedList > IArrayList + void addFirst (E e) + void addLast (E e) + E removeFirst() + E removeLast) + void push) +E pop() +E peek () + void clear( + ListIteratorStep by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help