JAVA. Codes are given below. Must complete what the question is asking. Thank you.

QUESTION: Draw a depiction of an ArrayList300 object and a LinkedList300 object, as they are implemented in the accompanying hw4.jar file, after each operation in the following sequence. The ArrayList300 class uses wrap-around and chooses to shift data based on an index (for those methods that are passed indices), and the LinkedList300 class is a doubly-linked implementation with sentinels. Assume the lists are initially empty.

list.add(a);

list.add(0, b);

list.add (1, c);

list.add(d);

list.remove(2);

ARRAYLIST

package hw4;

/* * CSC 300 Sections 201, 210 Summer I 2017 * Homework assignment 4, part 3 * * You must complete the reverse method below. * Reverse should be a destructive method; * that is, it should make changes to the * ArrayList300 object that it is invoked on. * * This is the full-fledged version of an array-based * implementation of List. It uses a wrap-around array. * When data shifting is necessary (as it is in add and * remove), we determine which way to shift based on the * index passed. The the index is less than halfway * through the list, then data is shifted from the left * otherwise it's to the right. * * Notice that because of wrap-around, the front of the * list does not necessary correspond to index 0 in the * array. */

import java.util.Iterator; import java.util.List;

public class ArrayList300 implements List300 { // the initial capacity can be whatever we want. // In Java, by default the initial capacity of // ArrayList is 10. private static final int INIT_CAPACITY = 5; private T[] items = (T[]) new Object[INIT_CAPACITY]; // front is the index where the list begins, and // back is where it ends. At times, it will be the // case that front > back, which would indicate that // wrap-around has occurred. // Note that the size of the list is somewhat difficult // to compute based on the values of front and back. // If there is no wrap-around, size = (back-front)+1. // If there is wrap-around, size = (back-front)+items.length+1 private int size, front, back; public ArrayList300() { // by convention we'll indicate an empty list by // setting front and back to -1 front = -1; back = -1; size = 0; }

// this was mainly for testing purposes. Create an // ArrayList as specified by the parameters public ArrayList300(T[] initItems, int front, int back, int size) { items = initItems; this.front = front; this.back = back; this.size = size; }

public String toString() { if (size == 0) return "[]"; StringBuilder b = new StringBuilder("["); // Notice that since the front of the list is not necessarily // at index 0 of the "items" array, the for loop calculates // (front+i) % items.length to compute the location of the next // item in the list. The % operator is needed because of potential // wrap-around for (int i=0; i other = (Iterable) o; int i; Iterator it = iterator(), otherIt = other.iterator(); for (i=0; it.hasNext() && otherIt.hasNext(); i++) { T mine = it.next(); T others = otherIt.next(); /* * this was for debugging * if (mine == null) { System.out.println("Mine is null"); System.out.println(this + " size = " + size + " front = " + front + " back = " + back + " length " + items.length); System.exit(0); } if (!mine.equals(others)) { System.out.println("lists are not equal at index " + i); return false; } */ } if (it.hasNext() != otherIt.hasNext()) { // System.out.println("lists are not equal at index " + i); return false; } return true; }

// when the list is expanded, we eliminate wrap-around by copying the // items in the old array in such a way that the first item in the // list is place in newItems[0] private void expand() { T[ ] newItems = (T[ ]) new Object[items.length*2]; for (int i=0; i

// Add is written to decide which way to shift, in order // to make room and place the new item at the position specified // by idx. If idx is less than half of the size of the list, // then left shifting is performed to make room // for item. Otherwise, right shifting is performed. public void add(int idx, T item) { if (size == items.length) expand(); // case 1: add to the end if (idx == size) add(item); // case 2: add to the front else if (idx == 0) { front--; if (front < 0) front += items.length; items[front] = item; size++; } // case 3: add somewhere in the middle. // determine whether to shift data to the left or the right // depending on precisely where the new item is to be // placed else { // calculate the index into "items" (pos) that corresponds // to the correct position in the list (idx) int pos = (front+idx-1); if (pos < 0) pos += items.length; else pos %= items.length; // if the new data is to be inserted somewhere in // the first half of the list, left shift data in // order to make room for the new item // For example: // // ------------------- // | a | c | d | e | | // ------------------- // front = 0, back = 3, size = 4 // // list.add(1, "b"); // // In this case, we choose to left shift, resulting in // ------------------- // | b | c | d | e | a | // ------------------- // front = 4, back = 3, size = 5 if (idx <= size/2) { leftShift(front, pos); items[pos] = item; front--; if (front<0) front += items.length; size++; } // otherwise, right shift. For example: // // ------------------- // | e | | a | b | c | // ------------------- // front = 2, back = 0, size = 4 // // list.add(3, "d"); // // We choose to right shift, resulting in // ------------------- // | d | e | a | b | c | // ------------------- // front = 2, back = 1, size = 5 else { rightShift(pos, back); items[pos] = item; back = (back + 1) % items.length; size++; } } }

// Shift all data to the left that is between the start index // and the end index (inclusive). This may involve wrap-around public void leftShift(int start, int end) { // case 1: no wrap-around if (start != 0 && start <= end) for (int i=start; i<=end; i++) items[i-1] = items[i]; // case 2: wrap-around, in which case there are 3 steps // (a) shift data between indices start and items.length-1 (inclusive) // (b) copy items[0] into items[items.length-1] // (c) shift data between indices 1 and end (inclusive) else { if (start != 0) for (int i=start; i=start; i--) items[i+1] = items[i]; // case 2: wrap-around, in which case there are 3 steps // (a) shift data between indices start and items.length-1 (inclusive) // (b) copy items[0] into items[items.length-1] // (c) shift data between indices 1 and end (inclusive) else { if (end != items.length) for (int i=end; i>=0; i--) items[i+1] = items[i]; items[0] = items[items.length-1]; for (int i=items.length-2; i>=end; i--) items[i+1] = items[i]; } } // returns the current value stored in position idx public T set(int idx, T item) { if (idx >= size) throw new IndexOutOfBoundsException(); int pos = (idx + front) % items.length; T oldContents = items[pos]; items[pos] = item; return oldContents; }

// return true if item is in the list, or false otherwise. public boolean contains(T item) { int current = front; for (int i=0; i

public T get(int idx) { if (idx >= size) throw new IndexOutOfBoundsException(); return items[(idx+front)%items.length]; }

public void clear() { size = 0; front = -1; back = -1; }

public boolean isEmpty() { return size == 0; }

public int size() { return size; }

public boolean remove(T item) { int pos = front; for (int i=0; i

// Remove is written to decide which way to shift, in order // to remove the item at the position specified by idx. // If idx is less than half of the size of the list, // then right shifting is performed to remove the item. // Otherwise, left shifting is performed. public T remove(int idx) { // calculate the index into "items" (pos) that corresponds // to the correct position in the list (idx) int pos = (front+idx) % items.length; T answer = items[pos]; // determine whether to shift data to the left or the right // depending on precisely where the item is being // removed from the list

// if the data to be removed is somewhere in // the first half of the list, right shift data in // order to overwrite the deleted item // For example: // // ------------------- // | a | b | c | d | | // ------------------- // front = 0, back = 3, size = 4 // // list.remove(1); // // In this case, we choose to right shift, resulting in // ------------------- // | a | a | c | d | | // ------------------- // front = 1, back = 3, size = 3 // // Note that "a" is also at index 0 in the "items" // array. This is because there is no real need // to clear index 0; we can tell from front and back // that this "a" is not in the list. Eventually, // it will probably be overwritten as the list grows // and shrinks. if (idx < size/2 && pos != 0) { rightShift(front, pos-1); front = (front + 1) % items.length; size--; } // otherwise, left shift. For example: // // ------------------- // | d | | a | b | c | // ------------------- // front = 2, back = 0, size = 4 // // list.remove(2); // // We choose to left shift, resulting in // ------------------- // | d | | a | b | d | // ------------------- // front = 2, back = 4, size = 3 // // Again, the "d" remains also at index 0 of "items". // There is no need to set items[0] back to null, // because we can tell by the values of front and // back that items[0] is not in the list. Eventually, // it is likely the items[0] will be overwritten // as the list grows and shrinks. else { leftShift((pos+1)%items.length, back); back -= 1; if (back < 0) back += items.length; size--; } return answer; }

public Iterator iterator() { return new Iterator() { private int current = front; private int i = 0; public boolean hasNext() { return i < size; }

public T next() { i++; T answer = items[current]; current = (current + 1) % items.length; return answer; } }; }

}

LINKED LIST

package hw4;

/* * CSC 300 Sections 201, 210 Summer I 2017 * Homework assignment 4, problem 2 * * Complete the copyList method below, as described * in the homework write-up. * */

/* * LinkedList300: a doubly linked list * * The list is made up of Nodes. Each node * now has 3 instance variables: "item" stores * a piece of data (of type T), "next" * is a pointer to the next Node in the list, * and "previous" points back to the previous * Node. In additional, this implementation * has "sentinel" nodes, which are the first and * last Nodes in the list, and which contain no * data (i.e., item is null). The use of these * Nodes is to reduce the number of special cases, * which may be difficult to program correctly. */

import java.util.Iterator; import java.util.LinkedList;

public class LinkedList300 implements List300 { private int count = 0; private class Node { private int id; private T item; private Node next; private Node previous; public Node(T item, Node next, Node previous) { this.item = item; this.next = next; this.previous = previous; id = ++count; } public String toString() { StringBuilder b = new StringBuilder("[Node "); b.append(id + " item " + item + " next "); if (next == null) b.append("null"); else b.append(next.id); b.append(" previous "); if (previous == null) b.append("null]"); else b.append(previous.id + "]"); return b.toString(); } } private Node first, last; private int size;

public LinkedList300() { first = new Node(null, null, null); last = new Node(null, null, first); first.next = last; size = 0; } /* this was for debugging purposes public void printNodes() { System.out.println("printNodes of list " + this); Node n = first; while (n != last) { System.out.println(n); n = n.next; } System.out.println(last); } */ /********** WRITE THIS METHOD *********/ public LinkedList300 copyList() { LinkedList300 List = new LinkedList300(); Nodecurrent; current = first.next; while(current != last){ List.add(current.item); current = current.next; }

return List; // remove this } public String toString() { if (isEmpty()) return "[]"; StringBuilder b = new StringBuilder("["); Node current = first.next; // current = first; while (current != last.previous) { // (current != last) if (current.item == null) b.append("null, "); else b.append(current.item + ", "); current = current.next; } b.append(current.item /*.toString()*/ + "]"); return b.toString(); } /* public String toString() { StringBuilder b = new StringBuilder("List size " + size + " "); Node current = first; while (current != null) { b.append(current.toString()); current = current.next; } return b.toString() + actualToString() + " "; } */ public boolean equals(Object o) { Iterable other = (Iterable) o; int i; Iterator it = iterator(), otherIt = other.iterator(); for (i=0; it.hasNext() && otherIt.hasNext(); i++) { if (!it.next().equals(otherIt.next())) { System.out.println("lists are not equal at index " + i); return false; } } if (it.hasNext() != otherIt.hasNext()) { System.out.println("lists are not equal at index " + i); return false; } return true; }

public boolean add(T item) { // System.out.println("Add " + item); Node newNode = new Node(item, last, last.previous); last.previous.next = newNode; last.previous = newNode; size++; // System.out.println(this); return true; }

public void add(int idx, T item) { // System.out.println("Add(" + idx + "," + item + ")"); if (idx > size) throw new IndexOutOfBoundsException(); if (idx == size) add(item); else if (idx <= size/2) addFromFront(idx, item); else addFromBack(idx, item); }

private void addFromFront(int idx, T item) { // System.out.println("addFromFront"); Node current = first; for (int i=0; i newNode = new Node(item, current.next, current); current.next.previous = newNode; current.next = newNode; size++; } private void addFromBack(int idx, T item) { // System.out.println("addFromBack"); Node current = last; for (int i=size; i>idx; i--) current = current.previous; Node newNode = new Node(item, current, current.previous); current.previous.next = newNode; current.previous = newNode; size++; } public T set(int idx, T item) { if (idx >= size) throw new IndexOutOfBoundsException(); Node current = first.next; for (int i=0; i

/* public boolean contains(T item) { for (Node current = first.next; current != last; current = current.next) if (current.item == item) return true; return false; } */

public boolean contains (T item) { for (T data : this) if (data.equals(item)) return true; return false; }

public T get(int idx) { if (idx >= size) throw new IndexOutOfBoundsException(); Node current = first.next; for (int i=0; i

public void clear() { first.next = last; last.previous = first; size = 0; }

public boolean isEmpty() { return first.next == last; }

public int size() { return size; }

public boolean remove(T item) { Node current = first.next; while (current != last) { if (current.item.equals(item)) { current.previous.next = current.next; current.next.previous = current.previous; size--; return true; } else current = current.next; } return false; }

public T remove(int idx) { if (idx >= size) throw new IndexOutOfBoundsException(); Node current = first.next; for (int i=0; i

public Iterator iterator() { return new Iterator() { // easier to write remove this way private Node current = first.next; public boolean hasNext() { return current != null && current != last; } public T next() { T answer = current.item; current = current.next; return answer; } /* public void remove() { if (current == null) throw new IllegalStateException("Iterator's next() has not yet been called"); if (previous == null) first = current.next; else previous.next = current.next; current = previous; } */ }; } }