JAVA. Code that must be completed is below(where it says must be completed). Wri
ID: 3855188 • Letter: J
Question
JAVA. Code that must be completed is below(where it says must be completed). Written in bold.
Starting from the implementation of LinkedList300 from the accompanying hw4.jar file, complete a method for this class called copyList. It returns a new LinkedList300 item which contains the same data as the old linked list, in the same sequence.
The TestHW4 class makes a sample call to the copyList method. When properly implemented, the ouptput should be
You will receive 1 point of extra credit if you write this method such that it runs in (n) time, where n is the number of items in the 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() {
return this; // 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 answer is as follows:
The code for creating a copy of a list is as follows:
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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.