Improving DoublyLinkedList Your assignment is to improve the DoublyLinkedList cl
ID: 3847685 • Letter: I
Question
Improving DoublyLinkedList
Your assignment is to improve the DoublyLinkedList class we wrote in class. Please start with the versionuploaded to Canvas to make sure there is a common starting point, but it should be equivalent to whatwe wrote in class.
size method (30 points)
Implement a method public int size() that returns the number of elements of the list in constanttime. You will need to add a member field to DoublyLinkedList to support it. The member field will haveto be maintained by the other methods as operations are performed to add or remove elements fromthe list.
get method speedup (20 points)
Improve the speed of public T get(int i) by having it work backward from the end of the array ifyou attempt to get a member which is closer to the end than the start. This improvement will be testedthrough timing tests on large lists.
reverse method (25 points)
Implement a method public void reverse() that reverses the list. The list A-B-C-D would becomeD-C-B-A. The old start (A in the example) should be the new end and the old end should be the start. Thenext element after the start should be what was the previous element before the end, and so forth. Themethod should work for a list of any length, including the empty list. This method should not need tocall “new”.
add with index method (25 points)
Implement a method public boolean add(int i, T s) that adds an element with an element oftype T at index i. (Note that this uses Java’s overload facility since we already have an add method withjust a String argument.) Return false if index i does not already exist in the list, otherwise add theelement and return true. (Note that this doesn’t let you add a new element to the very end but theexisting add method accomplishes this.) The elements before index i should be unchanged. Theelements already at index i and after should all be in the same order but at one index value greater thanthey were before the call to add.
Here is the code needed to be improving:
//DoublyLinkedList.java
import java.util.Iterator;
/**
* Generic doubly linked list class.
*
* @param <T>
*/
public class DoublyLinkedList<T> implements Iterable<T> {
/**
* Each element of the DoublyLinkedList class is a node that links to the
* next node and the previous node. There is no next node (next == null) if
* it's the last node (end of the list) and no previous node if it's the
* first node (start of the list)
*
* @param <T>
*/
private static class Node<T> {
public T data; // Data within each node
// Previous has a smaller index (closer to start)
// Next has a larger index (closer to end)
public Node<T> prev, next;
}
/**
* The conductor is capable of walking down the "train" of nodes. This
* allows it to follow Java's "iterator" interface.
*
* @param <T>
*/
private static class Conductor<T> implements Iterator<T> {
private Node<T> current;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public T next() {
// Retrieve passenger from current car
T s = current.data;
// Conductor advances to next car
current = current.next;
return s;
}
public Conductor(Node<T> n) {
current = n;
}
}
// First and last nodes of the list.
private Node<T> start, end;
/**
* Create an empty list.
*/
public DoublyLinkedList() {
start = end = null;
}
/**
* Add an element to the end.
*
* @param s
* Data for that element
*/
public void add(T s) {
if (start == null) {
assert end == null;
start = end = new Node<T>();
start.data = s;
// end == start so it doesn't need to be changed
// start.next and start.prev are both null
} else {
// Add to the end
// First, attaching a new boxcar to the end
end.next = new Node<T>();
// Next, building a doorway from the new last to the old last
end.next.prev = end;
// Then, setting up the data member of the new last boxcar
end.next.data = s;
// Finally, new last boxcar is the last boxcar!
end = end.next;
}
}
/**
* Access element at index i (0 based). start has index 0. Runs in O(i) time
* (fast to access near the start, slow near the end)
*
* @param i
* @return data in element at index i or null if i is not a valid index
*/
public T get(int i) {
Node<T> n = start;
if (i < 0)
return null;
try {
for (int j = 0; j < i; j++) {
n = n.next;
}
return n.data;
} catch (NullPointerException e) {
return null; // Not a valid index
}
}
/**
* Remove an element from the list. Repairs the list so that it's connected
* but without that element. Runs in O(i) time.
*
* @param i
* @return data in removed element or null if i is not a valid index
*/
public T remove(int i) {
Node<T> n = start;
if (i < 0)
return null;
try {
for (int j = 0; j < i; j++) {
n = n.next;
}
// NOTE: n could be null, but then we would
// get caught by our null pointer catch clause
// Let's say we have a list x-A-B-C-x
// where next is to the right of each node
// and we want to remove B (variable n)
// The new list would be x-A-C-x
// First we will connect A to C.
if (n.prev != null) {
// If there is such an A
// Change its next variable to C
n.prev.next = n.next;
} else {
// If there is no such A,
// we must be the start of the list
assert n == start;
start = n.next;
}
// Then we will connect C to A
if (n.next != null) {
// If there is such a C
// Change its prev variable to A
n.next.prev = n.prev;
} else {
// If there is no such C,
// we must be the end of the list
assert n == end;
end = n.prev;
}
return n.data;
} catch (NullPointerException e) {
return null; // Not a valid index
}
}
@Override
public Iterator<T> iterator() {
return new Conductor<T>(start);
}
}
And here is the code that tests if DoublyLinkedList.java works well
TEST CODES
import java.util.Random;
public class DoublyLinkedListTester {
public static void main(String[] args) {
int sizeScore = 0, getScore = 0, revScore = 0, addScore = 0;
try {
DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
list.reverse();
int n = 1000000;
for (int i = 0; i < n; i++) {
list.add(i);
if (i == n / 2) {
list.reverse();
int j = i;
for (int k : list) {
if (k != j) {
System.out.println("Unexpected value in reversed array! Expected " + j + " got " + k);
break;
}
j--;
}
if (j == -1) {
revScore += 10;
} else {
System.out.println("Reversed array contained error at index " + (i - j));
}
j = 0;
list.reverse();
for (int k : list) {
if (k != j) {
System.out.println("Unexpected value in re-reversed array! Expected " + j + " got " + k);
break;
}
j++;
}
if (j == i + 1) {
revScore += 10;
} else {
System.out.println("Re-reversed array contained error at index " + j);
}
}
}
int s;
{
long start = System.currentTimeMillis();
s = list.size();
long end = System.currentTimeMillis();
if (end - start > 10) {
System.out.println("Size of list was slow! Took " + (end - start) + " ms.");
} else {
sizeScore += 10;
}
}
if (s != n) {
System.out.println("Size incorrect after adding " + n + " elements! You report " + list.size());
} else {
sizeScore += 10;
}
Random r = new Random();
int n2 = 100;
int[] vals = new int[n2];
for (int i = 0; i < n2; i++) {
int ri = r.nextInt();
vals[i] = ri;
list.add(ri);
}
int count = 0;
{
long start = System.currentTimeMillis();
for (int i = 0; i < n2; i++) {
if (list.get(n) != vals[i]) {
System.out.println("Get didn't work for element " + n + ": got " + list.get(n)
+ " expected " + vals[i]);
} else
count++;
list.remove(1);
}
if (count == n2) {
getScore += 10;
}
long end = System.currentTimeMillis();
if (end - start > 20) {
System.out.println("Get was slow! Took " + (end - start) + " ms.");
} else {
getScore += 10;
}
}
list.remove(-1);
list.remove(n + n2);
if (list.size() != n) {
System.out.println("Wrong size after more adds and removes! Expected " + n + " got " + list.size());
} else {
sizeScore += 5;
}
for (int i = n2; i >= 0; i--) {
if (!list.add(i, -i - 1)) {
System.out.println("Complained when adding " + (-i - 1) + " to index " + i);
break;
}
int saw = list.get(i);
if (saw != -i - 1) {
System.out.println(
"Insert at index " + i + " did not place " + (-i - 1) + " there - instead, saw " + saw);
break;
}
if (i == 0) {
addScore += 10;
}
}
if (list.size() != n + n2 + 1) {
System.out.println("Wrong size after indexed adds! Expected " + (n + 101) + " got " + list.size());
} else {
sizeScore += 5;
}
if (list.remove(1) != 0) {
System.out.println("First element should be 0 because list.remove(1) ignored element 0");
} else {
addScore += 2;
}
for (int i = 0; i < n2; i++) {
int saw = list.remove(i + 2);
if (saw != i + n2 + 1) {
System.out.println("Alternating removals expected to see " + (i + n2 + 1) + " but saw " + saw);
break;
}
if (i == n2 - 1) {
addScore += 10;
}
}
list.reverse();
{
int j = -n2 - 1;
int k = -1;
for (int i : list) {
k++;
if (k < n - n2 - 1)
continue; // Skip first (was last) part of list
if (i != j) {
System.out.println("Element retrieved " + i
+ " not the expected value inserted from list.add(i, -i - 1) " + j);
System.out.println("This error affects both your reverse and add method scores.");
break;
}
j++;
}
if (k == list.size() - 1) {
revScore += 5;
addScore += 3;
}
}
} finally {
System.out.println("Size method: " + sizeScore + " / 30");
System.out.println("Get method: " + getScore + " / 20");
System.out.println("Reverse method: " + revScore + " / 25");
System.out.println("Add with index method: " + addScore + " / 25");
System.out.println("Tentative score: " + (sizeScore + getScore + revScore + addScore) + " / 100");
}
}
}
Explanation / Answer
import java.util.Iterator;
public class DoublyLinkedList<T> implements Iterable<T> {
private static class Node<T> {
public T data; // Data within each node
public Node<T> prev, next;
}
private static class Conductor<T> implements Iterator<T> {
private Node<T> current;
public boolean hasNext() {
return current != null;
}
public T next() {
T s = current.data;
current = current.next;
return s;
}
public Conductor(Node<T> n) {
current = n;
}
}private Node<T> start, end;
public DoublyLinkedList() {
start = end = null;
}
public void add(T s) {
if (start == null) {
assert end == null;
start = end = new Node<T>();
start.data = s;
} else {
end.next = new Node<T>();
end.next.prev = end;
end.next.data = s;
end = end.next;
}
}public T get(int i) {
Node<T> n = start;
if (i < 0)
return null;
try {
for (int j = 0; j < i; j++) {
n = n.next;
}
return n.data;
} catch (NullPointerException e)
{
return null;
}
}public T remove(int i) {
Node<T> n = start;
if (i < 0)
return null;
try {
for (int j = 0; j < i; j++)
{
n = n.next;
}
if (n.prev != null)
{
n.prev.next = n.next;
} else {
assert n == start;
start = n.next;
}if (n.next != null)
{
n.next.prev = n.prev;
} else
{
assert n == end;
end = n.prev;
}
return n.data;
} catch (NullPointerException e) {
return null;
}
}
@Override
public Iterator<T> iterator() {
return new Conductor<T>(start);
}
}
import java.util.Random;
public class DoublyLinkedListTester {
public static void main(String[] args) {
int sizeScore = 0, getScore = 0, revScore = 0, addScore = 0;
try {
DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
list.reverse();
int n = 1000000;
for (int i = 0; i < n; i++) {
list.add(i);
if (i == n / 2) {
list.reverse();
int j = i;
for (int k : list) {
if (k != j) {
System.out.println("Unexpected value in reversed array! Expected " + j + " got " + k);
break;
}
j--;
}
if (j == -1) {
revScore += 10;
} else {
System.out.println("Reversed array contained error at index " + (i - j));
}
j = 0;
list.reverse();
for (int k : list) {
if (k != j) {
System.out.println("Unexpected value in re-reversed array! Expected " + j + " got " + k);
break;
}
j++;
}
if (j == i + 1) {
revScore += 10;
} else {
System.out.println("Re-reversed array contained error at index " + j);
}
}
}
int s;
{
long start = System.currentTimeMillis();
s = list.size();
long end = System.currentTimeMillis();
if (end - start > 10) {
System.out.println("Size of list was slow! Took " + (end - start) + " ms.");
} else {
sizeScore += 10;
}
}
if (s != n) {
System.out.println("Size incorrect after adding " + n + " elements! You report " + list.size());
}
else
{
sizeScore += 10;
}
Random r = new Random();
int n2 = 100;
int[] vals = new int[n2];
for (int i = 0; i < n2; i++) {
int ri = r.nextInt();
vals[i] = ri;
list.add(ri);
}
int count = 0;
{
long start = System.currentTimeMillis();
for (int i = 0; i < n2; i++) {
if (list.get(n) != vals[i]) {
System.out.println("Get didn't work for element " + n + ": got " + list.get(n)
+ " expected " + vals[i]);
} else
count++;
list.remove(1);
}
if (count == n2) {
getScore += 10;
}
long end = System.currentTimeMillis();
if (end - start > 20) {
System.out.println("Get was slow! Took " + (end - start) + " ms.");
} else {
getScore += 10;
}
}
list.remove(-1);
list.remove(n + n2);
if (list.size() != n) {
System.out.println("Wrong size after more adds and removes! Expected " + n + " got " + list.size());
} else {
sizeScore += 5;
}
for (int i = n2; i >= 0; i--) {
if (!list.add(i, -i - 1)) {
System.out.println("Complained when adding " + (-i - 1) + " to index " + i);
break;
}
int saw = list.get(i);
if (saw != -i - 1) {
System.out.println(
"Insert at index " + i + " did not place " + (-i - 1) + " there - instead, saw " + saw);
break;
}
if (i == 0) {
addScore += 10;
}
}
if (list.size() != n + n2 + 1) {
System.out.println("Wrong size after indexed adds! Expected " + (n + 101) + " got " + list.size());
} else {
sizeScore += 5;
}
if (list.remove(1) != 0) {
System.out.println("First element should be 0 because list.remove(1) ignored element 0");
} else {
addScore += 2;
}
for (int i = 0; i < n2; i++) {
int saw = list.remove(i + 2);
if (saw != i + n2 + 1) {
System.out.println("Alternating removals expected to see " + (i + n2 + 1) + " but saw " + saw);
break;
}
if (i == n2 - 1) {
addScore += 10;
}
}
list.reverse();
{
int j = -n2 - 1;
int k = -1;
for (int i : list) {
k++;
if (k < n - n2 - 1)
continue; // Skip first (was last) part of list
if (i != j) {
System.out.println("Element retrieved " + i
+ " not the expected value inserted from list.add(i, -i - 1) " + j);
System.out.println("This error affects both your reverse and add method scores.");
break;
}
j++;
}
if (k == list.size() - 1)
{
revScore += 5;
addScore += 3;
}
}
}
finally
{
System.out.println("Size method: " + sizeScore + " / 30");
System.out.println("Get method: " + getScore + " / 20");
System.out.println("Reverse method: " + revScore + " / 25");
System.out.println("Add with index method: " + addScore + " / 25");
System.out.println("Tentative score: " + (sizeScore + getScore + revScore + addScore) + " / 100");
}
}
}