You are required, but not limited, to turn in the following source files: Assign
ID: 3701466 • Letter: Y
Question
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 #10, 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)
The addElement adds the parameter element into the linked list. The linked list should contain all elements (strings) in alphabetical order. Therefore, in this addElement method, a correct location to insert the parameter element needs to be searched and the element needs to be inserted in that location.
4.
public void removeElementsAtOddIndices( )
The removeElementsAtOddIndices should remove objects at odd indices within the linked list. For instance, if the linked list contains { Apple Banana Melon Orange }, then after calling this method, the linked list will contains { Apple Melon } since Banana at the index 1 and Orange at the index 3 need to be removed. Each element within the linked list will can be labeled starting the index 0, and based on this assumption, elements should be removed. If the linked list does not contain any element, or contains only one element, then the method should not change its content.
5.
public void removeAdditionalOccurrences(Object element)
The removeAdditionalOccurrences method should search the parameter object (a string in this case) in the linked list, then it should keep the first occurrence of the element, but it should remove any other elements that is same as the parameter object within the linked list if any. For instance, if the linked list contains { Apple Banana Banana Banana Melon Melon Orange }, then after calling removeAdditionalOccurrences(Banana), the linked list will become { Apple Banana Melon Melon Orange }.
6.
public Object searchByIndex(int index)
The searchByIndex method should look for an object of the given parameter index and return it. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class.
7.
public void searchAndIncrease(Object element, int howMany)
The searchAndIncrease method should search the parameter object (a string), and if it is found, add the same object (a string) as many as the integer specified by the parameter howMany. For instance, if the linked list contains { Apple Banana Melon Orange }, and searchAndIncrease(Melon, 3) is called, then the linked list will contain { Apple Banana Melon Melon Melon Melon Orange } by adding Melon three times right after the found Melon. If the parameter element is not found in the linked list, or the value of howMany is 0 or less, then it should not change the content of the linked list.
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.
Files provided (No modification needed):
Assignment10.java:
ListIterator.java:
File provided that NEEDS modification:
LinkedList.java
Explanation / Answer
Assignment10.java
// Assignment #: 10
// Name:
// StudentID:
// 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 'C': //Count the size of the linked list
int size = list1.size();
System.out.print("The size of the linked list is " + size + " ");
break;
case 'L': //List Strings
System.out.print(list1.toString());
break;
case 'P': //RemoveElementsAtOddIndices
list1.removeElementsAtOddIndices();
System.out.print("Elements at odd indices removed ");
break;
case 'Q': //Quit
break;
case 'R': //RemoveAdditionalOccurrences
System.out.print("Please enter a string to remove its duplicates: ");
String remove = stdin.readLine().trim();
list1.removeAdditionalOccurrences(remove);
break;
case 'S': //Search By Index
System.out.print("Please enter an index to search: ");
int index2 = Integer.parseInt(stdin.readLine().trim());
try
{
String found = (String) list1.searchByIndex(index2);
System.out.print("The string at the index " + index2
+ " is "+ found + " ");
}
catch(IndexOutOfBoundsException ex)
{
System.out.print("The index is out of bounds ");
System.out.print("There is no string at the index ");
}
break;
case 'T': //Search and Increase
System.out.print("Please enter a string to search: ");
String str2 = stdin.readLine().trim();
System.out.print("Please enter a number to increase: ");
inputInfo = stdin.readLine().trim();
int howMany = Integer.parseInt(inputInfo);
list1.searchAndIncrease(str2, howMany);
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 Action " +
"------ ------ " +
"A Add String " +
"C Count Its Size " +
"L List Strings " +
"P Remove Elements At Odd Indices " +
"Q Quit " +
"R Remove Additional Occurrences " +
"S Search By Index " +
"T Search And Increase " +
"? Display Help ");
} //end of printMenu()
}
ListIterator.java
// 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);
}
LinkedList.java
// 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
{
//nested 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();
}
/*********************************************************
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.
*********************************************************/
public String toString()
{
String toStringop = "{"
ListIterator iter = listIterator();
while(iter.hasNext())
{
toStringop = toStringop +" "+ (iter.next).toString();
}
toStringop = toStringop + " }";
return toStringop;
}
/*********************************************************
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.
*********************************************************/
public int size()
{
int size = 0;
ListIterator iter = listIterator();
while(iter.hasNext())
{
size++;
}
return size;
}
/*****************************************
3.
public void addElement(Object element)
The addElement adds the parameter element into the linked list. The linked list should contain all elements (strings) in alphabetical order. Therefore, in this addElement method, a correct location to insert the parameter element needs to be searched and the element needs to be inserted in that location.
*************************************/
public void addElement(Object element)
{
ListIterator iter = listIterator();
while(iter.hasNext())
{
if((element.toString()).compareTo((iter.next).toString())<0)
{
iter.add(element);
return;
}
}
iter.add(element);
return;
}
/*********************************************************
4.
public void removeElementsAtOddIndices( )
The removeElementsAtOddIndices should remove objects at odd indices within the linked list. For instance, if the linked list contains { Apple Banana Melon Orange }, then after calling this method, the linked list will contains { Apple Melon } since Banana at the index 1 and Orange at the index 3 need to be removed. Each element within the linked list will can be labeled starting the index 0, and based on this assumption, elements should be removed. If the linked list does not contain any element, or contains only one element, then the method should not change its content.
*********************************************************/
public void removeElementsAtOddIndices()
{
ListIterator iter = listIterator();
while(iter.hasNext())
{
iter.next()
if(iter.hasNext())
{
iter.next();
iter.remove();
}
}
return;
}
/*********************************************************
5.
public void removeAdditionalOccurrences(Object element)
The removeAdditionalOccurrences method should search the parameter object (a string in this case) in the linked list, then it should keep the first occurrence of the element, but it should remove any other elements that is same as the parameter object within the linked list if any. For instance, if the linked list contains { Apple Banana Banana Banana Melon Melon Orange }, then after calling removeAdditionalOccurrences(Banana), the linked list will become { Apple Banana Melon Melon Orange }.
*********************************************************/
public void removeAdditionalOccurrences(Object element)
{
ListIterator iter = listIterator();
while(iter.hasNext())
{
if((element.toString()).compareTo((iter.next).toString())==0)
{
while(iter.hasNext())
{
if((element.toString()).compareTo((iter.next).toString())==0)
{
iter.remove();
}
}
return;
}
}
return;
}
/*********************************************************
6.
public Object searchByIndex(int index)
The searchByIndex method should look for an object of the given parameter index and return it. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class.
*********************************************************/
public Object searchByIndex(int index) throws IndexOutOfBoundsException()
{
if(index<0||index>=size())
{
throw new IndexOutOfBoundsException(index);
}
ListIterator iter = listIterator();
for(int i=0;i<index;i++)
{
iter.next();
}
return iter.next();
}
/*********************************************************
7.
public void searchAndIncrease(Object element, int howMany)
The searchAndIncrease method should search the parameter object (a string), and if it is found, add the same object (a string) as many as the integer specified by the parameter howMany. For instance, if the linked list contains { Apple Banana Melon Orange }, and searchAndIncrease(Melon, 3) is called, then the linked list will contain { Apple Banana Melon Melon Melon Melon Orange } by adding Melon three times right after the found Melon. If the parameter element is not found in the linked list, or the value of howMany is 0 or less, then it should not change the content of the linked list.
*********************************************************/
public void searchAndIncrease(Object element, int howMany)
{
ListIterator iter = listIterator();
while(iter.hasNext())
{
if((element.toString()).compareTo((iter.next).toString())==0)
{
for(int i=0;i<howMany;i++)
{
iter.add(element);
}
}
}
return;
}
//nested 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) //not 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) //never 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) //not 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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.