JAVA. Codes are given below. Must complete what the question is asking. Thank yo
ID: 3855873 • Letter: J
Question
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<T> implements List300<T> {
// 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<size-1; i++)
b.append(items[(front+i)%items.length] + ", ");
b.append(items[(front+size-1)%items.length] + "]");
// This was for debugging purposes
// b.append(" front " + front + " back " + back + " size " + size + " length " + items.length);
return b.toString();
}
// equals must be passed a parameter of type Object,
// due to inheritance. Then it should be cast
// to the appropriate type and used as an instance
// of that type for the rest of the method
// In the test code, I call equals occasionally to make
// sure that my methods do the same thing as the corresponding
// methods. That is why the print statements are in the
// code. Once I'm certain the code works properly, I
// would take them out.
public boolean equals(Object o) {
Iterable<T> other = (Iterable<T>) o;
int i;
Iterator<T> 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<size; i++)
newItems[i] = items[(front+i)%items.length];
items = newItems;
front = 0;
back = size-1;
}
/************* YOU MUST WRITE THIS METHOD *********/
public void reverse() {
}
public boolean add(T item) {
if (size == items.length) expand();
// special case: in an empty list, back and front are both -1.
// So they should now both be set to 0.
if (isEmpty()) {
front = back = 0;
items[0] = item;
size = 1;
}
// otherwise, increment back (but use % to wrap around if
// necessary), and store the new item at that position.
// Also, of course size needs to be incremented.
else {
back = (back + 1) % items.length;
items[back] = item;
size++;
}
return true;
}
// 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<items.length; i++)
items[i-1] = items[i];
items[items.length-1] = items[0];
for (int i=1; i<=end; i++)
items[i-1] = items[i];
}
}
// Shift all data to the left that is between the start index
// and the end index (inclusive). This may involve wrap-around.
// This is more or less a mirror image of leftShift.
public void rightShift(int start, int end) {
// case 1: no wrap-around
if (end != items.length-1 && start <= end)
for (int i=end; 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<size; i++) {
if (items[current].equals(item))
return true;
current = (current + 1) % items.length;
}
return false;
}
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<size; i++)
if (items[pos].equals(item)) {
// remove the item by shifting data
// to the left. This has the effect
// of overwriting the removed item.
leftShift(pos, back);
size--;
return true;
}
else pos = (pos+1) % items.length;
return false;
}
// 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<T> iterator() {
return new Iterator<T>() {
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<T> implements List300<T> {
private int count = 0;
private class Node<T> {
private int id;
private T item;
private Node<T> next;
private Node<T> previous;
public Node(T item, Node<T> next, Node<T> 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<T> first, last;
private int size;
public LinkedList300() {
first = new Node<T>(null, null, null);
last = new Node<T>(null, null, first);
first.next = last;
size = 0;
}
/* this was for debugging purposes
public void printNodes() {
System.out.println("printNodes of list " + this);
Node<T> n = first;
while (n != last) {
System.out.println(n);
n = n.next;
}
System.out.println(last);
}
*/
/********** WRITE THIS METHOD *********/
public LinkedList300<T> copyList() {
LinkedList300<T> List = new LinkedList300<T>();
Node<T>current;
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<T> 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<T> current = first;
while (current != null) {
b.append(current.toString());
current = current.next;
}
return b.toString() + actualToString() + " ";
}
*/
public boolean equals(Object o) {
Iterable<T> other = (Iterable<T>) o;
int i;
Iterator<T> 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<T> newNode = new Node<T>(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<T> current = first;
for (int i=0; i<idx; i++) {
current = current.next;
// System.out.println(current);
}
Node<T> newNode = new Node<T>(item, current.next, current);
current.next.previous = newNode;
current.next = newNode;
size++;
}
private void addFromBack(int idx, T item) {
// System.out.println("addFromBack");
Node<T> current = last;
for (int i=size; i>idx; i--)
current = current.previous;
Node<T> newNode = new Node<T>(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<T> current = first.next;
for (int i=0; i<idx; i++)
current = current.next;
T answer = current.item;
current.item = item;
return answer;
}
/*
public boolean contains(T item) {
for (Node<T> 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<T> current = first.next;
for (int i=0; i<idx; i++)
current = current.next;
return current.item;
}
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<T> 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<T> current = first.next;
for (int i=0; i<idx; i++)
current = current.next;
current.previous.next = current.next;
current.next.previous = current.previous;
size--;
return current.item;
}
public Iterator<T> iterator() {
return new Iterator<T>() {
// easier to write remove this way
private Node<T> 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;
} */
};
}
}
Explanation / Answer
The required code using Java is as follows:
DoublyLL.java
import java.util.ListIterator;
import java.util.NoSuchElementException;
public class DoublyLL<box> implements Iterable<box> {
private int no;
private Node first;
private StructNode last;
public DoublyLL() {
first = new StructNode();
last = new StructNode();
first.nxt = last;
last.earlier = first;
}
private class StructNode {
private box items;
private StructNode nxt;
private StructNode earlier;
}
public boolean isBlank()
{
return no == 0;
}
public int ssz()
{
return no;
}
public void add(box items) {
StructNode last = last.earlier;
StructNode io = new StructNode();
io.items = items;
io.nxt = last;
io.earlier = last;
last.earlier = io;
last.nxt = io;
no++;
}
public liIterate<box> iterate() { return new DoublyLLIterate(); }
private class DoublyLLIterate implements liIterate<box> {
private StructNode curr = first.nxt;
private StructNode lstAccess = null;
private int indices = 0;
public boolean hsNxt() { return indices < no; }
public boolean hasEarlier() { return indices > 0; }
public int prevIn() { return indices - 1; }
public int nxtInd() { return indices; }
public box nxt() {
if (!hsNxt()) throw new NoSuchElementException();
lstAccess = curr;
box items = curr.items;
curr = curr.nxt;
indices++;
return items;
}
public box previous() {
if (!hasEarlier()) throw new NoSuchElementException();
curr = curr.earlier;
indices--;
lstAccess = curr;
return curr.items;
}
public void keep(box items) {
if (lstAccess == null) throw new IllegalStateException();
lstAccess.items = items;
}
public void rm() {
if (lstAccess == null) throw new IllegalStateException();
StructNode io = lstAccess.earlier;
StructNode ui = lstAccess.nxt;
io.nxt = ui;
ui.earlier = io;
no--;
if (curr == lstAccess)
curr = ui;
else
indices--;
lstAccess = null;
}
public void add(box items) {
StructNode io = curr.earlier;
StructNode ui = new StructNode();
StructNode qq = curr;
ui.items = items;
io.nxt = ui;
ui.nxt = qq;
qq.earlier = ui;
ui.earlier = io;
no++;
indices++;
lstAccess = null;
}
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (box items : this)
sb.append(items + " ");
return sb.toString();
}
public static void main(String[] args) {
int no = Integer.parseInt(args[0]);
StdOut.println(no + " Random integers between 0 - 99");
DoublyLL<Integer> lss = new DoublyLL<Integer>();
for (int i = 0; i < no; i++)
lss.add(StdRandom.uniform(100));
StdOut.println(lss);
StdOut.println();
liIterate<Integer> iterate = lss.iterate();
StdOut.println("Add 1 to each element");
while (iterate.hsNxt()) {
int io = iterate.nxt();
iterate.keep(io + 1);
}
StdOut.println(lss);
StdOut.println();
StdOut.println("Multiply each element by 3");
while (iterate.hasEarlier()) {
int io = iterate.previous();
iterate.keep(io + io + io);
}
StdOut.println(lss);
StdOut.println();
StdOut.println("Remove elements which are multiple of 4");
while (iterate.hsNxt()) {
int io = iterate.nxt();
if (io % 4 == 0) iterate.rm();
}
StdOut.println(lss);
StdOut.println();
StdOut.println("Remove elements that are even");
while (iterate.hasEarlier()) {
int io = iterate.previous();
if (io % 2 == 0) iterate.rm();
}
StdOut.println(lss);
StdOut.println();
StdOut.println("Add elements");
while (iterate.hsNxt()) {
int io = iterate.nxt();
iterate.add(io + 1);
}
StdOut.println(lss);
StdOut.println();
StdOut.println("Add elements");
while (iterate.hasEarlier()) {
int io = iterate.previous();
iterate.add(io * 10);
iterate.previous();
}
StdOut.println(lss);
StdOut.println();
}
}
Please rate the answer if it helped....Thankyou
Hope it helps.....
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.