Homework SourseClass Diagram In the Assignment 10 you are given three files
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.
2.
public boolean isEmpty()
The isEmpty method returns true of the linked list is empty, false otherwise.
3.
public void addElement(Object element)
The addElement adds the parameter element at the parameter in the linked list in alphabetical order. For instance, if the linked list contains {Apple, Banana, Grape}, and a user tries to add \"Carrot\", then it should be added as:
{Apple, Banana, Carrot, Grape}.
4.
public Object removeElement(int index)
The removeElement removes the string (Object) at the parameter index and returns it. Note that this index starts with 0 just like array indices. For instance, if the linked list contains {Apple, Banana, Carrot, Grape} and the parameter index is 3, then \"Grape\" should be remove. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class (and the content of the linked list should remain unchanged).
5.
public Object getElement(int index)
The getElement searches the string (Object) at the parameter index and returns it. Note that this index starts with 0 just like array indices. For instance, if the linked list contains {Apple, Banana, Carrot, Grape} and the parameter index is 3, then \"Grape\" will be returned. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class (and the content of the linked list should remain unchanged).
6.
public void searchAndReplace(Object oldString, Object newString)
The searchAndReplace method searches all occurrences of the first parameter string (object) in the list, and replaces them with the second parameter string (object). If the parameter string does not exist in the linked list, then the linked list content will not change.
7.
public int indexOfLast(Object searchString)
The indexOfLast searches the parameter string (object) with the largest index, and returns its index. If the parameter string does not exist in the linked list, then it should return -1.
For instance, if the linked list contains { Apple Banana Banana Orange }, then after calling this method with the parameter \"Banana\", then it should return 2, which is the index of later Banana.
Solution
/* Posting Only the LinkedList.java where new methods have been added. */
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();
}
/*********************************************************
* Add your methods here
*********************************************************/
// 1. toString()
// Override because we are overriding the Object class toString() method
@Override
public String toString() {
/*
* Since we need to add all the Nodes, use StringBuffer which is mutable
* unlike String which is Immutable. This increases efficiency.
*/
StringBuffer ansBuffer = new StringBuffer(\"{ \");
// add Nodes to the ans string ony if list is not empty
if (!isEmpty()) {
ListIterator listIteratorObject = listIterator();
while (listIteratorObject.hasNext()) {
ansBuffer.append(listIteratorObject.next() + \" \");
}
}
ansBuffer.append(\"}\ \");
// ansBuffer.toString() returns a String object
return ansBuffer.toString();
}
// 2. isEmpty() method
public boolean isEmpty() {
// return this.first is null then return true else return false ( not
// Empty)
return this.first == null;
}
// 3. addElement(Object element)
public void addElement(String element) {
if (isEmpty()) {
addFirst(element);
} else {
// Empty String is also considered as a valid string since nothing
// has been mentioned about that case
ListIterator listIteratorObject = listIterator();
while (listIteratorObject.hasNext()) {
String current = (String) listIteratorObject.next();
if (element.compareTo(current) < 0) {
// change current string to new element
listIteratorObject.set(element);
//add current String after the current position
listIteratorObject.add(current);
return;
}
}
listIteratorObject.add(element);
}
}
// 4. Remove element at index removeIndex
public String removeElement(int removeIndex) {
// Holds the String which is Being removed
String removedString = null;
// If list is empty or removeIndex is negative, throw Exception
if (isEmpty() || removeIndex < 0) {
IndexOutOfBoundsException ex = new IndexOutOfBoundsException();
throw ex;
} else {
// Iterate to the removeIndex position
ListIterator listIteratorObject = listIterator();
while (removeIndex-- >= 0) {
if (listIteratorObject.hasNext()) {
removedString = (String) listIteratorObject.next();
} else {
// If no element left to iterate , throw Exception
IndexOutOfBoundsException ex = new IndexOutOfBoundsException();
throw ex;
}
}
// Remove the Node at that position
listIteratorObject.remove();
}
return removedString;
}
// 5. Same logic as above, only change is at the end do not remove the
// string
public String getElement(int getIndex) {
String getString = null;
if (isEmpty() || getIndex < 0) {
IndexOutOfBoundsException ex = new IndexOutOfBoundsException();
throw ex;
} else {
ListIterator listIteratorObject = listIterator();
while (getIndex-- >= 0) {
if (listIteratorObject.hasNext()) {
getString = (String) listIteratorObject.next();
} else {
IndexOutOfBoundsException ex = new IndexOutOfBoundsException();
throw ex;
}
}
}
return getString;
}
// 6. search original string and replace with newStr
public void searchAndReplace(String original, String newStr) {
ListIterator listIteratorObject = listIterator();
// Iterate up to the last Node
while (listIteratorObject.hasNext()) {
// If current Iterator object equals Original String ,set it to new
// String
if (original.equals(listIteratorObject.next())) {
listIteratorObject.set(newStr);
}
}
}
// 7. return LastIndexOf of the string str2.
public int indexOfLast(String str2) {
int lastIndex = -1;
int currentIndex = -1;
ListIterator listIteratorObject = listIterator();
// Iterate up to the last Node
while (listIteratorObject.hasNext()) {
// keep track of the current index
currentIndex++;
// Update Last Index if str2 matches current string
if (str2.equals(listIteratorObject.next()))
lastIndex = currentIndex;
}
return lastIndex;
}
/*********************************************************
* End of added methods
*********************************************************/
// 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
