Specifically, the following methods must be implemented in the LinkedList class:
ID: 3686013 • Letter: S
Question
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 addElementAt(Object element, int index)
The addElementAt 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 void addFewAtEnd(Object element, int howMany)
The addFewAtEnd method adds the parameter element at the end of the linked list for the number of times specified by the parameter howMany. For instance, if the parameter integer is 3, then it should add the parameter Object three times at the end of the linked list. If the parameter integer is less than or equals to 0, nothing should be added to the linked list (so the linked list will be unchanged.)
5.
public void removeLastFew(int howMany)
The removeLastFew method removes the number of elements at the end of the linked list, which was specified by the parameter howMany. For instance, if the parameter integer is 3, then the last three elements of the linked list will be removed. If the parameter integer is 0 or less, then the linked list content will not be changed. If the parameter integer is same or more than the size of the linked list, then all elements will be removed and the linked list will be empty.
6.
public void removeAllOccurrences(Object stringToBeRemoved)
The removeAllOccurrences method removes all occurrences of the parameter string (object) in the list. If the parameter string does not exist in the linked list, then the linked list content will not change.
7.
public void reverseLastFew(int howMany)
The reverseLastFew method reverses the number of elements at the end of the linked list, which was specified by the parameter howMany. For instance, if the parameter integer is 3, then only the last three elements of the linked list will be reversed.
For instance, if the linked list contains { Apple Banana Melon Orange }, then after calling this method with the parameter 3, its content becomes { Apple Orange Melon Banana }. 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.
Files Provided by Instructor:
Assignment10 (does not need to be modified):
---------------------------------------------------------------------------------------------
LinkedList (Needs to be modified):
---------------------------------------------------------------------------------------------
ListIterator (Does not need to be modified):
Explanation / Answer
Answer:
Program code to copy:
Here is the program code with added required methods and they are highlighted in bold letters.
//LinkedList.java
import java.util.NoSuchElementException;
public class LinkedList
{
int size = 0;
// 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();
}
//The toString() method should concatenate strings in the linked list,
//and return a string of the format as {string1 string2 string3 ... ... ...}
public String toString()
{
String str = "";
if (size() == 0)
{
str = "{ } ";
}
else
{
str = "{ ";
StringBuilder sb = new StringBuilder();
ListIterator iterator = listIterator();
while (iterator.hasNext())
{
sb.append(String.valueOf(iterator.next())).append(" ");
}
sb.append("} ");
str = str.concat(sb.toString());
}
return str;
}
//size() method returns the number of strings that the linked list
//contains at the time when this method is called.
public int size()
{
int listsize = 0;
ListIterator iterator_list = listIterator();
while (iterator_list.hasNext())
{
iterator_list.next();
listsize++;
}
return listsize;
}
/*
* The addElementAt 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.
*/
public void addElementAt(Object element, int index)
{
try
{
LinkedListIterator iterator_list = new LinkedListIterator();
if (index == 0)
{
addFirst(element);
return;
}
else
{
if (index >= 0 || index < size)
{
for (int i = 0; i < index; i++)
{
iterator_list.next();
}
iterator_list.add(element);
size++;
}
else
{
IndexOutOfBoundsException ex = new IndexOutOfBoundsException();
throw ex;
}
}
}
catch (IndexOutOfBoundsException iobe)
{
System.out.print("Index out of bounds exception. ");
}
}
/* The addFewAtEnd method adds the parameter element at the end of the
* linked list for the number of times specified by the parameter
* 'howMany'
*/
public void addFewAtEnd(Object element, int howMany)
{
int i = 0;
int listSize = size();
while (i < howMany)
{
addElementAt(element, listSize);
listSize++;
i++;
}
}
/*
* The removeLastFew method removes the number of elements at the end
* of the linked list, which was specified by the parameter 'howMany'.
*/
public void removeLastFew(int howMany)
{
ListIterator listIterator = listIterator();
int listsize = size();
int i = 0;
if (howMany > 0)
{
if (howMany < listsize)
{
while (i < (listsize - howMany))
{
listIterator.next();
i++;
}
for (int r = 0; r < howMany; r++)
{
listIterator.next();
listIterator.remove();
}
}
else
{
while (i < listsize)
{
listIterator.next();
i++;
}
for (int r = 0; r < listsize; r++)
{
listIterator.remove();
}
}
}
}
// The removeAllOccurrences method removes all occurrences
// of the parameter string (object) in the list
public void removeAllOccurrences(Object stringToBeRemoved)
{
LinkedListIterator listiterator = new LinkedListIterator();
while (listiterator.hasNext())
{
if (listiterator.next().equals(stringToBeRemoved.toString()))
{
listiterator.remove();
}
}
}
/*
* The reverseLastFew method reverses the number of elements
* at the end of the linked list, which was specified by the
* parameter 'howMany'.
*/
public void reverseLastFew(int howMany)
{
ListIterator listiterator = this.listIterator();
int listsize = size();
int i = 0, count = 0;
LinkedList linkedList = new LinkedList();
if (howMany > 0)
{
if (howMany < listsize)
{
while (i < (listsize - howMany))
{
listiterator.next();
i++;
}
count = 0;
while (listiterator.hasNext())
{
String str = String.valueOf(listiterator.next());
linkedList.listIterator().add(str);
count++;
}
i = 0;
while (i < howMany)
{
removeLastFew(1);
i++;
}
i = 0;
while (i < howMany)
{
String str1 = String.valueOf(linkedList.getFirst());
this.addFewAtEnd(str1, 1);
linkedList.removeFirst();
i++;
}
}
else
{
count = 0;
while (listiterator.hasNext())
{
String str = String.valueOf(listiterator.next());
linkedList.listIterator().add(str);
System.out.println(str + "--");
count++;
}
i = 0;
while (i < listsize)
{
removeLastFew(1);
i++;
}
i = 0;
while (i < listsize)
{
String str1 = String.valueOf(linkedList.getFirst());
this.addFewAtEnd(str1, 1);
linkedList.removeFirst();
i++;
}
}
}
}
// 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 before 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
//ListIterator.java
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);
}
//Assignment10.java
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();
System.out.print("Please enter its index: ");
int index = Integer.parseInt(stdin.readLine().trim());
try
{
list1.addElementAt(str1, index);
}
catch(IndexOutOfBoundsException ex)
{
System.out.print("The index is out of bounds ");
}
break;
case 'B': //Add Strings at End
System.out.print("Please enter a string to add at the end: ");
String str2 = stdin.readLine().trim();
System.out.print("Please enter a number of times to add: ");
String times = stdin.readLine().trim();
int howMany = Integer.parseInt(times);
list1.addFewAtEnd(str2, howMany);
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 'Q': //Quit
break;
case 'R': //Remove Strings from end
System.out.print("Please enter a number of elements to remove from the end: ");
inputInfo = stdin.readLine().trim();
int howMany2 = Integer.parseInt(inputInfo);
list1.removeLastFew(howMany2);
break;
case 'S': //Remove String from List
System.out.print("Please enter a string to remove from the linked list: ");
inputInfo = stdin.readLine().trim();
list1.removeAllOccurrences(inputInfo);
break;
case 'T': //Reverse Strings from End
System.out.print("Please enter a number of elements to reverse from the end: ");
inputInfo = stdin.readLine().trim();
int howMany3 = Integer.parseInt(inputInfo);
list1.reverseLastFew(howMany3);
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 ");
}
}
public static void printMenu()
{
System.out.print("Choice Action " +
"------ ------ " +
"A Add String " +
"B Add Strings at End " +
"C Count its Size " +
"L List Strings " +
"Q Quit " +
"R Remove Strings from End " +
"S Remove String from List " +
"T Reverse Strings from End " +
"? Display Help ");
} //end of printMenu()
}
Sample Output:
Sample Output:
Choice Action
------ ------
A Add String
B Add Strings at End
C Count its Size
L List Strings
Q Quit
R Remove Strings from End
S Remove String from List
T Reverse Strings from End
? Display Help
What action would you like to perform?
A
Please enter a string to add:
AVOCADO
Please enter its index:
0
What action would you like to perform?
A
Please enter a string to add:
BILBERRY
Please enter its index:
1
What action would you like to perform?
KIWIFRUIT
Unknown action
What action would you like to perform?
A
Please enter a string to add:
KIWIFRUIT
Please enter its index:
2
What action would you like to perform?
A
Please enter a string to add:
LYCHEE
Please enter its index:
3
What action would you like to perform?
BILBERRY
Unknown action
What action would you like to perform?
A
Please enter a string to add:
BILBERRY
Please enter its index:
4
What action would you like to perform?
A
Please enter a string to add:
POMELO
Please enter its index:
3
What action would you like to perform?
L
{ AVOCADO BILBERRY KIWIFRUIT POMELO LYCHEE BILBERRY }
What action would you like to perform?
?
Choice Action
------ ------
A Add String
B Add Strings at End
C Count its Size
L List Strings
Q Quit
R Remove Strings from End
S Remove String from List
T Reverse Strings from End
? Display Help
What action would you like to perform?
B
Please enter a string to add at the end:
POMELO
Please enter a number of times to add:
1
What action would you like to perform?
L
{ AVOCADO BILBERRY KIWIFRUIT POMELO LYCHEE BILBERRY POMELO }
What action would you like to perform?
C
The size of the linked list is 7
What action would you like to perform?
T
Please enter a number of elements to reverse from the end:
4
What action would you like to perform?
L
{ AVOCADO BILBERRY KIWIFRUIT POMELO BILBERRY LYCHEE POMELO }
What action would you like to perform?
A
Please enter a string to add:
POMELO
Please enter its index:
1
What action would you like to perform?
L
{ AVOCADO POMELO BILBERRY KIWIFRUIT POMELO BILBERRY LYCHEE POMELO }
What action would you like to perform?
?
Choice Action
------ ------
A Add String
B Add Strings at End
C Count its Size
L List Strings
Q Quit
R Remove Strings from End
S Remove String from List
T Reverse Strings from End
? Display Help
What action would you like to perform?
R
Please enter a number of elements to remove from the end:
2
What action would you like to perform?
L
{ AVOCADO POMELO BILBERRY KIWIFRUIT POMELO BILBERRY }
What action would you like to perform?
S
Please enter a string to remove from the linked list:
POMELO
What action would you like to perform?
L
{ AVOCADO BILBERRY KIWIFRUIT BILBERRY }
What action would you like to perform?
Q
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.