Linked Lists Purpose: -To implement a linked list of Strings using the \"Bag\" a
ID: 3672029 • Letter: L
Question
Linked Lists
Purpose:
-To implement a linked list of Strings using the "Bag" approach
Task:
-Write the StringNode class following the UML below and write the StringLinkedBag following the UML below.
UML
UML for StringNode
-data:String
-link:StrongNode
+StringNode(initialData:String, initialLink:StringNode)
+getData():String
+getLink():StringNode
+setData(initialData:String):void
+setLink(initialLink:StringNode):void
UML for StringLinkedBag
-head:StringNode
-numElements:int
+StringLinkedBag()
+getSize():int
+toString():String
+add(element:String):void
+exists(target:String):boolean
+countOccurrences(target:String):int
+remove(target:String):boolean
Tester
-The tester will check to see if the tests for exists() counterOccurrences(), or remove() methods succeed or not.
NOTE: Tester assumes that toString() has been implemented correctinly in StringLinkedBag
SAMPLE RUN:
run:
Display Bag on startup
Empty: Check [empty]
Currently: 0 adding: Swiss...added...now: 1
Currently: 1 adding: Colby...added...now: 2
Currently: 2 adding: MonteRey jack...added...now: 3
Currently: 3 adding: Cheddar...added...now: 4
Currently: 4 adding: Havarti...added...now: 5
Currently: 5 adding: MoNterey JAck...added...now: 6
Currently: 6 adding: Alpine Lace...added...now: 7
Currently: 7 adding: Wisconsin Cheddar...added...now: 8
Display Bag after adds
Not Empty: Check [Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
edam is not in the bag -good
sWiss is in the bag -good
coLBy is in the bag -good
monTereY jaCk is in the bag-good
Display Bag after searches
Not Empty: Check [Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
# of edam in bag: 0 -good
# of sWiss in bag: 1 -good
# of coLBy in bag: 1 -good
# of monTereY jaCk in bag: 2 -good
Display Bag after counts
Not Empty: Check [Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
Edam remove failed -good
Display Bag after trying to remove: [Edam]
Not Empty: Check [Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
Colby removed -good
Display Bag after trying to remove: [Colby]
Not Empty: Check [Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Wisconsin Cheddar, Swiss]
Size: 7
Alpine Lace removed -good
Display Bag after trying to remove: [Alpine Lace]
Not Empty: Check [MoNterey JAck, Havarti, Cheddar, MonteRey jack, Wisconsin Cheddar, Swiss]
Size: 6
Swiss removed -good
Display Bag after trying to remove: [Swiss]
Not Empty: Check [Havarti, Cheddar, MonteRey jack, Wisconsin Cheddar, MoNterey JAck]
Size: 5
BUILD SUCCESSFUL (total time: 0 seconds)
Explanation / Answer
StringLinkedBag.java
public class StringLinkedBag
{
//region FIELDS
private StringNode head; //the first node in the list
private int numElements; //the number of elements in the list
//endregion
public StringLinkedBag()
{
head = null;
numElements = 0;
}
//endregion
//region ACCESSORS
/*
Returns the size of the list.
@returns the size of the list.
*/
public int getSize()
{
return numElements;
}
/*
Checks whether or not the given element exists within the list.
@params The element to be searched for in the list.
@returns Whether or not the element exists.
*/
public boolean exists(String element)
{
boolean elementFound = false;
for (StringNode cursor = head; cursor != null && !elementFound; cursor = cursor.getLink())
{
if (cursor.getData().equalsIgnoreCase(element))
{
elementFound = true;
}
}
return elementFound;
}
/*
Counts the number of times an element is contained within the list.
@params The element to be searched for.
@returns The number of times the element has been found within the list.
*/
public int countOccurrences(String element)
{
int occurrences = 0;
for (StringNode cursor = head; cursor != null; cursor = cursor.getLink())
{
if (cursor.getData().equalsIgnoreCase(element))
{
occurrences++;
}
}
return occurrences;
}
//endregion
//region MUTATORS
/*
Add an element to the list.
@param element The element to be added to the list.
*/
public void add(String element)
{
head = new StringNode(element, head);
numElements++;
}
/*
Removes the element from the list.
@param element The element to be removed.
*/
public boolean remove(String element)
{
boolean elementFound = false;
StringNode targetNode = head;
for (StringNode cursor = head; cursor != null && !elementFound; cursor = cursor.getLink())
{
if (cursor.getData().equalsIgnoreCase(element)) {
elementFound = true;
targetNode = cursor;
}
}
if (elementFound)
{
targetNode.setData(head.getData());
head = head.getLink();
numElements--;
}
return elementFound;
}
//endregion
//region OVERRIDES
/*
Returns the list as a single string.
@returns The list as a single String.
*/
public String toString()
{
//first check for a null head, or 0 elements
if (head == null || numElements == 0)
{
return "empty";
}
String returnString = "";
for (StringNode cursor = head; cursor != null; cursor = cursor.getLink())
{
returnString += cursor.getData();
if (cursor.getLink() == null)
{
returnString += ".";
}
else
{
returnString += ", ";
}
}
return returnString;
}
//endregion
StringNode.java
public class StringNode
{
//region FIELDS
private String data; //holds the string
private StringNode link; //the node this one is linked to
//endregion
//region CONSTRUCTORS
/*
Default constructor. Initializes with a data item and a link.
@param initialData The initial string this node is initialized with.
@param initialLink The initial string this node is initialized with.
*/
public StringNode(String initialData, StringNode initialLink)
{
data = initialData;
link = initialLink;
}
//endregion
//region ACCESSORS
/*
Returns the data associated with this node.
@returns The data associated with this node.
*/
public String getData()
{
return data;
}
/*
Returns the link associate with this node.
@returns The link associated with this node.
*/
public StringNode getLink()
{
return link;
}
//endregion
//region MUTATORS
/*
Changes the data associated with this node.
@params The new data to be associated with this node.
*/
public void setData(String newData)
{
data = newData;
}
/*
Changes the link associated with this node.
@params The new data to be associated with this node.
*/
public void setLink(StringNode newLink)
{
link = newLink;
}
//endregion
}
Lab4_LinkedListStringBag.java
public class Lab04StringLinkedBag
{
/**
* The main method is the program's starting point.
* @param args the command line arguments
*/
public static void main(String[] args)
{
// creates a linked bag
StringLinkedBag cheeseBag = new StringLinkedBag();
//test data
String[] stringsToAddArray = {"Swiss", "Colby", "MonteRey jack", "Cheddar",
"Havarti", "MoNterey JAck", "Alpine Lace",
"Wisconsin Cheddar"};
String[] stringsToFindArray = {"edam", "sWiss", "coLBy",
"monTereY jaCk"};
boolean[] expectedFindResults = {false,true,true,true};
String[] stringsToCountArray = stringsToFindArray.clone();
int[] expectedCountResults = {0,1,1,2};
String[] stringsToRemoveArray = {"Edam", "Colby", "Alpine Lace", "Swiss"};
boolean[] expectedRemoveResults = {false,true,true,true};
// show initial bag
displayBag("Display Bag on startup",cheeseBag);
// add some cheeses to bag
for (String stringToAdd : stringsToAddArray)
addValue(stringToAdd,cheeseBag);
// show bag after adds
displayBag("Display Bag after adds",cheeseBag);
// look for some cheeses
for (int i = 0; i < stringsToFindArray.length; i++)
displayValueExists(stringsToFindArray[i],cheeseBag,expectedFindResults[i]);
// show bag after searches
displayBag("Display Bag after searches",cheeseBag);
// count some cheeses
for (int i = 0; i < stringsToCountArray.length; i++)
displayCountValue(stringsToCountArray[i],cheeseBag,expectedCountResults[i]);
// show bag after counted
displayBag("Display Bag after counts",cheeseBag);
// remove some cheeses AND display
for (int i = 0; i < stringsToRemoveArray.length; i++)
removeValue(stringsToRemoveArray[i],cheeseBag,expectedRemoveResults[i]);
}
/**
the displayValueExists method displays whether aValue exists in aBag
@param aValue the String to look for
@param aBag the StringLinkedBag to look in
*/
public static void displayValueExists(String aValue, StringLinkedBag aBag,
boolean shouldSucceed)
{
if (aBag.exists(aValue))
{
System.out.print( aValue + " is in the bag");
if (!shouldSucceed)
System.out.print(" <==== issue - shouldn't exist");
else
System.out.print(" -good");
}
else
{
System.out.print( aValue + " is not in the bag");
if (shouldSucceed)
System.out.print(" <==== issue - should exist");
else
System.out.print(" -good");
}
System.out.println();
}
/**
the displayBag method displays the linked bag
@param heading a String to display before the bag
@param aBag the StringLinkedBag to display
*/
public static void displayBag(String heading, StringLinkedBag aBag)
{
System.out.println(heading);
if (aBag.getSize() == 0)
{
System.out.println("Empty: Check [ " + aBag + "]");
}
else
{
System.out.println("Not Empty: Check [ " + aBag + "]");
System.out.println("Size: " + aBag.getSize());
}
System.out.println();
}
/**
the displayCountValue method displays the number of aValue that occurs in aBag
@param aValue the String to look for
@param aBag the StringLinkedBag to look in
*/
public static void displayCountValue(String aValue, StringLinkedBag aBag,
int expectedCount)
{
int count = aBag.countOccurrences(aValue);
System.out.printf("# of %20s in bag: %2d", aValue, count );
if (count != expectedCount)
System.out.print(" <==== issue - expected "+expectedCount);
else
System.out.print(" -good");
System.out.println();
}
/**
the removeValue method attempts to remove aValue from aBag
@param aValue the String to remove
@param aBag the StringLinkedBag to look in
*/
public static void removeValue(String aValue, StringLinkedBag aBag,
boolean shouldSucceed)
{
boolean wasInBagBeforeRemoval;
if (aBag.toString().toLowerCase().indexOf(aValue.toLowerCase()) == -1)
wasInBagBeforeRemoval = false;
else
wasInBagBeforeRemoval = true;
// was remove successful?
if (aBag.remove(aValue))
{
// remove() returned true
System.out.print(aValue+" removed");
// should remove have suceeded?
if (shouldSucceed)
{
// double check it is really gone
if (aBag.toString().toLowerCase().indexOf(aValue.toLowerCase()) == -1)
System.out.print(" -correct return- value gone from bag -good");
else
System.out.print(" -correct boolean return- but value is still in bag <==== issue");
}
else // remove should not have succeeded
{
// remove returned true but false expected
// was it there?
if (wasInBagBeforeRemoval)
{
// how can something that shouldn't have been in the bag
// had actually been in the bag?
System.out.print(" -uhhhhh...possible logic issue in tester-contact instructor<<Code A");
if (aBag.toString().toLowerCase().indexOf(aValue.toLowerCase()) == -1)
System.out.print("01>> <==== issue");
else
System.out.print("02>> <==== issue");
}
else
{
// is it there
if (aBag.toString().toLowerCase().indexOf(aValue.toLowerCase()) == -1)
System.out.print(" remove() returned true and shouldn't have / it's not in bag <==== issue");
else
System.out.print(" remove() returned true and shouldn't have and it's still in bag <==== issue");
}
}
}
else // remove returned false
{
// remove() returned false
System.out.printf(aValue+" remove failed");
// should remove have returned true?
if (shouldSucceed)
{
// remove() returned false, should have returned true
// was it actually removed?
if (aBag.toString().toLowerCase().indexOf(aValue.toLowerCase()) == -1)
{
// remove() returned false but did remove it
System.out.print(" - remove worked but returned false <==== issue");
}
else
{
// remove() returned false and that was expected
// make sure it isn't there
System.out.print(" - remove returned false item still in bag <==== issue");
}
}
else // remove() returned false as exptected
{
if (aBag.toString().toLowerCase().indexOf(aValue.toLowerCase()) == -1)
{
if (wasInBagBeforeRemoval)
{
// how can something that shouldn't have been in the bag
// had actually been in the bag?
System.out.print(" -uhhhhh...possible logic issue in tester-contact instructor<<Code B02>> <==== issue");
}
else
System.out.print(" wasn't in bag before removal so it was expected to fail remove-good");
}
else
{
System.out.print(" -received expected false return value, but it is still in the bag <==== issue");
}
}
}
System.out.println();
displayBag("Display Bag after trying to remove: ["+aValue+"]",aBag);
}
/**
the addValue method adds aValue to aBag
@param aValue the String to remove
@param aBag the StringLinkedBag to look in
*/
public static void addValue(String aValue, StringLinkedBag aBag)
{
System.out.print("Currently: "+aBag.getSize()+" adding: "+aValue);
aBag.add(aValue);
System.out.println("...added...now: "+aBag.getSize());
// uncomment next line if you need to debug
//displayBag("Display Bag after adding: ["+aValue+"]",aBag);
}
}
Output:
Display Bag on startup
Empty: Check [ empty]
Currently: 0 adding: Swiss...added...now: 1
Currently: 1 adding: Colby...added...now: 2
Currently: 2 adding: MonteRey jack...added...now: 3
Currently: 3 adding: Cheddar...added...now: 4
Currently: 4 adding: Havarti...added...now: 5
Currently: 5 adding: MoNterey JAck...added...now: 6
Currently: 6 adding: Alpine Lace...added...now: 7
Currently: 7 adding: Wisconsin Cheddar...added...now: 8
Display Bag after adds
Not Empty: Check [ Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
edam is not in the bag -good
sWiss is in the bag -good
coLBy is in the bag -good
monTereY jaCk is in the bag -good
Display Bag after searches
Not Empty: Check [ Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
# of edam in bag: 0 -good
# of sWiss in bag: 1 -good
# of coLBy in bag: 1 -good
# of monTereY jaCk in bag: 2 -good
Display Bag after counts
Not Empty: Check [ Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
Edam remove failed wasn't in bag before removal so it was expected to fail remove-good
Display Bag after trying to remove: [Edam]
Not Empty: Check [ Wisconsin Cheddar, Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Colby, Swiss]
Size: 8
Colby removed -correct return- value gone from bag -good
Display Bag after trying to remove: [Colby]
Not Empty: Check [ Alpine Lace, MoNterey JAck, Havarti, Cheddar, MonteRey jack, Wisconsin Cheddar, Swiss]
Size: 7
Alpine Lace removed -correct return- value gone from bag -good
Display Bag after trying to remove: [Alpine Lace]
Not Empty: Check [ MoNterey JAck, Havarti, Cheddar, MonteRey jack, Wisconsin Cheddar, Swiss]
Size: 6
Swiss removed -correct return- value gone from bag -good
Display Bag after trying to remove: [Swiss]
Not Empty: Check [ Havarti, Cheddar, MonteRey jack, Wisconsin Cheddar, MoNterey JAck]
Size: 5
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.