In Java, your task is to create a public, concrete class named MyDoublyLinkedList that extends MyAbstractSequentialList and implements Cloneable:

public class MyDoublyLinkedList extends MyAbstractSequentialList implements Cloneable {

The class must override the clone and equals methods that are inherited from the Object class. All supported methods should work just like those in java.util.LinkedList.

You are required to implement your class by using a circular doubly-linked list with a dummy head node.

Each node object should have three data fields: one for the element, one for the previous node, and one for the next node. Where the diagrams above use the name listHead, I will use the name head. Note that the first element of a non-empty list is head.next.element. The last element is head.prev.element. In your list class you will not need a separate data field that points to the tail. If you find yourself using a data field called tail then you are not implementing the data structure properly.

The methods contains, indexOf, and lastIndexOf should compare elements to e by using the equals method. You may need to handle a null value as a special case because the call e.equals() will throw a NullPointerException if e is null. The following description (from http://docs.oracle.com/javase/7/docs/api/java/util/List.html) of the contains method shows a good way to handle this:

boolean contains(Object e)

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element o such that (e == null ? o == null : e.equals(o)).

remove and set should throw an IndexOutOfBoundsException if index = size(). When set does not throw an exception, it should return the element that was previously at the given index. add should throw an IndexOutOfBoundsException if index size().

Iterators:

You will need to write an inner class that implements the ListIterator interface. Note that the remove and set methods need to throw an IllegalStateException in certain circumstances.

/**

* Inserts the specified element into the list. The element is inserted

* immediately before the element that would be returned by next(), if

* any, and after the element that would be returned by previous(), if

* any. (If the list contains no elements, the new element becomes the

* sole element on the list.) The new element is inserted before the

* implicit cursor: a subsequent call to next would be unaffected, and a

* subsequent call to previous would return the new element. (This call

* increases by one the value that would be returned by a call to

* nextIndex or previousIndex.)

*/

void add(E e);

/**

* Removes from the list the last element that was returned by next()

* or previous(). This call can only be made once per call to next or

* previous. It can be made only if add(E) has not been called after the

* last call to next or previous.

* throws IllegalStateException if neither next nor previous have been

* called, or remove or add have been called after the last call to next

* or previous.

*/

void remove();

/**

* Replaces the last element returned by next() or previous() with the

* specified element. This call can be made only if neither remove() nor

* add(E) have been called after the last call to next or previous.

* throws IllegalStateException if neither next nor previous have been

* called, or remove or add have been called after the last call to next

* or previous.

*/

void set(E e);

Note also that an iterators next method should throw a NoSuchElementException if there is no next element. Likewise, a list iterators previous method should throw a

NoSuchElementException if there is no previous element.

clone() method:

Here is the Java documentation for the clone() method

public Object clone()

Returns a shallow copy of this LinkedList. (The elements themselves are not cloned.)

You also do not want a throws declaration in the header of your clone method. Following the format of that example, here is one good way to accomplish your task: Inside your try block, after you have called super.clone, allocate a new Node for the dummy head. Then make the next and previous from the clones head point back to the clones head. Set the size data field of the clone to 0. Then use an iterator and a loop to iterate through this list and add every element to the clone. Finally, return the clone. In the catch block of your clone method you can just throw a RuntimeException. That catch block should never be executed. Here is the above algorithm expressed as pseudocode:

clone(): try

Create the clone by calling super.clone.

Make the clone's head point to a new dummy head node.

Make the next and previous in the clone's dummy head node point back to the clone's dummy head node.

Initially set size of the clone to 0.

Iterate through this linked list, adding each element to the clone by calling the clone's add method.

Return the clone.

catch CloneNotSupportedException

If you've done things correctly, this catch block should never execute. But for good style throw some sort of RuntimeException.

equals(Object other) method:

The equals method should return true if and only if other is an instance of MyList with the same size as this list and with the corresponding elements equal to the elements of this list. Here is some pseudocode for a good way to accomplish this:

equals(Object other): if this == other return true

else if other is not an instance of MyList return false

if other's size != this's size return false else

get an iterator to this get an iterator to other

if corresponding elements are not equal* return false

return true

In the above algorithm, once you get past the check that ensures that other is an instance of MyList, you can typecast other to type (MyList>). This will enable you to call methods such as size() and iterator().

*Note that lists are allowed to have null elements. Your equals method should not throw a NullPointerException in that case. Deal with this issue like you did in the contains, indexOf, and lastIndexOf methods. I.e., you should use the == operator to compare a null reference, but use the equals method to compare actual objects.

MyDoublyLinkedList.java: import java.util.*; public class MyDoublyLinkedList extends MyAbstractSequentialList implements Cloneable { private Node head = new Node(null); /** Create a default list */ public MyDoublyLinkedList() { head.next = head; head.previous = head; } private static class Node { E element; Node previous; Node next; public Node(E element) { this.element = element; } } public String toString() { StringBuilder result = new StringBuilder("["); Node current = head.next; for (int i = 0; i index; i--) current = current.previous; return current; } @Override public void add(int index, E e) { if (index size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } Node prev = getNode(index - 1); Node next = prev.next; Node newNode = new Node(e); prev.next = newNode; next.previous = newNode; newNode.previous = prev; newNode.next = next; size++; } @Override public void clear() { // TODO Auto-generated method stub } @Override public boolean contains(E o) { for (Node current = head.next; current != head; current = current.next) { E e = current.element; if (o == null ? e == null : o.equals(e)) return true; } return false; } @Override public E get(int index) { // TODO Auto-generated method stub return null; } @Override public int indexOf(E e) { // TODO Auto-generated method stub return 0; } @Override public int lastIndexOf(E e) { // TODO Auto-generated method stub return 0; } @Override public E remove(int index) { // TODO Auto-generated method stub return null; } @Override public Object set(int index, E e) { // TODO Auto-generated method stub return null; } @Override public E getFirst() { // TODO Auto-generated method stub return null; } @Override public E getLast() { // TODO Auto-generated method stub return null; } @Override public void addFirst(E e) { add(0, e); } @Override public void addLast(E e) { // TODO Auto-generated method stub } @Override public E removeFirst() { // TODO Auto-generated method stub return null; } @Override public E removeLast() { // TODO Auto-generated method stub return null; } @Override public ListIterator listIterator(int index) { return new MyDoublyLinkedListIterator(index); } private static enum ITERATOR_STATE { CANNOT_REMOVE, CAN_REMOVE_PREV, CAN_REMOVE_CURRENT }; private class MyDoublyLinkedListIterator implements ListIterator { private Node current; // node that holds the next element in the // iteration private int nextIndex; // index of current ITERATOR_STATE iterState = ITERATOR_STATE.CANNOT_REMOVE; private MyDoublyLinkedListIterator(int index) { if (index size) throw new IndexOutOfBoundsException("iterator index out of bounds"); current = getNode(index); } @Override public void add(E arg0) { // TODO Auto-generated method stub } @Override public boolean hasNext() { return nextIndex = size) throw new NoSuchElementException(); E returnVal = current.element; current = current.next; nextIndex++; iterState = ITERATOR_STATE.CAN_REMOVE_PREV; return returnVal; } @Override public int nextIndex() { // TODO Auto-generated method stub return 0; } @Override public E previous() { // TODO Auto-generated method stub return null; } @Override public int previousIndex() { // TODO Auto-generated method stub return 0; } @Override public void remove() { switch (iterState) { case CANNOT_REMOVE: // ... break; case CAN_REMOVE_PREV: // ... break; case CAN_REMOVE_CURRENT: // ... break; } } @Override public void set(E arg0) { // TODO Auto-generated method stub } } } MyAbstractSequentialList.java: public abstract class MyAbstractSequentialList extends MyAbstractList { /** Create a default list */ protected MyAbstractSequentialList() { } /** Create a list from an array of objects */ protected MyAbstractSequentialList(E[] objects) { super(objects); } public java.util.Iterator iterator() { return listIterator(); } public java.util.ListIterator listIterator() { return listIterator(0); } abstract public E getFirst(); abstract public E getLast(); abstract public void addFirst(E e); abstract public void addLast(E e); abstract public E removeFirst(); abstract public E removeLast(); abstract public java.util.ListIterator listIterator(int index); }

clone ) try tCreate the clone by calling super.clone. Make the clone's head point to a new dummy head node Make the next and previous in the clone's dummy head node point back to the clone's dummy head node. Initially set size of the clone to 0. Iterate through this linked list, adding each element to the clone by calling the clone's add method Return the clone catch CloneNotSupportedException If you've done things correctly, this catch block should never execute. But for good style throw some sort of RuntimeException equals (object other): if this = other else if other is not an instance of MyList if other's size != this's size else return true return false return false get an iterator to this get an iterator to other if corresponding elements are not equal* return false return true *Note that lists are allowed to have null elements Your code should not throw a NullPointException in that case Deal with this issue 1ike you did in the contains, indexof, and lastIndexof methods I.e., you will need to use theoperator to compare references to null, but use the equals method to compare actual objects to each other. (a) listHead AbleBaker Smith .Wso.. Dummy head node (b) 1istHead clone ) try tCreate the clone by calling super.clone. Make the clone's head point to a new dummy head node Make the next and previous in the clone's dummy head node point back to the clone's dummy head node. Initially set size of the clone to 0. Iterate through this linked list, adding each element to the clone by calling the clone's add method Return the clone catch CloneNotSupportedException If you've done things correctly, this catch block should never execute. But for good style throw some sort of RuntimeException equals (object other): if this = other else if other is not an instance of MyList if other's size != this's size else return true return false return false get an iterator to this get an iterator to other if corresponding elements are not equal* return false return true *Note that lists are allowed to have null elements Your code should not throw a NullPointException in that case Deal with this issue 1ike you did in the contains, indexof, and lastIndexof methods I.e., you will need to use theoperator to compare references to null, but use the equals method to compare actual objects to each other. (a) listHead AbleBaker Smith .Wso.. Dummy head node (b) 1istHead