Write a non-member method named listReplacer() that receives as parameter a SinglyLinkedList L, and two elements e and f.

The method replaces each copy of e with f in the list in time O(n)(), where n = L.size(). 

Solutions that are not O(n)() will get at most 50% of the score. 

If e is not found, then the method returns a list that has the same elements as L. Notice that this method modifies L! 

For example, if L = {Bob, Apu, Ned, Joe, Apu}, then a call to listReplacer(L, Apu, Kim ) produces {Bob, Kim, Ned, Joe, Kim}. 

Hint: Use an auxilary list to help you out, take advantage of the fact that Linked Lists have O(1)(1) time when adding, removing and inspecting at position 0 because all it does is it modifies or inspects header.getNext()

import java.util.Iterator; import java.util.NoSuchElementException;

public class LinkedListWrapper { public static interface List extends Iterable { public int size(); public boolean isEmpty(); public boolean isMember(E e); public int firstIndexOf(E e); public int lastIndexOf(E e);

public void add(E e); public void add(E e, int index); public E get(int index); public E remove(int index); public boolean remove(E e); public int removeAll(E e); public E replace(int index, E newElement); public void clear(); public Object[] toArray(); public void addAfter(E e, E f);

} public static class SinglyLinkedList implements List {

@SuppressWarnings("hiding") private class SinglyLinkedListIterator implements Iterator{ private Node nextNode;

@SuppressWarnings("unchecked") public SinglyLinkedListIterator() { this.nextNode = (Node) header.getNext(); } @Override public boolean hasNext() { return nextNode != null; }

@Override public E next() { if (this.hasNext()) { E result = this.nextNode.getElement(); this.nextNode = this.nextNode.getNext(); return result; } else { throw new NoSuchElementException(); } } } private static class Node { private E element; private Node next; public Node(E element, Node next) { super(); this.element = element; this.next = next; } public Node() { super(); } public E getElement() { return element; } public void setElement(E element) { this.element = element; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; }

}

private Node header; private int currentSize; public SinglyLinkedList() { this.header = new Node<>(); this.currentSize = 0; } @Override public int size() { return this.currentSize; }

@Override public boolean isEmpty() { return this.size() == 0; }

@Override public boolean isMember(E e) { return this.firstIndexOf(e) >= 0; }

@Override public int firstIndexOf(E e) { int i = 0; for (Node temp = this.header.getNext(); temp != null; temp = temp.getNext(), ++i) { if (temp.getElement().equals(e)) { return i; } } // not found return -1; }

@Override public void add(E e) { if (this.isEmpty()) { this.header.setNext(new Node(e, null)); this.currentSize++; } else { Nodetemp= this.header.getNext(); while (temp.getNext() != null) { temp = temp.getNext(); } Node newNode = new Node<>(e, null); temp.setNext(newNode); this.currentSize++; } }

@Override public void add(E e, int index) { if ((index < 0) || (index > this.currentSize)) { throw new IndexOutOfBoundsException(); } if (index == this.currentSize) { this.add(e); } else { Node temp = null; if (index == 0) { temp = this.header; } else { temp = this.getPosition(index -1); } Node newNode = new Node<>(); newNode.setElement(e); newNode.setNext(temp.getNext()); temp.setNext(newNode); this.currentSize++; } }

@Override public E get(int position) { if ((position < 0) || position >= this.currentSize) { throw new IndexOutOfBoundsException(); } Node temp = this.getPosition(position); return temp.getElement(); }

}

@Override public int removeAll(E e) { int count = 0; while (this.remove(e)) { count++; } return count; }

@Override public void addAfter(E e, E f) { // ADD YOUR CODE HERE }

} }