TestDoublyLinkedList.java

public class TestMyDoublyLinkedList {

public static void main(String[] args) {

String[] array = {"A", "B", "A", "A"};

MyDoublyLinkedList list = new MyDoublyLinkedList(array);

System.out.printf("%-32s%-10s ", "Initialized with {A,B,A,A}:", list);

long startTime = System.nanoTime();

testAdding(list);

testGetting(list);

testSetting(list);

testRemoving(list);

testChecking(list);

long endTime = System.nanoTime();

long duration = endTime - startTime;

System.out.println(" duration = " + duration/1000000.0 );

System.out.printf(" %-32s%-10s ", "ToString: " , list);

System.out.printf("%-32s%-10s ", "ToReversedString: " , list.toReversedString());

//the follow code should throw an exception

int Xnum = 20;

System.out.println(" Adding 'X' at : " + Xnum);

if ( Xnum > list.size()) {

Xnum = list.size();

}

System.out.println("size of list = " + list.size());

list.add(Xnum, "X");

System.out.println(list);

}

private static void testAdding(MyDoublyLinkedList list) {

System.out.printf(" %-32s%-10s ", "Adding elements: ", list);

list.addFirst("*"); System.out.printf("%-32s%-10s ", " - '*' at first", list);

list.addLast("C"); System.out.printf("%-32s%-10s ", " - 'C' at last", list);

list.add("D");System.out.printf("%-32s%-10s ", " - 'D'", list);

list.add(2, "#"); System.out.printf("%-32s%-10s ", " - '#' @ 2", list);

}

private static void testGetting(MyDoublyLinkedList list) {

System.out.printf(" %-32s%-10s ", "Getting elements: ", list);

System.out.printf("%-32s%-10s ", " - First Element", list.getFirst());

System.out.printf("%-32s%-10s ", " - Last Element", list.getLast());

System.out.printf("%-32s%-10s ", " - Element at 1", list.get(1));

System.out.printf("%-32s%-10s ", " - Element at 20", list.get(20));

}

private static void testSetting(MyDoublyLinkedList list) {

System.out.printf(" %-32s%-10s ", "Setting elements: ", list);

System.out.printf("%-32s%-10s ", " - Element @ 0: '"+list.set(0,"+")+"' -> '+'", list);

System.out.printf("%-32s%-10s ", " - Element @ 2: '"+list.set(2, "-")+"' -> '-'", list);

System.out.printf("%-32s%-10s ", " - Element @ 9: '"+list.set(9, "&")+"' -> '&'", list);

}

private static void testRemoving(MyDoublyLinkedList list) {

System.out.printf(" %-32s%-10s ", "Removing elements: ", list);

System.out.printf("%-32s%-10s ", " - First element '" + list.removeFirst() + "'", list);

System.out.printf("%-32s%-10s ", " - Last element '" + list.removeLast() + "'", list);

System.out.printf("%-32s%-10s ", " - Element @ 1 '" + list.remove(1) + "'", list);

System.out.printf("%-32s%-10s ", " - Element @ 9 '" + list.remove(9) + "'", list);

}

private static void testChecking(MyDoublyLinkedList list) {

System.out.printf(" %-32s%-10s ", "Checking: ", list);

System.out.printf("%-32s%-10s ", " - Contains 'A'? ", list.contains("A"));

System.out.printf("%-32s%-10s ", " - Contains 'Z'? ", list.contains("Z"));

System.out.printf("%-32s%-10s ", " - First occurence of 'A' @ ", list.indexOf("A"));

System.out.printf("%-32s%-10s ", " - Last occurence of 'A' @ ", list.lastIndexOf("A"));

System.out.printf("%-32s%-10s ", " - First index of 'Z' @", list.indexOf("Z"));

System.out.printf("%-32s%-10s ", " - Last index of 'Z' @", list.lastIndexOf("Z"));

}

}

MyLinkedList.java

public class MyLinkedList {

private int size;

private Node head, tail;

// Constructors

public MyLinkedList() {

head = tail = null;

}

public MyLinkedList(E[] objects) {

for (int i = 0; i

add(objects[i]);

}

// Methods

//*** ADDING ***

public void add(E e) {

addLast(e);

}

public void addFirst(E e) { /** add code to set 'previous' */

Node newNode = new Node(e); // Create a new node

if (tail == null) // if empty list

head = tail = newNode; // new node is the only node in list

else {

newNode.next = head; // link the new node with the head

// **** add new codes here to handle the head.previous ****

head = newNode; // head points to the new node

}

size++;

}

public void addLast(E e) { /** add code to set 'previous' */

Node newNode = new Node(e); // Create a new for element e

if (tail == null) // if empty list

head = tail = newNode; // new node is the only node in list

else {

tail.next = newNode; // Link the new with the last node

tail = tail.next; // tail now points to the last node

// you will replace the above line of code with the new.previous

// and update the tail to newNode....!!

}

size++;

}

public void add(int index, E e){/** add code to set 'previous' & to improve performance */

if (index size)

throw new IndexOutOfBoundsException(); //according to Java doc.

else if (index == 0) addFirst(e);

else if (index == size) addLast(e);

else {

Node newNode = new Node(e);

// you will need to replace the following block of codes with current.previous

// you will write a getNodeAt(index) for the current Node

Node current = head; // ] //

for (int i = 1; i

current = current.next; // ]

newNode.next = current.next; // Link the new node to element @ index

current.next = newNode; // Link element @ index-1 to newNode

size++;

}

}

//*** REMOVING ***

public E removeFirst() { /** add code to set 'previous' */

if (size == 0) // need to add code to set "previous"

return null;

else {

Node temp = head; // element will be returned

head = head.next;

// need to set head.previous = null here **** //

size--;

if (head == null) // if list becomes empty

tail = null;

return temp.element; // return the removed element

}

}

public E removeLast() { /** improve performance using 'previous' */

if (size == 0) // need to add code to set "previous"

return null;

else if (size == 1) {

Node temp = head;

head = tail = null;

size = 0;

return temp.element;

} else {

Node temp = tail; // to return it

// need to update the tail with previous and don't need to current

Node current = head; // get ref. to second to last

for (int i = 0; i

current = current.next;

tail = current;

tail.next = null; // remove last

size--;

return temp.element; // return last

}

}

public E remove(int index) { /** add code to set 'previous' */

if (index = size)

return null;

else if (index == 0)

return removeFirst();

else if (index == size - 1)

return removeLast();

else { // needs new codes to set current with getNodeAt(index) and update previous

Node previous = head;

for (int i = 1; i

previous = previous.next;

Node current = previous.next;

previous.next = current.next;

size--;

return current.element;

}

}

public boolean remove(E e) {

if (indexOf(e) >= 0) { //if the element exists

remove(indexOf(e)); //call the other remove method

return true;

} else

return false;

}

public void clear() {

size = 0;

head = tail = null;

}

//*** GETTING ***

public E getFirst() {

if (size == 0)

return null;

else

return head.element;

}

public E getLast() {

if (size == 0)

return null;

else

return tail.element;

}

public E get(int index) { /** improve performance using 'previous' */

if (index = size)

return null;

else if (index == 0)

return getFirst();

else if (index == size - 1)

return getLast();

else { // needs new code here... getNodeAt(index).element;....to replace the following

Node current = head; // ]

for (int i = 0; i

current = current.next; // ]

return current.element;

}

}

//*** SETTING ***

public E set(int index, E e) { /** improve performance using 'previous' */

if (index size - 1)

return null;

Node current = head; // ** need to replace this with getNodeAt(index) and the following for loop

for (int i = 0; i

current = current.next;

E temp = current.element;

current.element = e;

return temp;

}

//*** TOSTRING ***

public String toString() {

StringBuilder result = new StringBuilder("[");

Node current = head;

for (int i = 0; i

result.append(current.element);

current = current.next;

if (current != null)

result.append(", "); // Separate two elements with a comma

else

result.append("]"); // Insert the closing ] in the string

}

return result.toString();

}

public String toReversedString(){/** write code to return a string representing the list from right to left */

return null;

}

//*** CHECKING ***

public int size(){

return size;}

public boolean contains(E e) {

Node current = head;

for (int i = 0; i

if (current.element.equals(e))

return true;

current = current.next;

}

return false;

}

public int indexOf(E e) {

Node current = head;

for (int i = 0; i

if (current.element.equals(e))

return i;

current = current.next;

}

return -1;

}

public int lastIndexOf(E e) { /** improve performance using 'previous' */

// this whole method needs to be replaced

// set your current Node to tail to start

int lastIndex = -1;

Node current = head;

for (int i = 0; i

if (current.element.equals(e))

lastIndex = i;

current = current.next;

}

return lastIndex;

}

//*** HELPER METHODS ***

private void checkIndex(int idx) {

if (idx = size)

throw new IndexOutOfBoundsException("Index: " + idx + ", Size: "

+ size);

}

private Node getNodeAt(int index){ /** write code for this method to return a reference to a node at a given index */

// a big chunk of codes are here

return null;

}

//*** INNER NODE CLASS ***

private static class Node { /** add code to consider 'previous' */

E element;

Node next; // you need to add previous here

public Node(E e) {

element = e;

}

}

}

For this question, you will convert the given MyLinkedList.java that we discussed in class, to support a doubly linked list operation. The given MyLinkedList.java file is a singly linked list type. Most of code has already been written. (say thank you). You will need to add extra codes to the myLinkedList.java file to support the doubly linked list approach in traversing through the list. In order.to show that the doubly linked list operation is faster that the (given) singly operation, add some time measurement codes to compare the time performance of the two operations. (There are 12 (3 points each) possible locations in the program that that require you to make changes to support doubly linked list operation) For this question, you will convert the given MyLinkedList.java that we discussed in class, to support a doubly linked list operation. The given MyLinkedList.java file is a singly linked list type. Most of code has already been written. (say thank you). You will need to add extra codes to the myLinkedList.java file to support the doubly linked list approach in traversing through the list. In order.to show that the doubly linked list operation is faster that the (given) singly operation, add some time measurement codes to compare the time performance of the two operations. (There are 12 (3 points each) possible locations in the program that that require you to make changes to support doubly linked list operation)