Design a SelfAdjustingList class that extends DoublyLinkedList. Make your code as simple as possible! Only override a method if it is absolutely necessary. Test thoroughly.

public class SelfAdjustingList extends DoublyLinkedList {

// TODO: New code goes here. /** * Simple testing to get you started. Add more tests of your own! */ public static void main(String... args) { SelfAdjustingList xs = new SelfAdjustingList<>(); for (int x = 1; x <= 10; x++) xs.add(x); for (int i = 0; i < xs.size(); i++) assert 10 - i == xs.get(i); for (int i = 0; i < xs.size(); i++) { int x = xs.get(i); assert x == xs.find(i); } for (int i = 0; i < xs.size(); i++) { int x = xs.find(i); assert x == xs.get(0); } System.out.println("All tests passed..."); } }

DoublyLinkedList class:

/**

* hw3: Problem 1 starter code.

*

* Hallmarks of a DoublyLinkedList:

* - headnode (also called a dummy node)

* - backward pointers to the previous node in the list

* - circularity: last node points forward to the headnode and the

* headnode points backward to the last node

*/

import java.util.Iterator;

public class DoublyLinkedList implements List {

/**

* Node is a pair containing a data field and a pointers to

* the previous and next nodes in the list.

*/

class Node {

T data;

Node next, prev;

Node(T data) {

this(data, null, null);

}

Node(T data, Node prev, Node next) {

this.data = data;

this.prev = prev;

this.next = next;

}

}

Node head; // always points to the headnode for this list

int n; // the number of nodes in this list, initially 0

/**

* Creates the empty list.

*/

public DoublyLinkedList() {

// TODO: Create the headnode.

// Note that the prev and next fields in the headnode should

// point back to the headnode.

}

/**

* Inserts the value x at the end of this list.

*/

public void add(T x) {

// TODO: This must run in O(1) time.

}

/**

* Removes the element at index i from this list.

* @return the data in the removed node.

* @throw IndexOutOfBoundsException iff i is out of range for this list.

*/

public T remove(int i) {

if (i < 0 || i >= size())

throw new IndexOutOfBoundsException();

// TODO: Don't forget to skip over the headnode.

return null;

}

/**

* Returns the i-th element from this list, where i is a zero-based index.

* @throw IndexOutOfBoundsException iff i is out of range for this list.

*/

public T get(int i) {

if (i < 0 || i >= size())

throw new IndexOutOfBoundsException();

// TODO: Don't forget to skip over the headnode.

return null;

}

/**

* Returns true iff the value x appears somewhere in this list.

*/

public boolean contains(T x) {

// TODO: Don't forget to skip over the headnode.

return false;

}

/**

* Returns the number of elements in this list.

*/

public int size() {

return n;

}

/**

* Returns an iterator for this list.

*/

public Iterator iterator() {

return new Iterator() {

public boolean hasNext() {

// TODO

return false;

}

public T next() {

// TODO

return null;

}

public void remove() {

// TODO: This must run in O(1) time.

}

};

}

/**

* Returns a string representing this list (resembling a Racket list).

*/

public String toString() {

if (isEmpty())

return "()";

Iterator it = iterator();

StringBuilder ans = new StringBuilder("(").append(it.next());

while (it.hasNext())

ans.append(" ").append(it.next());

return ans.append(")").toString();

}

/**

* Simple testing to get you started. Add more tests of your own!

*/

public static void main(String... args) {

DoublyLinkedList xs = new DoublyLinkedList<>();

int[] a = new int[] { 4, 3, 6, 5, 7, 8 };

for (int x : a)

xs.add(x);

assert 6 == xs.size();

for (int i = 0; i < a.length; i++)

assert xs.get(i) == a[i];

assert !xs.contains(null);

for (int x : a)

assert xs.contains(x);

assert "(4 3 6 5 7 8)".equals(xs.toString());

assert xs.remove(0) == 4;

assert xs.remove(1) == 6;

assert 4 == xs.size();

assert "(3 5 7 8)".equals(xs.toString());

while (!xs.isEmpty())

xs.remove(xs.size() - 1);

assert 0 == xs.size();

for (int x : a)

xs.add(x);

for (int x : xs)

assert xs.contains(x);

Iterator it = xs.iterator();

while (it.hasNext())

if (it.next() % 2 == 0)

it.remove();

assert 3 == xs.size();

assert "(3 5 7)".equals(xs.toString());

System.out.println("All tests passed...");

}

}

/**

* If you want to call yourself a List, then implement this interface:

*/

interface List extends Iterable {

void add(T x); // simple add

T remove(int i);

T get(int i);

boolean contains(T x);

int size();

default boolean isEmpty() {

return size() == 0;

}

}