Please Help me complete the reverse() and cycle() method in both AList.java and LList.java

AList.java

import java.util.Arrays;

class AList implements ListInterface {

private T[] list; //Array of list entries; ignore list[0] private int numberOfEntries; // current number of entries in list private boolean initialized = false; private static final int DEFAULT_CAPACITY = 25; private static final int MAX_CAPACITY = 10000;

public AList() { this(DEFAULT_CAPACITY); // Call next constructor } // end default constructor

public AList(int initialCapacity) { // Is initialCapacity too small? if (initialCapacity < DEFAULT_CAPACITY) initialCapacity = DEFAULT_CAPACITY; else // Is initialCapacity too big? checkCapacity(initialCapacity); // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] tempList = (T[]) new Object[initialCapacity + 1]; list = tempList; numberOfEntries = 0; initialized = true; } // end constructor

/** Throws an exception if this object is not initialized. * */ private void checkInitialization(){ if (!initialized) throw new SecurityException("ArrayBag object is not initialized " + "properly."); } // end checkInitialization

/** Throws an exception if the desired capacity exceeds the maximum. * */ private void checkCapacity(int desiredCapacity){ if(desiredCapacity > MAX_CAPACITY) throw new IllegalStateException("Attempt to create a bag " + "whose capacity exceeds " + "allowed maximum."); } // end checkCapacity public void add(T newEntry) { checkInitialization(); list[numberOfEntries+1] = newEntry; numberOfEntries++; ensureCapacity(); } // end add

// Precondition: The array list has room for another entry public void add(int newPosition, T newEntry) { checkInitialization();

if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) { if (newPosition <= numberOfEntries) { makeRoom(newPosition); }

list[newPosition] = newEntry; numberOfEntries++; ensureCapacity(); // Ensure enough room for next add } else { throw new IndexOutOfBoundsException("Illegal position given to add operation."); } } // end add

public T remove(int givenPosition) { checkInitialization(); if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); T result = list[givenPosition ]; // Get entry to be removed // Move subsequent entries toward entry to be removed, // unless it is last in list if (givenPosition < numberOfEntries) { removeGap(givenPosition); } numberOfEntries--; return result; // Return reference to removed entry } else throw new IndexOutOfBoundsException("Illegal position given to remove operation.");

} // end remove

public void clear() { numberOfEntries = 0; } // end clear

public T replace(int givenPosition, T newEntry) { checkInitialization();

if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); T originalEntry = list[givenPosition]; list[givenPosition] = newEntry; return originalEntry; } else throw new IndexOutOfBoundsException("Illegal position give to replace operation."); } // end replace

public T getEntry(int givenPosition) { checkInitialization(); if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); return list[givenPosition]; } else throw new IndexOutOfBoundsException("Illegal position given to getEntry operation."); } // end getEntry

public boolean contains(T anEntry) { checkInitialization(); boolean found = false; int index = 1;

while (!found && (index <= numberOfEntries)) { if (anEntry.equals(list[index])) { found = true; } index++; } // end for

return found; } // end contains

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

public boolean isEmpty() { return numberOfEntries == 0; } // end isEmpty

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

for (int index = 0; index < numberOfEntries; index++) { result[index] = list[index+1]; } // end for

return result; } // end toArray

// Doubles the size of the array list if it is full. private void ensureCapacity() { int capacity = list.length - 1; if (numberOfEntries >= capacity) { int newCapacity = 2 * capacity; checkCapacity(newCapacity); // Is capacity too big? list = Arrays.copyOf(list, newCapacity + 1); } } // end ensureCapacity

/** Makes room for a new entry at newPosition. * Precondition: 1 <= newPosition <= numberOfEntries+1; * numberOfEntries is list's length before addition. * checkInitialization has been called. */ private void makeRoom(int newPosition) { assert (newPosition >= 1) && (newPosition <= numberOfEntries + 1); int newIndex = newPosition; int lastIndex = numberOfEntries; // Move each entry to next higher index, starting at end of // array and continuing until the entry at newIndex is moved for (int index = lastIndex; index >= newIndex; index--) { list[index + 1] = list[index]; } } // end makeRoom

/** Shifts entries that are beyond the entry to be removed * to the next lower position. * Precondition: 1 <= givenPosition < numberOfEntries; * numberOfEntries is list's length before removal. * checkInitialization has been called. */ private void removeGap(int givenPosition) { assert (givenPosition >= 1) && (givenPosition < numberOfEntries);

int removedIndex = givenPosition; int lastIndex = numberOfEntries; for (int index = removedIndex; index < lastIndex; index++) list[index] = list[index + 1]; } // end removeGap

/** Build a string representation of the list * * @return A string showing the state of the list. */ public String toString() { String result = "{ "; for (int i = 0; i < numberOfEntries; i++) { result = result + "<" + list[i+1] + "> "; } result = result + "}";

return result; }

/** Display the list with indices one to a line * */ public void display() { for (int index = 1; index <= numberOfEntries; index++) { System.out.println(index + ":" + list[index]); } } // end display

/** Check to see if two lists are the same. * @param aList Another array list to check this list against. * @return True if all the items in this list and the other list are equals. */

public boolean equals(AList aList) { boolean result = false; // result of comparison of lists

int position; // want position available throughout method

// If the lists have unequal lengths just use the default value of result. if (numberOfEntries == (aList.getLength())) { boolean allMatch = true; position = 1; // Scan the equal length lists looking for a non equal pair of items. while((position <= numberOfEntries) && allMatch){ // If we find a mismatch allMatch becomes false and we will escape the while allMatch = list[position].equals(aList.list[position]); position++; } // end while result = allMatch; }

return result; } // end equals /********************************************************************* * * METHODS TO BE COMPLETED * ***********************************************************************/ /** Reverse the order of items in a list. */ public void reverse() { // COMPLETE THIS METHOD } /** Cycle the first item to the end of the list. */ public void cycle() { // COMPLETE THIS METHOD }

}

LList.java

import java.io.*;

class LList implements ListInterface {

private Node firstNode; // Reference to first node of chain private int numberOfEntries;

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

public void clear() { initializeDataFields();

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

public void add(T newEntry) { 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 newPosition, T newEntry) { if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) { Node newNode = new Node(newEntry); if (newPosition == 1) // Case 1 { newNode.setNextNode(firstNode); firstNode = newNode; } else // Case 2: List is not empty { // and newPosition > 1 Node nodeBefore = getNodeAt(newPosition - 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 T remove(int givenPosition) { T result = null; // Teturn value if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !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; } else throw new IndexOutOfBoundsException("Illegal position given to remove operation.");

} // end remove

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 T getEntry(int givenPosition) { if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); return getNodeAt(givenPosition).getData(); } else throw new IndexOutOfBoundsException("Illegal position given to getEntry operation."); } // end getEntry

public T replace(int givenPosition, T newEntry) { if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !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 int getLength() { return numberOfEntries; }

public boolean isEmpty() { boolean result; if (numberOfEntries == 0) // Or getLength() == 0 { assert firstNode == null; result = true; } else { assert firstNode != null; result = false; } // end if return result; } // end isEmpty

public T[] toArray() { // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] result = (T[]) new Object[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

// Return a reference to the node at a given position. // Precondition: List is not empty; // 1 <= givenPostion <= numberOfEntries private Node getNodeAt(int givenPosition) { assert (firstNode != null) && (1 <= givenPosition) && (givenPosition <= numberOfEntries); Node currentNode = firstNode; // Traverse the chain to locate the desired node for (int counter = 1; counter < givenPosition; counter++) { currentNode = currentNode.getNextNode(); } assert currentNode != null; return currentNode; } // end getNodeAt

private class Node {

private T data; // entry in bag private Node next; // link to next node

private Node(T dataPortion) { this(dataPortion, 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

/** Build a string representation of the list. * * @return A string showing the state of the list. */ public String toString() { String result = "{ "; Node currentNode = firstNode; while (currentNode != null) {

result = result + "<" + currentNode.data + "> "; currentNode = currentNode.next;

} result = result + "}";

return result; }

/** Display the list with indices one to a line * This will correctly display an infinite list, * whereas the toString() method will never return. * */ public void display() { int index = 1; Node currentNode = firstNode;

while (currentNode != null) { System.out.println(index + ":" + currentNode.getData());

currentNode = currentNode.getNextNode(); index++; }

} // end display

/** Check to see if two lists are the same. * @param aList Another linked list to check this list against. * @return True if all the items in this list and the other list are equals. */ public boolean equals(LList aList) { boolean isEqual = false; // result of comparison of lists

Node currOne = firstNode; Node currTwo = aList.firstNode; int counter;

if (numberOfEntries == aList.numberOfEntries) { // Lists have equal lengths, so traverse both and compare items as you go: // (NOTE: loop is skipped if lists are empty)

while ((currOne != null) && (currOne.getData()).equals(currTwo.getData())) { currOne = currOne.getNextNode(); currTwo = currTwo.getNextNode(); } // end while

// If we made it to the end, the lists are equal isEqual = (currOne == null); }

return isEqual; } // end equals

/********************************************************************* * * METHODS TO BE COMPLETED * ***********************************************************************/

/** Reverse the order of items in a list. */ public void reverse() {

// CODE TO BE COMPLETED

}

/** Cycle the first item to the end of the list. */ public void cycle() {

// CODE TO BE COMPLETED

} }

ListInterface.java

public interface ListInterface { /** Adds a new entry to the end of this list. Entries currently in the list are unaffected. The list's size is increased by 1. * @param newEntry The object to be added as a new entry. */ public void add(T newEntry);

/** Adds a new entry at a specified position within this list. * Entries originally at and above the specified position * are at the next higher position within the list. * The list's size is increased by 1. * @param newPosition An integer that specifies the desired * position of the new entry. * @param newEntry The object to be added as a new entry. * @throws IndexOutOfBoundsException if either * newPosition less than 1, or * newPosition greater than getLength()+1. */ public void add(int newPosition, T newEntry);

/** Removes the entry at a given position from this list. * Entries originally at positions higher than the given * position are at the next lower position within the list, * and the list's size is decreased by 1. * @param givenPosition An integer that indicates the position of * the entry to be removed. * @return A reference to the removed entry. * @throws IndexOutOfBoundsException if either * givenPosition less than 1, or * givenPosition greater than getLength()+1. */ public T remove(int givenPosition);

/** Removes all entries from this list. */ public void clear();

/** Replaces the entry at a given position in this list. * @param givenPosition An integer that indicates the position of the * entry to be replaced. * @param newEntry The object that will replace the entry at the * position givenPosition. * @return The original entry that was replaced. * @throws IndexOutOfBoundsException if either * givenPosition less than 1, or * givenPosition greater than getLength()+1. */ public T replace(int givenPosition, T newEntry);

/** Retrieves the entry at a given position in this list. * @param givenPosition An integer that indicates the position of * the desired entry. * @return A reference to the indicated entry. * @throws IndexOutOfBoundsException if either * givenPosition less than 1, or * givenPosition greater than getLength()+1. */ public T getEntry(int givenPosition);

/** Sees whether this list contains a given entry. * @param anEntry The object that is the desired entry. * @return True if the list contains anEntry, or false if not. */ public boolean contains(T anEntry);

/** Gets the length of this list. * @return The integer number of entries currently in the list. */ public int getLength();

/** Sees whether this list is empty. * @return True if the list is empty, or false if not. */ public boolean isEmpty();

/** Retrieves all entries that are in this list in the order in which they occur in the list. @return A newly allocated array of all the entries in the list. */ public T[] toArray(); } // end ListInterface