LList

// Write methods called insertAfterEvery(), and replace()

/**
 * A linked implemention of the ADT list.
 *
 * @author Frank M. Carrano
 * @author Timothy M. Henry
 * @version 5.0
 */
public class LList<T extends Comparable<? super T>> implements ListInterface<T> {
    private Node firstNode; // Reference to first node of chain
    private int numberOfEntries;

    public LList() {
        initializeDataFields();
    } // end default constructor

    public void clear() {
        initializeDataFields();
    } // end clear

    public void add(T newEntry) // OutOfMemoryError possible
    {
        Node newNode = new Node(newEntry);

        if (isEmpty())
            firstNode = newNode;
        else // Add to end of nonempty list
        {
            Node lastNode = getNodeAt(numberOfEntries);
            lastNode.setNextNode(newNode); // Make last node reference new node
        } // end if

        numberOfEntries++;
    } // end add

    public void add(int givenPosition, T newEntry) // OutOfMemoryError possible
    {
        if ((givenPosition >= 1) && (givenPosition <= numberOfEntries + 1)) {
            Node newNode = new Node(newEntry);
            if (givenPosition == 1) // Case 1
            {
                newNode.setNextNode(firstNode);
                firstNode = newNode;
            } else // Case 2: list is not empty
            { // and givenPosition > 1
                Node nodeBefore = getNodeAt(givenPosition - 1);
                Node nodeAfter = nodeBefore.getNextNode();
                newNode.setNextNode(nodeAfter);
                nodeBefore.setNextNode(newNode);
            } // end if
            numberOfEntries++;
        } else
            throw new IndexOutOfBoundsException("Illegal position given to add operation.");
    } // end add

    public void addAll(T[] items) {
        Node currentNode = getNodeAt(numberOfEntries); // will set currentNode at end of chain
        for (T item : items) { // Cannot 'transform' this for loop to a simpler while loop
            Node newNode = new Node(item);
            if (isEmpty()) {
                firstNode = newNode;
            } else {
                currentNode.setNextNode(newNode);
            }
            numberOfEntries++;
            currentNode = newNode;
        }
    }

    public T remove(int givenPosition) {
        T result = null; // Return value
        if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
            // Assertion: !isEmpty()
            if (givenPosition == 1) // Case 1: Remove first entry
            {
                result = firstNode.getData(); // Save entry to be removed
                firstNode = firstNode.getNextNode(); // Remove entry
            } else // Case 2: Not first entry
            {
                Node nodeBefore = getNodeAt(givenPosition - 1);
                Node nodeToRemove = nodeBefore.getNextNode();
                result = nodeToRemove.getData(); // Save entry to be removed
                Node nodeAfter = nodeToRemove.getNextNode();
                nodeBefore.setNextNode(nodeAfter); // Remove entry
            } // end if
            numberOfEntries--; // Update count
            return result; // Return removed entry
        } else
            throw new IndexOutOfBoundsException("Illegal position given to remove operation.");
    } // end remove

    public void removeAll(T item) {
        Node tempNode = new Node(item);
        tempNode.next = firstNode; // temp copy won't modify original value of firstNode

        Node currentNode = tempNode; // Unnecessary since currentNode and tempNode are both
        // Could've used tempNode throughout the while block
        // temporary "pointers" to traverse chain
        while (currentNode.next != null) {
            if (currentNode.next.data == item) {
                currentNode.next = currentNode.next.next;
                numberOfEntries -= 1;
            } else {
                currentNode = currentNode.next;
            }
        }
        firstNode = tempNode.next;
    }

    /*public T duplicateElement(T list) {
        if (!isEmpty()) {
            Node currentNode = firstNode;
            Node newNodeNextToCurrent;
            while (firstNode != null) {
                currentNode.next = currentNode.next.next;
                numberOfEntries++;
                currentNode.setNextNode(currentNode);
            }
        } else {
            throw new IndexOutOfBoundsException(")");
        }
    }*/

    public T replace(int givenPosition, T newEntry) {
        if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
            // Assertion: !isEmpty()
            Node desiredNode = getNodeAt(givenPosition);
            T originalEntry = desiredNode.getData();
            desiredNode.setData(newEntry);
            return originalEntry;
        } else
            throw new IndexOutOfBoundsException("Illegal position given to replace operation.");
    } // end replace

    public T getEntry(int givenPosition) {
        if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
            // Assertion: !isEmpty()
            return getNodeAt(givenPosition).getData();
        } else
            throw new IndexOutOfBoundsException("Illegal position given to getEntry operation.");
    } // end getEntry

    public T[] toArray() {
        // The cast is safe because the new array contains null entries
        @SuppressWarnings("unchecked")
        T[] result = (T[]) new Comparable[numberOfEntries];

        int index = 0;
        Node currentNode = firstNode;
        while ((index < numberOfEntries) && (currentNode != null)) {
            result[index] = currentNode.getData();
            currentNode = currentNode.getNextNode();
            index++;
        } // end while

        return result;
    } // end toArray

    public boolean contains(T anEntry) {
        boolean found = false;
        Node currentNode = firstNode;

        while (!found && (currentNode != null)) {
            if (anEntry.equals(currentNode.getData()))
                found = true;
            else
                currentNode = currentNode.getNextNode();
        } // end while

        return found;
    } // end contains

    public int getLength() {
        return numberOfEntries;
    } // end getLength

    public boolean isEmpty() {
        boolean result;

        if (numberOfEntries == 0) // Or getLength() == 0
        {
            // Assertion: firstNode == null
            result = true;
        } else {
            // Assertion: firstNode != null
            result = false;
        } // end if

        return result;
    } // end isEmpty

    public void insertAfterEvery(T listElement, T newElement) {
        Node currentNode = firstNode;
        int position = 1;

        while (numberOfEntries != 0 && currentNode != null) {
            if (this.contains(listElement)) {
                if (currentNode.data == listElement) {
                    this.add(position+1, newElement);
                }
                position++;
                currentNode = currentNode.next;
            }
        }
        numberOfEntries++;
    }

    // Initializes the class's data fields to indicate an empty list.
    private void initializeDataFields() {
        firstNode = null;
        numberOfEntries = 0;
    } // end initializeDataFields

    // Returns a reference to the node at a given position.
    // Precondition: The chain is not empty;
    // 1 <= givenPositon <= numberOfEntries.
    private Node getNodeAt(int givenPosition) {
        // Assertion: (firstNode != null) &&
        // (1 <= givenPosition) && (givenPosition <= numberOfEntries)
        Node currentNode = firstNode;

        // Traverse the chain to locate the desired node
        // (skipped if givenPosition is 1)
        for (int counter = 1; counter < givenPosition; counter++)
            currentNode = currentNode.getNextNode();
        // Assertion: currentNode != null
        return currentNode;
    } // end getNodeAt

    private class Node {
        private T data; // Entry in list
        private Node next; // Link to next node

        private Node(T dataPortion) {
            data = dataPortion;
            next = null;
        } // end constructor

        private Node(T dataPortion, Node nextNode) {
            data = dataPortion;
            next = nextNode;
        } // end constructor

        private T getData() {
            return data;
        } // end getData

        private void setData(T newData) {
            data = newData;
        } // end setData

        private Node getNextNode() {
            return next;
        } // end getNextNode

        private void setNextNode(Node nextNode) {
            next = nextNode;
        } // end setNextNode
    } // end Node
} // end LList