((----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;

}

}

}

((---TestMyDoublyLinkedList.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"));

}

}