You are required, but not limited, to turn in the following source files:

Assignment10.java (This file does not need to be modified)

LinkedList.java (It needs to be modified)

ListIterator.java (This file does not need to be modified)

Requirements to get full credits in Documentation

The assignment number, your name, StudentID, Lecture number, and a class description need to be included at the top of each file/class.

A description of each method is also needed.

Some additional comments inside of long methods (such as a "main" method) to explain codes that are hard to follow should be written.

You can look at the Java programs in the text book to see how comments are added to programs.

New Skills to be Applied

In addition to what has been covered in previous assignments, the use of the following items, discussed in class, will probably be needed:

Linked Lists

Program Description

Class Diagram:

In the Assignment, you are given three files Assignment10.java, LinkedList.java, and ListIterator.java. You will need to add additional methods in the LinkedList class in the LinkedList.java file. The LinkedList will be tested using strings only.

Specifically, the following methods must be implemented in the LinkedList class:

(You should utilize listIterator() method already defined in the LinkedList class to obtain its LinkedListIterator object, and use the methods in the LinkedListIterator class to traverse from the first element to the last element of the linked list to define the following methods.)

1.

public String toString()

The toString method should concatenate strings in the linked list, and return a string of the following format:

{ Apple Banana Melon Orange }

Thus it starts with "{" and ends with "}", and there is a space between strings and "{" or "}". If the list is empty, it returns "{ }" with a space in between. Note that all elements in the linked list will be added in alphabetical order.

2.

public int size()

The size method returns the number of strings that the linked list contains at the time when this method is called.

3.

public void addElement(Object element, int index)

The addElement adds the parameter element at the parameter specified index. The element at the index and any elements at the later indices will be shifted towards the end of the list. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class.

4.

public String findSmallest( )

The findSmallest method should return the string that is smallest lexically among the strings stored in the linked list. It should return null (null pointer) if the linked list is empty.

5.

public void searchAndReplace(Object first, Object second)

The searchAndReplace method should search and replace all strings that match with the first parameter "first" with the second parameter "second". If the linked list does not contain a string that matches with the first parameter, then the linked list content should not change after calling this method.

6.

public void searchAndRemove(Object toBeRemoved)

The searchAndRemove method should search and remove all strings that match with the first parameter "toBeRemoved". If the linked list does not contain a string that matches with the first parameter, then the linked list content should not change after calling this method.

7.

public void reverseFirstSome(int howMany)

The reverseFirstSome method should reverse the number of strings located at the beginning, specified by the parameter integer. For instance, if the parameter "howMany" is 3, then the first 3 strings in the linked list should be reversed.

If the number "howMany" is 0 or less, then the linked list content will not change, and if it is same or more than the size of the linked list, then the entire linked list content will be reversed.

Test your LinkedList class with the given Assignment10.java file.

It is recommended to test boundary cases such as the cases when the linked list is empty, when it contains only one element, when adding/removing at the beginning or at the end of the linked list.

Input

The following files are the test cases that will be used as input for your program (Right-click and use "Save As"):

// Assignment #: 10

// Name: Your name

// StudentID: Your id

// Lab Lecture: Your lecture

// Description: The Assignment 10 class displays a menu of choices to a user

// and performs the chosen task. It will keep asking a user to

// enter the next choice until the choice of 'Q' (Quit) is

// entered.

import java.io.*;

public class Assignment10

{

public static void main(String[] args)

{

char input1;

String inputInfo = new String();

int operation2;

String line = new String();

//create a linked list to be used in this method.

LinkedList list1 = new LinkedList();

try

{

// print out the menu

printMenu();

// create a BufferedReader object to read input from a keyboard

InputStreamReader isr = new InputStreamReader (System.in);

BufferedReader stdin = new BufferedReader (isr);

do

{

System.out.print("What action would you like to perform? ");

line = stdin.readLine().trim(); //read a line

input1 = line.charAt(0);

input1 = Character.toUpperCase(input1);

if (line.length() == 1) //check if a user entered only one character

{

switch (input1)

{

case 'A': //Add String

System.out.print("Please enter a string to add: ");

String str1 = stdin.readLine().trim();

list1.addElement(str1);

break;

case 'G': //Get a String at a certain index

System.out.print("Please enter an index of a string to get: ");

inputInfo = stdin.readLine().trim();

int getIndex = Integer.parseInt(inputInfo);

try

{

String getString = (String) list1.getElement(getIndex);

System.out.print("The string at the index " + getIndex + " is "

+ getString + " ");

}

catch(IndexOutOfBoundsException ex)

{

System.out.print("The index is not valid ");

}

break;

case 'E': //Check if the linked list is empty

boolean empty = list1.isEmpty();

if (empty)

System.out.print("The linked list is empty ");

else

System.out.print("The linked list is not empty ");

break;

case 'I': //Get the last index of a given String

System.out.print("Please enter a string to search: ");

String str2 = stdin.readLine().trim();

int searchIndex = list1.indexOfLast(str2);

if (searchIndex != -1)

System.out.print("The index of the last " + str2 + " is " + searchIndex

+ " ");

else

System.out.print("The string " + str2

+ " does not exist in the linked list ");

break;

case 'L': //List Strings

System.out.print(list1.toString());

break;

case 'Q': //Quit

break;

case 'R': //Remove a String

System.out.print("Please enter an index of a string to remove: ");

inputInfo = stdin.readLine().trim();

int removeIndex = Integer.parseInt(inputInfo);

try

{

String removeString = (String) list1.removeElement(removeIndex);

System.out.print("The string at the index " + removeIndex + " was "

+ removeString + " and was removed ");

}

catch(IndexOutOfBoundsException ex)

{

System.out.print("The index is not valid ");

}

break;

case 'S': //Search and Replace

System.out.print("Please enter a string to replace: ");

String original = stdin.readLine().trim();

System.out.print("Please enter a string used to replace with: ");

String newStr = stdin.readLine().trim();

list1.searchAndReplace(original, newStr);

break;

case '?': //Display Menu

printMenu();

break;

default:

System.out.print("Unknown action ");

break;

}

}

else

{

System.out.print("Unknown action ");

}

} while (input1 != 'Q' || line.length() != 1);

}

catch (IOException exception)

{

System.out.print("IO Exception ");

}

}

/** The method printMenu displays the menu to a user **/

public static void printMenu()

{

System.out.print("Choice\t\tAction " +

"------\t\t------ " +

"A\t\tAdd String " +

"G\t\tGet String " +

"E\t\tCheck if Empty " +

"I\t\tIndex of Last String " +

"L\t\tList Strings " +

"Q\t\tQuit " +

"R\t\tRemove String " +

"S\t\tSearch and Replace " +

"?\t\tDisplay Help ");

} //end of printMenu()

}

// A linked list is a sequence of nodes with efficient

// element insertion and removal.

// This class contains a subset of the methods of the

// standard java.util.LinkedList class.

import java.util.NoSuchElementException;

public class LinkedList

{

/ested class to represent a node

private class Node

{

public Object data;

public Node next;

}

//only instance variable that points to the first node.

private Node first;

// Constructs an empty linked list.

public LinkedList()

{

first = null;

}

// Returns the first element in the linked list.

public Object getFirst()

{

if (first == null)

{

NoSuchElementException ex

= new NoSuchElementException();

throw ex;

}

else

return first.data;

}

// Removes the first element in the linked list.

public Object removeFirst()

{

if (first == null)

{

NoSuchElementException ex = new NoSuchElementException();

throw ex;

}

else

{

Object element = first.data;

first = first.next; //change the reference since it's removed.

return element;

}

}

// Adds an element to the front of the linked list.

public void addFirst(Object element)

{

//create a new node

Node newNode = new Node();

newNode.data = element;

newNode.next = first;

//change the first reference to the new node.

first = newNode;

}

// Returns an iterator for iterating through this list.

public ListIterator listIterator()

{

return new LinkedListIterator();

}

/*********************************************************

Add your methods here

*********************************************************/

/ested class to define its iterator

private class LinkedListIterator implements ListIterator

{

private Node position; //current position

private Node previous; //it is used for remove() method

// Constructs an iterator that points to the front

// of the linked list.

public LinkedListIterator()

{

position = null;

previous = null;

}

// Tests if there is an element after the iterator position.

public boolean hasNext()

{

if (position == null) /ot traversed yet

{

if (first != null)

return true;

else

return false;

}

else

{

if (position.next != null)

return true;

else

return false;

}

}

// Moves the iterator past the next element, and returns

// the traversed element's data.

public Object next()

{

if (!hasNext())

{

NoSuchElementException ex = new NoSuchElementException();

throw ex;

}

else

{

previous = position; // Remember for remove

if (position == null)

position = first;

else

position = position.next;

return position.data;

}

}

// Adds an element after the iterator position

// and moves the iterator past the inserted element.

public void add(Object element)

{

if (position == null) /ever traversed yet

{

addFirst(element);

position = first;

}

else

{

//making a new node to add

Node newNode = new Node();

newNode.data = element;

newNode.next = position.next;

//change the link to insert the new node

position.next = newNode;

//move the position forward to the new node

position = newNode;

}

//this means that we cannot call remove() right after add()

previous = position;

}

// Removes the last traversed element. This method may

// only be called after a call to the next() method.

public void remove()

{

if (previous == position) /ot after next() is called

{

IllegalStateException ex = new IllegalStateException();

throw ex;

}

else

{

if (position == first)

{

removeFirst();

}

else

{

previous.next = position.next; //removing

}

//stepping back

//this also means that remove() cannot be called twice in a row.

position = previous;

}

}

// Sets the last traversed element to a different value.

public void set(Object element)

{

if (position == null)

{

NoSuchElementException ex = new NoSuchElementException();

throw ex;

}

else

position.data = element;

}

} //end of LinkedListIterator class

} //end of LinkedList class

// The ListIterator interface allows access of a position in a linked list.

// This interface contains a subset of the methods of the

// standard java.util.ListIterator interface. The methods for

// backward traversal are not included.

public interface ListIterator

{

//Move Moves the iterator past the next element.

Object next();

// Tests if there is an element after the iterator position.

boolean hasNext();

// Adds an element before the iterator position

// and moves the iterator past the inserted element.

void add(Object element);

// Removes the last traversed element. This method may

// only be called after a call to the next() method.

void remove();

// Sets the last traversed element to a different value.

void set(Object element);

}

Test Case #1 INPUT:

A Grape 0 L A Melon 0 L C A Apple 2 L A Peach 0 L A Banana 1 L C D L A Potato -1 L A Kiwi 5 L A Avocado 10 L A Lemon 0 L Q

Test Case #1 OUTPUT:

Choice Action ------ ------ A Add String C Count its Size D Find Smallest L List Strings Q Quit R Replace Strings S Remove Strings T Reverse Strings from Beginning ? Display Help What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Grape } What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Melon Grape } What action would you like to perform? The size of the linked list is 2 What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Melon Grape Apple } What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Peach Melon Grape Apple } What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Peach Banana Melon Grape Apple } What action would you like to perform? The size of the linked list is 5 What action would you like to perform? The smallest string is Apple What action would you like to perform? { Peach Banana Melon Grape Apple } What action would you like to perform? Please enter a string to add: Please enter its index: The index is out of bounds What action would you like to perform? { Peach Banana Melon Grape Apple } What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Peach Banana Melon Grape Apple Kiwi } What action would you like to perform? Please enter a string to add: Please enter its index: The index is out of bounds What action would you like to perform? { Peach Banana Melon Grape Apple Kiwi } What action would you like to perform? Please enter a string to add: Please enter its index: What action would you like to perform? { Lemon Peach Banana Melon Grape Apple Kiwi } What action would you like to perform?

Assignment 10 +main(StringD: void. printMenuo:void LinkedList first Node +LinkedList tgetFirst(): Object tremove rst(): Object rtaddFirst(Object):void +listlteratoro: ListIterator +toString String nt addElement(Object, int) void ndSmallesto:String searchAndReplace (Object,Object): void tsearchAndRemove(Object):void reversedFirstSome(int):void You will need to implement only the methods in red. LinkedListlterator position: Node -previous: Node +LinkedList Iterator +hasNext():boolean tnext0 Object +add(Object):void +remove(): void +set (Object):void Node data: Object +next:Node ListIterator +hasNext(): boolean tnexto:Object +add(Object): void +remove 0: void +set(Object) void Assignment 10 +main(StringD: void. printMenuo:void LinkedList first Node +LinkedList tgetFirst(): Object tremove rst(): Object rtaddFirst(Object):void +listlteratoro: ListIterator +toString String nt addElement(Object, int) void ndSmallesto:String searchAndReplace (Object,Object): void tsearchAndRemove(Object):void reversedFirstSome(int):void You will need to implement only the methods in red. LinkedListlterator position: Node -previous: Node +LinkedList Iterator +hasNext():boolean tnext0 Object +add(Object):void +remove(): void +set (Object):void Node data: Object +next:Node ListIterator +hasNext(): boolean tnexto:Object +add(Object): void +remove 0: void +set(Object) void