I need help with this.

Submit LinkedList.java with the following methods added:

MUST start with LinkedList.java and add these four methods (or more).

Above file is modified from text (e.g. fixed List, Iterable, Comparable).

Added a backwards() method so we can check both directions.

All your methods must work for empty or identical lists.

1.Write a method min that returns the minimum value in a list of integers. If the list is empty, it should throw a NoSuchElementException.

2. Write a method countDuplicates that returns the number of duplicates in a sorted list. The list will be in sorted order, so all of the duplicates will be grouped together. For example, if a variable list stores the sequence of values below, the call of list.countDuplicates() should return 7 because there are 2 duplicates of 1, 1 duplicate of 3, 1 duplicate of 15, 2 duplicates of 23 and 1 duplicate of 40: [1, 1, 1, 3, 3, 6, 9, 15, 15, 23, 23, 23, 40, 40]

Remember that you may assume that the list is in sorted order, so any duplicates would occur consecutively.

3. Write a method stutter that doubles the size of a list by replacing every integer in the list with two of that integer. For example, suppose a variable list stores the following sequence of integers:

[1, 8, 19, 4, 17] 

After a call of list.stutter(), it should store the following sequence of integers:

[1, 1, 8, 8, 19, 19, 4, 4, 17, 17] 

4. Write a method removeAll that removes all occurrences of a particular value. For example, if a variable list contains the following values:

[3, 9, 4, 2, 3, 8, 17, 4, 3, 18] 

The call of list.removeAll(3); would remove all occurrences of the value 3 from the list, yielding the following values:

[9, 4, 2, 8, 17, 4, 18] 

If the list is empty or the value doesn't appear in the list at all, then the list should not be changed by your method. You must preserve the original order of the elements of the list.

Test code.

LinkedList A = new LinkedList(); LinkedList B = new LinkedList(); B.add(1); B.add(19); B.add(4); B.add(17); B.stutter(); A.removeAll("nothing");

LinkedList.java:

public class LinkedList> implements Iterable{ // 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

// post: constructs an empty list public LinkedList() { front = new ListNode(null); back = new ListNode(null); clear(); } // ADD MORE METHODS HERE :

// 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; } } }