In the Assignment #10, you are given three files Assignment10.java, LinkedList.j
ID: 3567686 • Letter: I
Question
In the Assignment #10, you are given three files Assignment10.java, LinkedList.java, ListIterator.java.
You will need to add additional methods in the LinkedList class. The LinkedList will be tested using integers only.
Specifically, the following methods must be implemented in the LinkedList class:
Note: 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 the linked list.
1.
public String toString()
The toString method returns a string of the following format:
{ 4 5 6 }
The string starts with "{" and ends with "}", and there is a space between integers and "{" or "}". If the list is empty, it returns "{ }" with a space in between.
2.
public int size()
The size method returns the number of integers in the inked list.
3.
public boolean isEmpty()
The isEmpty method returns true if the linked list is empty, returns false otherwise.
4.
public object searchElement(int index)
The searchElement method searches for the element at the specified index. It returns the object at the specified index.
5.
public void addElement(int index, Object element)
The addElement adds the parameter element at the specified index. The 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.
6.
public void reverse()
The reverse method reverses the integers in this linked list.
7.public void removeLastFew(int howMany)
The removeLastFew method removes the elements from the end of the linked list. If the parameter integer is larger than the current size of the linked list, then the linkedlist will be empty. If the parameter integer is less than 0, nothing should be removed from the linked list.
Assignment10.java
LinkedList.java
ListIterator.java
Explanation / Answer
Program code: Modified code is highted with Bold letters
import java.util.NoSuchElementException;
public class LinkedList
{
private class Node
{
public Object data;
public Node next;
}
//instance variable first points to the beginning of the linked list
private Node first;
public int n;
/**
Constructs an empty linked list.
*/
public LinkedList()
{
first = null;
n=0;
}
/**
@return the first element in the linked list
*/
public Object getFirst()
{
if (first == null)
throw new NoSuchElementException();
return first.data;
}
/**
@return the removed element
*/
public Object removeFirst()
{
if (first == null)
throw new NoSuchElementException();
Object element = first.data;
first = first.next;
n--;
return element;
}
//size method specifies the
//size of the bag
public int size()
{
return n;
}
/**
Adds an element to the front of the linked list.
@param element the element to add
*/
public void addFirst(Object element)
{
Node newNode = new Node();
newNode.data = element;
newNode.next = first;
//change the first reference to the new node
first = newNode;
n++;
}
//isEmpty method
public boolean isEmpty()
{
return first == null;
}
public void addElement(int index, Object element)
{
if(index==0)
{
addFirst(element);
}
else
{
Node node=new Node();
node.data=element;
Node present=first;
for(int i=0;i<n && present.next!=null ;i++)
{
present=present.next;
}
node.next=present.next;
present.next=node;
n++;
}
}
public Object searchElement(int index)
{
Node nNode=getNode(index);
Node fnode=searchNode(nNode,nNode.data);
return fnode.data;
}
public Node searchNode(Node head, Object element) {
System.out.println("In Search Node");
Node cHead = first;
while (cHead != null) {
if (cHead.data == element)
return cHead;
cHead = cHead.next;
}
return null;
}
public boolean removeLastFew(int num)
// post: removes the element at the specified position in this list.
{
Node current = first;
int index=n-num;
for(int i = 0; i < index; i++)
{
if(current.next == null)
return false;
current = current.next;
}
current.next=current.next.next;
n--; // decrement the number of elements variable
return true;
}
public String toString()
{
Node current = first;
String output = "{";
while(current != null)
{
output += "" + current.data.toString()+"," ;
current = current.next;
}
output+="}";
return output;
}
public void reverse()
{
reverse(first);
}
public void reverse(Node node) {
if (node != null) {
reverse(node.next);
System.out.print(" " + node.data);
}
}
/*****************************************************************************/
/**
Returns an iterator for iterating through this list.
@return an iterator for iterating through this list
*/
public ListIterator listIterator()
{
return new LinkedListIterator();
}
private class LinkedListIterator implements ListIterator
{
private Node position;
private Node previous;
/**
Constructs an iterator that points to the front
of the linked list.
*/
public LinkedListIterator()
{
position = null;
previous = null;
}
/**
Moves the iterator past the next element.
@return the traversed element
*/
public Object next()
{
if (!hasNext())
throw new NoSuchElementException();
previous = position; // Remember for remove
if (position == null)
position = first;
else
position = position.next;
return position.data;
}
/**
Tests if there is an element after the iterator
position.
@return true if there is an element after the iterator
position
*/
public boolean hasNext()
{
if (position == null)
return first != null;
else
return position.next != null;
}
/**
Adds an element before the iterator position
and moves the iterator past the inserted element.
@param element the element to add
*/
public void add(Object element)
{
if (position == null)
{
addFirst(element);
position = first;
}
else
{
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
position.next = newNode;
position = newNode;
}
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)
throw new IllegalStateException();
if (position == first)
{
removeFirst();
}
else
{
previous.next = position.next;
n--;
}
position = previous;
}
/**
Sets the last traversed element to a different
value.
@param element the element to set
*/
public void set(Object element)
{
if (position == null)
throw new NoSuchElementException();
position.data = element;
}
}//end of LinkedList iterator class
}//end of Linked List class
Unmodified code:
public interface ListIterator
{
/**
Moves the iterator past the next element.
@return the traversed element
*/
Object next();
/**
Tests if there is an element after the iterator
position.
@return true 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.
@param element the element to add
*/
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.
@param element the element to set
*/
void set(Object element);
}
import java.io.*;
import java.util.NoSuchElementException;
public class Assignment10
{
public static void main(String[] args)
{
char input1;
int inputInteger;
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
System.out.print("Please enter an integer to add: ");
int int1 = Integer.parseInt(stdin.readLine().trim());
System.out.print("Please enter an index to add: ");
inputInfo = stdin.readLine().trim();
int addIndex = Integer.parseInt(inputInfo);
list1.addElement(addIndex, int1);
break;
case 'E': //Search for an integer at an Index
System.out.print("Please enter an index to search: ");
int searchIndex = Integer.parseInt(stdin.readLine().trim());
System.out.print("Integer at the given index is " + list1.searchElement(searchIndex) + " ");
break;
case 'L': //List integers
System.out.print(list1.toString());
break;
case 'O': // List Current Size
System.out.print("The current size is " + list1.size() + " ");
break;
case 'T': //Reverse
list1.reverse();
System.out.print("list reversed ");
break;
case 'R': //Remove Last few --
System.out.print("How many to remove: ");
inputInteger = Integer.parseInt(stdin.readLine().trim());
list1.removeLastFew(inputInteger);
System.out.print("Removed " + inputInteger + " elements from the list ");
break;
case '?': //Display Menu
printMenu();
break;
case 'Q': //Quit
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 an Integer " +
"E Search for an Integer " +
"L List Integers " +
"R Remove Last Few " +
"T Reverse " +
"O List Current Size " +
"Q Quit " +
"? Display Help ");
} //end of printMenu()
}
-------------------------------------------------------------------------------------------------------------------
Sample Output:
Choice Action
------ ------
A Add an Integer
E Search for an Integer
L List Integers
R Remove Last Few
T Reverse
O List Current Size
Q Quit
? Display Help
What action would you like to perform?
A
Please enter an integer to add:
40
Please enter an index to add:
0
What action would you like to perform?
A
Please enter an integer to add:
50
Please enter an index to add:
1
What action would you like to perform?
A
Please enter an integer to add:
30
Please enter an index to add:
2
What action would you like to perform?
A
Please enter an integer to add:
80
Please enter an index to add:
3
What action would you like to perform?
A
Please enter an integer to add:
70
Please enter an index to add:
4
What action would you like to perform?
L
{40,50,30,80,70,}What action would you like to perform?
O
The current size is 5
What action would you like to perform?
E
Please enter an index to search:
2
In Search Node
Integer at the given index is 30
What action would you like to perform?
R
How many to remove:
2
Removed 2 elements from the list
What action would you like to perform?
L
{40,50,30,80,}What action would you like to perform?
T
80 30 50 40list reversed
What action would you like to perform?
?
Choice Action
------ ------
A Add an Integer
E Search for an Integer
L List Integers
R Remove Last Few
T Reverse
O List Current Size
Q Quit
? Display Help
What action would you like to perform?
Q