SUBMIT LINKEDLIST.JAVA WITH FOLLOWING TWO METHODS ADDED. MUST BE GOOD FORWARDS AND BACKWARD LINKS. CODE PASTED BELOW

isPerfectMirror(); returns true if this list is a mirror. Use the Chapter 15 exercise #18 definition of mirror(). For example, if this LinkedList contains the values ["a", "b", "c", "c", "b", "a"] then isPerfectMirror() returns true, while ["a", "b", "c"] would return false.

B. undoMirror(); a void method that will undo the mirror if this list is mirrored, as in isPerfectMirror() returns true. Whenever isPerfectMirror() is false, the undoMirror() method leaves this list unchanged..

import java.util.*; // Class LinkedList can be used to store a list of values of type E.

public class LinkedList> implements Iterable{ // 2017, removed implements List due to version differences of List private ListNode front; // first value in the list private ListNode back; // last value in the list private int size; // current number of elements

// NOTE: an empty list has TWO Nodes to mark front and back // post: constructs an empty list public LinkedList() { front = new ListNode(null); back = new ListNode(null); clear(); }

// post: returns the current number of elements in the list public int size() { return size; }

// pre : 0 <= index < size() (throws IndexOutOfBoundsException if not) // post: returns the value at the given index in the list public E get(int index) { checkIndex(index); ListNode current = nodeAt(index); return current.data; }

// post: creates a comma-separated, bracketed version of the list public String toString() { if (size == 0) { return "[]"; } else { String result = "[" + front.next.data; ListNode current = front.next.next; while (current != back) { result += ", " + current.data; current = current.next; } result += "]"; return result; } }

// post: creates a comma-separated, bracketed version of the list // Iverson creation public String backwards() { if (size == 0) { return "[]"; } else { String result = "[" + back.prev.data; ListNode current = back.prev.prev; while (current != front) { result += ", " + current.data; current = current.prev; } result += "]"; return result; } }

// post : returns the position of the first occurrence of the given // value (-1 if not found) public int indexOf(E value) { int index = 0; ListNode current = front.next; while (current != back) { if (current.data.equals(value)) { return index; } index++; current = current.next; } return -1; }

// post: returns true if list is empty, false otherwise public boolean isEmpty() { return size == 0; }

// post: returns true if the given value is contained in the list, // false otherwise public boolean contains(E value) { return indexOf(value) >= 0; }

// post: appends the given value to the end of the list public void add(E value) { add(size, value); }

// pre: 0 <= index <= size() (throws IndexOutOfBoundsException if not) // post: inserts the given value at the given index, shifting subsequent values right public void add(int index, E value) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("index: " + index); } ListNode current = nodeAt(index - 1); ListNode newNode = new ListNode(value, current.next, current); current.next = newNode; newNode.next.prev = newNode; size++; }

// post: appends all values in the given list to the end of this list public void addAll(List other) { for (E value: other) { add(value); } }

// pre : 0 <= index < size() (throws IndexOutOfBoundsException if not) // post: removes value at the given index, shifting subsequent values left public void remove(int index) { checkIndex(index); ListNode current = nodeAt(index - 1); current.next = current.next.next; current.next.prev = current; size--; }

// pre : 0 <= index < size() (throws IndexOutOfBoundsException if not) // post: replaces the value at the given index with the given value public void set(int index, E value) { checkIndex(index); ListNode current = nodeAt(index); current.data = value; }

// post: list is empty public void clear() { front.next = back; back.prev = front; size = 0; }

// post: returns an iterator for this list public Iterator iterator() { return new LinkedIterator(); }

// pre : 0 <= index < size() // post: returns the node at a specific index. Uses the fact that the list // is doubly-linked to start from the front or the back, whichever // is closer. private ListNode nodeAt(int index) { ListNode current; if (index < size / 2) { current = front; for (int i = 0; i < index + 1; i++) { current = current.next; } } else { current = back; for (int i = size; i >= index + 1; i--) { current = current.prev; } } return current; }

// post: throws an IndexOutOfBoundsException if the given index is // not a legal index of the current list private void checkIndex(int index) { if (index < 0 || index >= size()) { throw new IndexOutOfBoundsException("index: " + index); } }

private static class ListNode { public E data; // data stored in this node public ListNode next; // link to next node in the list public ListNode prev; // link to previous node in the list

// post: constructs a node with given data and null links public ListNode(E data) { this(data, null, null); }

// post: constructs a node with given data and given links public ListNode(E data, ListNode next, ListNode prev) { this.data = data; this.next = next; this.prev = prev; } }

private class LinkedIterator implements Iterator { private ListNode current; // location of next value to return private boolean removeOK; // whether it's okay to remove now

// post: constructs an iterator for the given list public LinkedIterator() { current = front.next; removeOK = false; }

// post: returns true if there are more elements left, false otherwise public boolean hasNext() { return current != back; }

// pre : hasNext() // post: returns the next element in the iteration public E next() { if (!hasNext()) { throw new NoSuchElementException(); } E result = current.data; current = current.next; removeOK = true; return result; }

// pre : next() has been called without a call on remove (i.e., at most // one call per call on next) // post: removes the last element returned by the iterator public void remove() { if (!removeOK) { throw new IllegalStateException(); } ListNode prev2 = current.prev.prev; prev2.next = current; current.prev = prev2; size--; removeOK = false; } } }