Overview This lab is to expose you to a singly Linked List of String The Lab The
ID: 3908579 • Letter: O
Question
Overview This lab is to expose you to a singly Linked List of String The Lab The add() method in the StringLinkedBag.java in Canvas, adds to the end of the Linked List. Modify the add) method to maintain a..z order. Make sure your revised add) method as O(n) in the worst case scenario. Make sure you add your name to the comments before the add method. Grading Rubric A more formal grading rubric will be created as a separate file. In the meantime: The only comment needed is you add your name to the Javadoc comments for the add method. make sure you follow the naming guidelines for variable names make sure your code is properly indenting make sure your StringLinkedBag.java file compiles . Submitting the Lab All you need to submit via Canvas is your modified StringLinkedBag.java file.Explanation / Answer
Here is the completed code for this problem. Please note that as you didn’t provide the code for ListerPrototype2 class, I removed the iterator method for successful compilation of the code. You can paste the code when you run. Also defined a toString() method to return a string containing all bag elements, so that we can test the working of add method. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// StringLinkedBag.java
/**
* Programmed by Stephen Brower Inspired by Michael Main Date Written 10/1/2012
* Date Modified 10/3/2012 - added grab() Date Modified 2/19/2014 - added
* comments in JavaDoc format Date Modified 9/21/2014 - Pulled out Part 2
* methods Date Modified 6/19/2018 - added tail Date Modified 6/21/2018 - pruned
* for Lab 4 Sum 18
*/
public class StringLinkedBag {
private StringNode head;
private StringNode tail;
private int numElements;
/**
* No-arg Constructor
*/
public StringLinkedBag() {
head = null;
tail = null;
numElements = 0;
}
/**
* The getSize method returns the linked bag's current size.
*
* @return The value in the numElements field.
*/
public int getSize() {
return numElements;
}
/**
* The add method adds a String to the linked bag This version just sticks
* the value at the end of the list
*
* @param newElement
* The String to be added to the linked bag.
*/
public void add(String newElement) {
if (tail == null) // is list empty?
{
/**
* Adding as the first node
*/
head = new StringNode(newElement, null);
tail = head;
} else {
/**
* Defining a node with new data
*/
StringNode newNode = new StringNode(newElement, null);
/**
* checking if the newnode should be inserted before first node
*/
if (newElement.compareTo(head.getData()) < 0) {
// new node's data is lexicographically before head node's data
newNode.setLink(head);
head = newNode;
} else {
/**
* iterating through each node for once
*/
StringNode current = head;
StringNode next = head.getLink();
boolean added = false;
while (next != null) {
/**
* checking if the value can be added in the middle of
* current pair of nodes
*/
if (newElement.compareTo(current.getData()) >= 0
&& newElement.compareTo(next.getData()) < 0) {
/**
* Adding to the middle
*/
newNode.setLink(next);
current.setLink(newNode);
added = true;
break;
}
// moving to next pair of nodes
current = current.getLink();
next = next.getLink();
}
/**
* if still not added, adding to the end of the list
*/
if (!added) {
tail.setLink(newNode);
tail = newNode;
}
}
}
numElements++;
}
/**
* The exists method looks for a String in the linked bag
*
* @param target
* The String to be found in the linked bag.
* @return a boolean to indicate if target is found in the linked bag.
*/
public boolean exists(String target) {
boolean found = false;
StringNode cursor = head;
while (cursor != null && !found) {
if (cursor.getData().equalsIgnoreCase(target))
found = true;
else
cursor = cursor.getLink();
}
return found;
// although not "efficient", this method could contain just 1 line:
// return (countOccurences(target) > 0);
}
/**
* The countOccurrences method looks for a String in the linked bag
*
* @param target
* The String to be found in the linked bag.
* @return an int with the number of times target is found in the linked
* bag.
*/
public int countOccurrences(String target) {
int numOccurrences = 0;
StringNode cursor;
for (cursor = head; cursor != null; cursor = cursor.getLink())
if (cursor.getData().equalsIgnoreCase(target))
numOccurrences++;
return numOccurrences;
}
/**
* The remove method looks for a String in the linked bag and removes it
* this version of remove maintains order
*
* @param target
* The String to be removed from the linked bag.
* @return a boolean to indicate if the target was removed from the bag.
*/
public boolean remove(String target) {
boolean found = false;
StringNode cursor = head, previous = null;
while (cursor != null && !found) {
if (cursor.getData().equalsIgnoreCase(target))
found = true;
else {
previous = cursor;
cursor = cursor.getLink();
}
}
if (found && cursor != null) {
if (previous == null)
head = head.getLink();
else
previous.setLink(cursor.getLink());
if (tail == cursor)
tail = previous;
numElements--;
}
return found;
}
/**
* method to return a String containing contents in bag, just implemented
* for testing the working of add method from test class
*/
@Override
public String toString() {
StringNode node = head;
String data = "[";
while (node != null) {
data += "{" + node.getData() + "}";
node = node.getLink();
if (node != null) {
data += ", ";
}
}
data += "]";
return data;
}
}
// Test.java (used for testing the modified method)
public class Test {
public static void main(String[] args) {
/**
* creating a bag and adding some random elements
*/
StringLinkedBag bag=new StringLinkedBag();
bag.add("Tomato");
bag.add("Almond");
bag.add("Zippy");
bag.add("Bunny");
bag.add("Dummy");
bag.add("Mummy");
bag.add("Zippy");
/**
* displaying the bag (using the newly created toString() method)
*/
System.out.println(bag);
}
}
/*OUTPUT*/
[{Almond}, {Bunny}, {Dummy}, {Mummy}, {Tomato}, {Zippy}, {Zippy}]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.