Implementing Data Structures When calling remove() the index must be between 0 a
ID: 3732901 • Letter: I
Question
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 Java’s 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<E> implements IArrayList<E> {
/**
* 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.
* <p>
* 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 <E> the type of elements in this list
*/
public class MyLinkedList<E> implements ILinkedList<E> {
// 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<E> {
// 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;
}
}
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.
Explanation / Answer
public class MyArrayList {
// YOUR CODE ANYWHERE IN THIS CLASS
private Object[] array;
public static final int CAPACITY = 10;
public int size;
public int capacity;
// there could be more instance variables!
/*
* initialise array with capacity. If capacity is less than 1, use CAPACITY.
*
*/
@SuppressWarnings("unchecked")
public MyArrayList() {
array = new Object[CAPACITY];
this.capacity = 10;
size = 0;
}
public MyArrayList(int capacity) {
array = new Object[capacity];
this.capacity = capacity;
size = 0;
}
public void add(int i, Object val) {
if (i >= capacity)
return;
else
{
size++;
for (int x = size - 1; x > i; x--) {
array[x] = array[x - 1];
}
array[i] = val;
}
}
public void add(Object x) {
if (size >= capacity){
Object[] temp = new Object[2*array.length];
for(int i=0;i<size;++i){
temp[i] = array[i];
}
this.capacity = 2*array.length;
array = temp;
array[size++] = x;
return;
}
else
{
array[size++] = x;
}
}
public void set(int i, Object val) {
// YOUR CODE ANYWHERE IN THIS CLASS
if (i >= capacity)
return;
else
{
size++;
for (int x = size - 1; x > i; x--) {
array[x] = array[x - 1];
}
array[i] = val;
}
}
/*
* if index is outside range of array. return null
*
*/
public Object get(int i) {
// YOUR CODE ANYWHERE IN THIS CLASS
if (i >= capacity)
return null;
else
return array[i];
}
/*
* if index is outside range of array. return null
*
*/
public void remove(int i) {
if (i >= size || size == 0)
return;
else {
Object e = array[i];
for (int x = i; x < this.array.length - 1; x++) {
array[x] = array[x + 1];
}
size--;
}
}
public void remove(Object ob) {
// YOUR CODE ANYWHERE IN THIS CLASS
if (size == 0)
return;
else {
int i;
for (i = 0; i < size; ++i) {
if (ob.equals(array[i]))
break;
}
if (i == size)
return;
Object e = array[i];
for (int x = i; x < this.array.length - 1; x++) {
array[x] = array[x + 1];
}
size--;
}
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object ob) {
for (int i = 0; i < size; ++i) {
if (ob.equals(array[i]))
return true;
}
return false;
}
public int search(Object ob) {
for (int i = 0; i < size; ++i) {
if (ob.equals(array[i]))
return i;
}
return -1;
}
public String toString() {
String res = "";
for (int i = 0; i < size; ++i) {
res = res + array[i] + " ";
}
return res;
}
@Override
public boolean equals(Object other) {
if (other == null)
return false;
System.out.println(this);
System.out.println((Integer) other);
if (other == this)
return true;
return false;
}
}
=============================================================================
import java.io.Serializable;
import java.util.*;
public class MyLinkedList implements List<Object>,
Serializable, Cloneable {
/**
*
*/
private static final long serialVersionUID = 1L;
ListNode head;
int size;
//inner class for ListNode
private class ListNode {
private Object data;
private ListNode next;
private ListNode(Object d) {
this.data = d;
this.next = null;
}
private ListNode (Object d, ListNode next){
this.data = d;
this.next = next;
}
private ListNode() {
}
}
public MyLinkedList() {
this.head = new ListNode(null);
this.size = 0;
}
public void addFirst(Object data){
ListNode temp = new ListNode(data);
temp.next = this.head.next;
this.head.next = temp;
this.size++;
}
public void addLast (Object data){
if(isEmpty())
addFirst(data);
else {
ListNode cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = new ListNode(data,null);
this.size++;
}
}
@Override
public boolean equals(Object o){
if(o == null){
throw new NullPointerException("NULL parameter passed on call to equals(Object)");
}
if(o == this){
return true;
}
if(o instanceof MyLinkedList){
MyLinkedList list = (MyLinkedList)o;
if(this.size == 0 && list.size() == 0){
return true;
}
if(this.size == list.size()){
boolean ret = true;
ListNode cur, cur2;
cur = this.head.next;
cur2 = list.head.next;
for(; cur!= null && cur2!= null; cur = cur.next, cur2 = cur2.next){
if(cur.data.equals(cur2.data) != true){
ret = false;
}
}// end for
return ret;
}// end if(size == size)
else{
return false;
}
}// end if(instanceof)
return false;
}// end equals()
@Override
public Iterator<Object> iterator() {
return new MyLinkedListIterator(this.head);
}
/* @Override
public int hashCode() {
int value;
return value;
}*/
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
Iterator<Object> it = this.iterator();
while(it.hasNext()) {
Object temp = it.next();
if(temp != null && o != null && temp.equals(o)) {
return true;
}
else if(temp == null && o == null) {
return true;
}
}
return false;
}
@Override
public Object[] toArray() {
throw new UnsupportedOperationException();
}
@Override
public <Object> Object[] toArray(Object[] a) {
throw new UnsupportedOperationException();
}
@Override
public boolean remove(Object o) {
for(ListNode prev = this.head, walk = this.head.next;
walk != null; prev = walk,walk = walk.next){
if (walk.data.equals(o)) { //should override equals in your class Object
prev.next = walk.next;
this.size --;
return true;
}
}//end for
return false;
}
@Override
public boolean containsAll(Collection c) {
for(Object e : c) {
if (!contains(e))
return false;
}
return true;
}
@Override
public boolean addAll(Collection c) throws NullPointerException {
if ( c == null ) {
throw new NullPointerException("Collection passed in is null!");
}
Iterator itr= c.iterator();
while(itr.hasNext()){
add(itr.next());
this.size ++;
}
return true;
}
@Override
public boolean addAll(int index, Collection c) {
// TODO Auto-generated method stub
if (c == null) {
throw new NullPointerException();
}
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
ListNode cur = this.head;
MyLinkedList temp = new MyLinkedList();
temp.addAll(c);
ListNode curTemp = temp.head;
ListNode curr = head;
ListNode firstIndexTemp = temp.head;
if(index == 0){
curTemp = curTemp.next;
firstIndexTemp = firstIndexTemp.next;
while( curTemp.next != null){
curTemp = curTemp.next;
}
curTemp.next = curr.next;
curr.next = firstIndexTemp;
}
else{
for(int i = 0; i < index; i++){
curr = curr.next;
}
curTemp = curTemp.next;
firstIndexTemp = firstIndexTemp.next;
while( curTemp.next != null){
curTemp = curTemp.next;
}
curTemp.next = curr.next;
curr.next = firstIndexTemp;
}
return true;
}
private ListNode findPrev(int index){
if (index == 0)
return null;
ListNode prev = head;
for (int i = 1; i < index -1; i++){
prev = prev.next;
}
return prev;
}
@Override
public boolean removeAll(Collection c) throws NullPointerException,
UnsupportedOperationException{
// TODO Auto-generated method stub
// Do not need to implement optional exceptions
// Check documentation
Boolean changed = false;
Iterator<Object> thisIt = this.iterator();
if(c == null){
throw new NullPointerException();
}
while(thisIt.hasNext()) {
if( c.contains(thisIt.next()) ) {
try{
thisIt.remove();
this.size --;
changed = true;
}catch(UnsupportedOperationException ex) {
throw new UnsupportedOperationException();
}
}
}//end of while
return changed;
}
@Override
public boolean retainAll(Collection c) {
// TODO Auto-generated method stub
if (c==null)
throw new NullPointerException();
if (this.head == null)
return true;
while(head.next != null){
head = head.next;
}
addAll(c);
return true;
}
@Override
public void clear() {
// TODO Auto-generated method stub
head = null;
size = 0;
}
@Override
public Object get(int index) throws IndexOutOfBoundsException{
if(index < 0 || index >= size()) {
throw new IndexOutOfBoundsException("Provided index is out of bounds! " + index);
}
ListNode walk = head;
for(int cur = 0; cur < index; walk = walk.next, cur ++){
//empty loop body
}
return walk.data;
}
@Override
public Object set(int index, Object element) {
// TODO Auto-generated method stub
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException("Provided index is out of bounds! " + index);
ListNode temp = new ListNode(element);
ListNode cur = this.head.next;
ListNode prev = this.head;
if (index == 0){
prev.next = temp;
temp.next = cur.next;
}
else{
for(int i = 0; i < index ; i++){
prev = prev.next;
cur = cur.next;
}
prev.next = temp;
temp.next = cur.next;
}
return null;
}
@Override
public void add(int index, Object element) throws IndexOutOfBoundsException{
// TODO Auto-generated method stub
if( index < 0 || index >= this.size +1){
throw new IndexOutOfBoundsException("Provided invalid index integer! " + index);
}
ListNode temp = new ListNode(element);
ListNode curr = head;
if (index == 0){
temp.next = curr.next;
curr.next = temp;
}
else{
for(int i = 0; i < index ; i++){
curr=curr.next;
}
temp.next = curr.next;
curr.next = temp;
}
this.size++;
}
@Override
public Object remove(int index) throws IndexOutOfBoundsException {
if(index < 0 || index >= size()) {
throw new IndexOutOfBoundsException("Provided index is out of bounds! " + index);
}
ListNode walk = head.next;
ListNode prev = head;
for(int cur = 0; cur < index; cur ++){
prev = walk;
walk = walk.next;
}
this.size --;
prev.next = walk.next;
return walk.data;
}
@Override
public int indexOf(Object o) {
// TODO Auto-generated method stub
ListNode curr = head.next;
for (int i = 0; i < size; i++){
if( o == null){
if(curr.data == null){
return i;
}
}
else{
if(o.equals(curr.data)){
return i;
}
}
curr = curr.next;
}
return -1;
}
@Override
public int lastIndexOf(Object o) {
// TODO Auto-generated method stub
ListNode curr = head.next;
int lastindex = 0;
for (int i = 0; i < size; i++){
if( o == null){
if(curr.data == null){
return i;
}
}
else{
if(o.equals(curr.data)){
lastindex = i;
}
}
curr = curr.next;
}
if(lastindex == 0)
return -1;
return lastindex;
}
@Override
public ListIterator<Object> listIterator() {
// TODO Auto-generated method stub
return null;
}
@Override
public ListIterator<Object> listIterator(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public List<Object> subList(int fromIndex, int toIndex) {
// TODO Auto-generated method stub
MyLinkedList newList = new MyLinkedList();
if(fromIndex < 0 || toIndex > this.size){
throw new IndexOutOfBoundsException("Provided invalid index! ");
}
else{
int i = 0;
ListNode node = null;
for (node = this.head.next; node != null && i<fromIndex;node = node.next);
while(node!=null && i<toIndex){
newList.add(node.data);
node = node.next;
}
}
// System.out.println(newList.toString());
return newList;
}
@Override
//this method is equivalent to addLast()
public boolean add(Object e) {
ListNode walk = head;
for(;walk.next != null; walk = walk.next){
//empty loop body
}
//make new node
ListNode anode = new ListNode(e);
walk.next = anode;
this.size ++; //increment size
return true;
}
public class MyLinkedListIterator implements Iterator<Object> {
private ListNode cur;
private MyLinkedListIterator ( ListNode start ) {
this.cur = start.next; //with dummy node
}
public boolean hasNext() {
return cur != null;
}
public Object next() throws NoSuchElementException {
if(hasNext()) {
Object data = cur.data;
cur = cur.next;
return data;
}
throw new NoSuchElementException();
}
public void remove() {
throw new UnsupportedOperationException();
}
}//end of Iterator
@Override
public String toString() {
String result = "( ";
for (ListNode node = this.head.next; node != null;
node = node.next) {
result += node.data + "-->";
}
return result + ")";
}
}