Problem 1

Start with the file AList.java and add the following methods:

1. Add the method public int getLastIndex(T item) which returns the index of the last entry which is equal to item. If item is not found, it returns -1. (15 points)

2. Add the method public int removeEvery(T item) that removes all occurrences of item and returns the number of removed items. (15 points)

3. Add the method public boolean equals(Object other) that returns true when the contents of 2 AList objects are the same. Note that 2 AList objects are the same if they have the same number of items and each item in one object is equal to the item in its corresponding location in the other object (15 points)

Problem 2

Start with the file LList2.java and add the following methods:

4. Add the method int getLastIndex(T item) that returns the index of the last entry which is equal to item. If item is not found, it returns -1. (15 points)

5. Add the method int removeEvery(T item) that removes all occurrences of item and returns the number of removed items. (15 points)

6. Add the methodboolean equals(Object other) method that returns true when the contents of 2 LList2 objects are the same (the two objects in this case are the current object and other). Note that 2 LList2 objects are the same if they have the same number of items and each item in one object exists in the same location in the other object (15 points)

7. Provide a second implementation of the method boolean contains2(T anEntry)that calls a private recursive method private boolean contains(T anEntry, Node startNode) that returns whether the list that starts at startNode contains the entry anEntry. (10 points)

ListInterface.Java

/** An interface for the ADT list. Entries in the list have positions that begin with 1. @author Frank M. Carrano @version 3.0*/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 @return true if the addition is successful, or false if newPosition < 1, or newPosition > getLength() + 1 */ public boolean 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 or null, if either the list was empty, givenPosition < 1, or givenPosition > getLength() */ 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 true if the replacement occurs, or false if either the list is empty, givenPosition < 1, or givenPosition > getLength() */ public boolean 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 or null, if either the list is empty, givenPosition < 1, or givenPosition > getLength() */ 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. */ public T[] toArray(); } // end ListInterface

AList.java

import java.util.Arrays;/** A class that implements the ADT list by using an array. The list is never full. @author Frank M. Carrano*/public class AList implements ListInterface { private T[] list; // array of list entries private int numberOfEntries; private static final int DEFAULT_INITIAL_CAPACITY = 25; public AList() {this(DEFAULT_INITIAL_CAPACITY); // call next constructor } // end default constructor public AList(int initialCapacity) {numberOfEntries = 0;// the cast is safe because the new array contains null entries@SuppressWarnings("unchecked") T[] tempList = (T[])new Object[initialCapacity];list = tempList; } // end constructor public void add(T newEntry) { ensureCapacity();list[numberOfEntries] = newEntry;numberOfEntries++; } // end add public boolean add(int newPosition, T newEntry) { boolean isSuccessful = true;if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) { ensureCapacity(); makeRoom(newPosition); list[newPosition - 1] = newEntry; numberOfEntries++;}else isSuccessful = false;return isSuccessful; } // end add public T remove(int givenPosition) { T result = null; // return valueif ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); result = list[givenPosition - 1]; // get entry to be removed // move subsequent entries towards entry to be removed, // unless it is last in list if (givenPosition < numberOfEntries)removeGap(givenPosition); numberOfEntries--;

} // end ifreturn result; // return reference to removed entry, or// null if either list is empty or givenPosition// is invalid } // end remove public void clear() { numberOfEntries = 0; } // end clear public boolean replace(int givenPosition, T newEntry) { boolean isSuccessful = true;if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { // test catches empty list assert !isEmpty(); list[givenPosition - 1] = newEntry;}else isSuccessful = false;return isSuccessful; } // end replace public T getEntry(int givenPosition) { T result = null; // result to returnif ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); result = list[givenPosition - 1];} // end ifreturn result; } // end getEntry public boolean contains(T anEntry) { boolean found = false;for (int index = 0; !found && (index < numberOfEntries); index++) { if (anEntry.equals(list[index]))found = true;} // end forreturn found; } // end contains public int getLength() {return numberOfEntries; } // end getLength public boolean isEmpty() {return numberOfEntries == 0; // or getLength() == 0 } // end isEmpty public T[] toArray() {// 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];} // end forreturn result; } // end toArray // Doubles the size of the array list if it is full. private void ensureCapacity() {if (numberOfEntries == list.length) list = Arrays.copyOf(list, 2 * list.length); } // end ensureCapacity private void makeRoom(int newPosition) {assert (newPosition >= 1) && (newPosition <= numberOfEntries + 1);int newIndex = newPosition - 1;int lastIndex = numberOfEntries - 1;// move each entry to next higher index, starting at end of// list and continuing until the entry at newIndex is movedfor (int index = lastIndex; index >= newIndex; index--) list[index + 1] = list[index]; } // end makeRoom private void removeGap(int givenPosition) {assert (givenPosition >= 1) && (givenPosition < numberOfEntries);int removedIndex = givenPosition - 1;int lastIndex = numberOfEntries - 1;for (int index = removedIndex; index < lastIndex; index++) list[index] = list[index + 1]; } // end removeGap# public int getLastIndex(T item) { } public boolean equals(Object other) { } public int removeEvery(T item) { }} // end AList

LList2.java

/** A class that implements the ADT list by using a chain of nodes. The chain has both a head reference and a tail reference. @author Frank M. Carrano @version 3.0*/public class LList2 implements ListInterface{private Node firstNode; // head reference to first nodeprivate Node lastNode; // tail reference to last nodeprivate int numberOfEntries;public LList2(){clear();} // end default constructorpublic final void clear() // NOTICE clear is not final in interface and that is OK{firstNode = null;lastNode = null;numberOfEntries = 0;} // end clearpublic void add(T newEntry) // OutOfMemoryError possible{Node newNode = new Node(newEntry); // create new nodeif (isEmpty())firstNode = newNode;elselastNode.setNextNode(newNode);lastNode = newNode;numberOfEntries++;} // end add public boolean add(int newPosition, T newEntry) // OutOfMemoryError possible{ boolean isSuccessful = true; if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) { Node newNode = new Node(newEntry); if (isEmpty()) { firstNode = newNode; lastNode = newNode; } else if (newPosition == 1) { newNode.setNextNode(firstNode); firstNode = newNode; } else if (newPosition == numberOfEntries + 1) { lastNode.setNextNode(newNode);

lastNode = newNode; } else { Node nodeBefore = getNodeAt(newPosition - 1); Node nodeAfter = nodeBefore.getNextNode(); newNode.setNextNode(nodeAfter); nodeBefore.setNextNode(newNode); } // end if numberOfEntries++; } else isSuccessful = false; return isSuccessful;} // end addpublic T remove(int givenPosition){ T result = null; // return 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(); if (numberOfEntries == 1) lastNode = null; // solitary entry was removed } else // case 2: givenPosition > 1 { Node nodeBefore = getNodeAt(givenPosition - 1); Node nodeToRemove = nodeBefore.getNextNode(); Node nodeAfter = nodeToRemove.getNextNode(); nodeBefore.setNextNode(nodeAfter); // disconnect the node to be removed result = nodeToRemove.getData(); // save entry to be removed if (givenPosition == numberOfEntries) lastNode = nodeBefore; // last node was removed } // end if numberOfEntries--; } // end if return result; // return removed entry, or // null if operation fails} // end removepublic boolean replace(int givenPosition, T newEntry){boolean isSuccessful = true; if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty();

Node desiredNode = getNodeAt(givenPosition);desiredNode.setData(newEntry); } elseisSuccessful = false;return isSuccessful; } // end replace public T getEntry(int givenPosition) { T result = null; // result to returnif ((givenPosition >= 1) && (givenPosition <= numberOfEntries)){assert !isEmpty(); result = getNodeAt(givenPosition).getData();} // end if return result; } // end getEntrypublic boolean contains(T anEntry){boolean found = false;Node currentNode = firstNode;while (!found && (currentNode != null)){if (anEntry.equals(currentNode.getData()))found = true;elsecurrentNode = currentNode.getNextNode();} // end whilereturn found;} // end contains public int getLength() { return numberOfEntries; } // end getLength public boolean isEmpty() {boolean result;if (numberOfEntries == 0) // or getLength() == 0{assert firstNode == null;result = true;}else{assert firstNode != null;result = false;} // end ifreturn 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]; // warning: [unchecked] unchecked cast 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// Returns a reference to the node at a given position.// Precondition: List is not empty; 1 <= givenPosition <= numberOfEntries.private Node getNodeAt(int givenPosition){assert (firstNode != null) && (1 <= givenPosition) && (givenPosition <=numberOfEntries);Node currentNode = firstNode; if (givenPosition == numberOfEntries) currentNode = lastNode; else if (givenPosition > 1) // traverse the chain to locate the desired node{ for (int counter = 1; counter < givenPosition; counter++) currentNode = currentNode.getNextNode();} // end ifassert currentNode != null;return currentNode;} // end getNodeAt// Lab 3// Problem 1public int getIndex(T item) {return 0;}// Problem 2public int removeEvery(T item) {return 0;}// Problem 3public boolean equals(Object other) {return false;}

//Problem 4public boolean contains2(T anEntry) {return false;}private boolean contains(T anEntry, Node startNode) {return false;}private class Node {private T data; // data portionprivate Node next; // next to next nodeprivate Node(T dataPortion)// PRIVATE or PUBLIC is OK{data = dataPortion;next = null;} // end constructorprivate Node(T dataPortion, Node nextNode)// PRIVATE or PUBLIC is OK{data = dataPortion;next = nextNode;} // end constructorprivate T getData(){return data;} // end getDataprivate void setData(T newData){data = newData;} // end setDataprivate Node getNextNode(){return next;} // end getNextNodeprivate void setNextNode(Node nextNode){next = nextNode;} // end setNextNode} // end Node} // end LList2

ListClient.java

public class ListClient {public static void main(String[] args) {testList();} // end mainpublic static void testList() { ListInterface runnerList = new AList();// runnerList has only methods in ListInterface runnerList.add("16"); // winner runnerList.add("4"); // second place runnerList.add("33"); // third place runnerList.add("27"); // fourth place displayList(runnerList); } // end testList public static void displayList(ListInterface list) { int numberOfEntries = list.getLength(); System.out.println("The list contains " + numberOfEntries + " entries, as follows:"); for (int position = 1; position <= numberOfEntries; position++) System.out.println(list.getEntry(position) + " is entry " + position); System.out.println(); } // end displayList} // end ListClient/**/