In this lab, we will implement the Linked Bag. The bag will contain a sequence of...
In this lab, we will implement the Linked Bag. The bag will contain a sequence of strings. First, you need to design the Node class (Node.java). It will contain an integer data and a reference to thenext Node. The constructor of Node class receives an integer and assigns it to the data field. It also has a default constructor.
Data Next Node
Then we will design another class named LinkedBag (LinkedBag.java). LinkedBag class has an instance variable called firstNode of type Node. It has the following methods:
-
public LinkedBag()
The default constructor of class LinkedBag.
-
public int getCurrentSize()
Gets the current number of entries in this bag.
-
public T[] toArray()
Retrieves all entries that are in this bag.
-
public boolean addToHead(T newEntry)
Adds the specified new entry to the start of the linked bag.
-
public boolean addToTail(T newEntry)
Adds the specified new entry to the end of the linked bag.
-
public T removeHead()
Removes and returns the first item from the bag. If the bag has no nodes, returns null.
-
public T removeTail()
Removes and returns the last item from the bag.
Implement all the methods in LinkedBag class.
======================================== Adding A to the Head of
the bag:
The bag contains 1 string(s), as follows:
A ======================================== Adding B to the Head of
the bag:
The bag contains 2 string(s), as follows:
BA ======================================== Adding C to the Tail of
the bag:
The bag contains 3 string(s), as follows:
BA C ======================================== Adding D to the Tail
of the bag:
The bag contains 4 string(s), as follows:
BA C D ======================================== Removing an entry
from the head:
The bag contains 3 string(s), as follows:
A CD ======================================== Removing an entry
from the Tail:
The bag contains 2 string(s), as follows: AC
-------------------------------------------------------------------------------------------------
Baginterface.java
/**
An interface that describes the operations of a bag of
objects.
*/
public interface BagInterface<T>
{
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in the bag.
*/
public int getCurrentSize();
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in the
bag.
Note: If the bag is empty, the returned array is empty. */
public T[] toArray();
/** Adds a new entry to the head of this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not.
*/
public boolean addToHead(T newEntry);
/** Adds a new entry to the tail of this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not.
*/
public boolean addToTail(T newEntry);
/** Removes one unspecified entry from the head of this bag, if
possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T removeHead();
/** Removes one entry from the tail of this bag, if
possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T removeTail();
} // end BagInterface
----------------------------------------------------------------------------------------------------
LinkedBag.java
/** A class of bags whose entries are stored in a chain of linked nodes. The
bag is never full. */public class LinkedBag<T> implements BagInterface<T>{
private Node firstNode; // Reference to first node private int
numberOfEntries; public LinkedBag() {
} // end default constructor /** Adds a new entry to the head of this bag.
@param newEntry The object to be added as a new entry. @return
True, as adding a new entry should always be successful. */public boolean
addToHead(T newEntry) // OutOfMemoryError possible {
} // end addToHead /** Adds a new entry to the tail of
this bag. @param newEntry The object to be added as a new entry. @return
True, as adding a new entry should always be successful. */ public boolean
addToTail(T newEntry) // OutOfMemoryError possible {
} // end addToTail /** Removes the first entry from this
bag, if possible. @return Either the removed entry, if the removal was
successful, or null if not. */ public T removeHead() {
} // end removeHead /** Removes the last entry from this
bag, if possible. @return Either the removed entry, if the removal was
successful, or null if not. */ public T removeTail() {
} // end removeHead /** Retrieves all entries that are
in this bag. @return A newly allocated array of all the entries in the
bag. */ public T[] toArray() {
} // end toArray /** Gets the number of entries currently in this bag.
@return The integer number of entries currently in the bag. */ public int
getCurrentSize() {
} // end
getCurrentSize // A class of nodes for a chain of linked nodes. private
class Node {
} // end Node} // end LinkedBag
--------------------------------------------------------------------------
LinkedBagTester.java
/**
A demonstration of the class LinkedBag.
*/
public class LinkedBagTester
{
public static void main(String[] args)
{
BagInterface<String> aBag = new LinkedBag<>();
// Adding strings to the head of bag
String contentsOfBag = "A";
testAddToHead(aBag, contentsOfBag);
String contentsOfBag1 = "B";
testAddToHead(aBag, contentsOfBag1);
// Adding strings to the tail of bag
String contentsOfBag3 = "C";
testAddToTail(aBag, contentsOfBag3);
String contentsOfBag4 = "D";
testAddToTail(aBag, contentsOfBag4);
// Removing an entry from the head
testRemoveHead(aBag);
// Removing an entry from the tail
testRemoveTail(aBag);
} // end main
// Tests the method addToHead.
private static void testAddToHead(BagInterface<String> aBag,
String content)
{
System.out.print("Adding " + content + " to the Head of the bag:
");
aBag.addToHead(content);
System.out.println();
displayBag(aBag);
} // end testAdd
// Tests the method addToTail.
private static void testAddToTail(BagInterface<String> aBag,
String content)
{
System.out.print("Adding " + content + " to the Tail of the bag:
");
aBag.addToTail(content);
System.out.println();
displayBag(aBag);
} // end testAdd
// Tests the remove methods from the Head.
private static void testRemoveHead(BagInterface<String>
aBag)
{
System.out.print("Removing an entry from the head: ");
aBag.removeHead();
System.out.println();
displayBag(aBag);
} // end testRemove
// Tests the remove methods from the Tail.
private static void testRemoveTail(BagInterface<String>
aBag)
{
System.out.print("Removing an entry from the Tail: ");
aBag.removeTail();
System.out.println();
displayBag(aBag);
} // end testRemove
// Tests the method toArray while displaying the bag.
private static void displayBag(BagInterface<String>
aBag)
{
System.out.println("The bag contains " + aBag.getCurrentSize()
+
" string(s), as follows:");
Object[] bagArray = aBag.toArray();
for (int index = 0; index < bagArray.length; index++)
{
System.out.print(bagArray[index] + " ");
} // end for
System.out.println();
} // end displayBag
} // end Project1
/*
TAdding A to the Head of the bag:
The bag contains 1 string(s), as follows:
A
Adding B to the Head of the bag:
The bag contains 2 string(s), as follows:
B A
Adding C to the Tail of the bag:
The bag contains 3 string(s), as follows:
B A C
Adding D to the Tail of the bag:
The bag contains 4 string(s), as follows:
B A C D
Removing an entry from the head:
The bag contains 3 string(s), as follows:
A C D
Removing an entry from the Tail:
The bag contains 2 string(s), as follows:
A C
*/
Homework Answers
Code
BagInterface.java
/**
An interface that describes the operations of a bag of
objects.
*/
public interface BagInterface<T>
{
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in the bag.
*/
public int getCurrentSize();
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in the
bag.
Note: If the bag is empty, the returned array is empty. */
public T[] toArray();
/** Adds a new entry to the head of this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not.
*/
public boolean addToHead(T newEntry);
/** Adds a new entry to the tail of this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not.
*/
public boolean addToTail(T newEntry);
/** Removes one unspecified entry from the head of this bag, if
possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T removeHead();
/** Removes one entry from the tail of this bag, if
possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T removeTail();
} // end BagInterface
LinkedBag.java
/** A class of bags whose entries are stored in a chain of
linked nodes. The
bag is never full. */
public class LinkedBag<T> implements
BagInterface<T>
{
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag()
{
firstNode=null;
numberOfEntries=0;
} // end default constructor
/** Adds a new entry to the head of this bag.
@param newEntry The object to be added as a new entry.
@return
True, as adding a new entry should always be successful. */
public boolean addToHead(T newEntry) // OutOfMemoryError
possible
{
Node nptr = new Node(newEntry, null);
if(firstNode == null)
{
firstNode = nptr;
}
else
{
nptr.setNext(firstNode);
firstNode = nptr;
}
numberOfEntries++;
return true;
} // end addToHead
/** Adds a new entry to the tail of
this bag. @param newEntry The object to be added as a new entry.
@return
True, as adding a new entry should always be successful. */
public boolean addToTail(T newEntry) // OutOfMemoryError
possible
{
Node nptr = new Node(newEntry, null);
if(firstNode==null)
{
firstNode=nptr;
}
Node head=firstNode;
while(head.next!=null)
{
head=head.getNext();
}
head.next=nptr;
numberOfEntries++;
return true;
}// end addToTail
/** Removes the first entry from this
bag, if possible. @return Either the removed entry, if the removal
was
successful, or null if not. */
public T removeHead()
{
if(firstNode!=null)
{
numberOfEntries--;
T firstElement =(T) firstNode.getItem();// removes and returns the
first element
firstNode = firstNode.getNext();
return firstElement ;
}
return null;
} // end removeHead
/** Removes the last entry from this
bag, if possible. @return Either the removed entry, if the removal
was
successful, or null if not. */
public T removeTail()
{
if(firstNode==null)
return null;
Node s = firstNode;
Node t = firstNode;
while (s.next!=null)
{
t = s;
s = s.next;
}
t.next=null;
numberOfEntries--;
return (T) t.getItem();
} // end removeHead
/** Retrieves all entries that are
in this bag. @return A newly allocated array of all the entries in
the
bag. */
public T[] toArray()
{
T[]arr=(T[])new Object[numberOfEntries];
Node s = firstNode;
int i=0;
while (s!=null)
{
arr[i]=(T) s.getItem();
i++;
s=s.next;
}
return arr;
} // end toArray
/** Gets the number of entries currently in this bag.
@return The integer number of entries currently in the bag.
*/
public int getCurrentSize()
{
return numberOfEntries;
} // endgetCurrentSize // A class of nodes for a chain of linked
nodes.
private class Node <T>
{
private T item; // reference to the element stored at this
node
private Node<T> next; // reference to the subsequent node in
the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param n reference to a node that should follow the new
node
*/
public Node(T e, Node<T> n)
{
item = e;
next = n;
}
public Node(T e)
{
item = e;
next = null;
}
// Accessor methods
public T getItem() { return item; }
public Node<T> getNext() { return next; }
// Modifier methods
public void setNext(Node<T> n) { next = n; }
}// end Node
} // end LinkedBag
LinkedBagTester.java
/**
A demonstration of the class LinkedBag.
*/
public class LinkedBagTester
{
public static void main(String[] args)
{
BagInterface<String> aBag = new LinkedBag<>();
// Adding strings to the head of bag
String contentsOfBag = "A";
testAddToHead(aBag, contentsOfBag);
String contentsOfBag1 = "B";
testAddToHead(aBag, contentsOfBag1);
// Adding strings to the tail of bag
String contentsOfBag3 = "C";
testAddToTail(aBag, contentsOfBag3);
String contentsOfBag4 = "D";
testAddToTail(aBag, contentsOfBag4);
// Removing an entry from the head
testRemoveHead(aBag);
// Removing an entry from the tail
testRemoveTail(aBag);
} // end main
// Tests the method addToHead.
private static void testAddToHead(BagInterface<String> aBag,
String content)
{
System.out.print("Adding " + content + " to the Head of the bag:
");
aBag.addToHead(content);
System.out.println();
displayBag(aBag);
} // end testAdd
// Tests the method addToTail.
private static void testAddToTail(BagInterface<String> aBag,
String content)
{
System.out.print("Adding " + content + " to the Tail of the bag:
");
aBag.addToTail(content);
System.out.println();
displayBag(aBag);
} // end testAdd
// Tests the remove methods from the Head.
private static void testRemoveHead(BagInterface<String>
aBag)
{
System.out.print("Removing an entry from the head: ");
aBag.removeHead();
System.out.println();
displayBag(aBag);
} // end testRemove
// Tests the remove methods from the Tail.
private static void testRemoveTail(BagInterface<String>
aBag)
{
System.out.print("Removing an entry from the Tail: ");
aBag.removeTail();
System.out.println();
displayBag(aBag);
} // end testRemove
// Tests the method toArray while displaying the bag.
private static void displayBag(BagInterface<String>
aBag)
{
System.out.println("The bag contains " + aBag.getCurrentSize()
+
" string(s), as follows:");
Object[] bagArray = aBag.toArray();
for (int index = 0; index < bagArray.length; index++)
{
System.out.print(bagArray[index] + " ");
} // end for
System.out.println();
} // end displayBag
} // end Project1
output
If you have any query regarding the code please ask me in the
comment i am here for help you. Please do not direct thumbs down
just ask if you have any query. And if you like my work then please
appreciates with up vote. Thank You.
Add Answer to:
In this lab, we will implement the Linked Bag. The bag will
contain a sequence of...
Write a complete bag class implementation using linked implementation. The linked bag class name must be...
Write a complete bag class implementation using linked implementation. The linked bag class name must be LinkedBag and name your test program as LinkedBagDemo. Your test program should include following test conditions: 1. Get the number of items currently in the bag 2. See whether the bag is full 3. See whether the bag is empty 4. Add a given object to the bag 5. Remove an unspecified (not random) object from the bag 6. Remove an occurrence of a...
import java.util.*; /** * A class that implements the ADT set by using a linked bag....
import java.util.*; /** * A class that implements the ADT set by using a linked bag. * The set is never full. * * */ public class LinkedSetWithLinkedBag> implements SetInterface { private LinkedBag setOfEntries; /** * Creates a set from a new, empty linked bag. */ public LinkedSetWithLinkedBag() { //TODO Project1 } // end default constructor public boolean add(T newEntry) { //TODO Project1 // new node is at beginning of chain if(this.setOfEntries.isEmpty()) { if (!this.setOfEntries.contains(newEntry)) this.setOfEntries.add(newEntry); } return true; //...
Create a java class that implements BagInterface using singly linked data. Name this new class LinkedBag....
Create a java class that implements BagInterface using singly linked data. Name this new class LinkedBag. Be sure to include a default constructor to initialize the private members of the class. Test that your code works properly. BagInterface includes the methods: public int getCurrentSize(); public boolean isEmpty(); public boolean add(T newEntry); public T remove(); public boolean remove(T anEntry); public void clear(); public int getFrequencyOf(T anEntry); public boolean contains(T anEntry); public T[] toArray();
Java Write an intersection method for the ResizableArrayBag class. The intersection of two bags is the...
Java Write an intersection method for the ResizableArrayBag class. The intersection of two bags is the overlapping content of the bags. Intersections are explained in more detail in Chapter 1, #6. An intersecion might contain duplicates. The method should not alter either bag. The current bag and the bag sent in as a parameter should be the same when the method ends. The method header is: public BagInterface<T> intersection(ResizableArrayBag <T> anotherBag) Example: bag1 contains (1, 2, 2, 3) bag2 contains...
This is a c++ class utilizing class templates and linked lists and Nodes. I need to...
This is a c++ class utilizing class templates and linked lists and Nodes. I need to implement the following member function(s) to LinkedBag.cpp. Node.hpp/cpp should be fine but if you feel like there needs to be a change for compilation or testing, feel free to do so but make sure to comment on why it was done. In this case, I need to join the original items with the user items(a_bag). So if the original has {1,2,3} and a_bag has...
C++ Error. I'm having trouble with a pointer. I keep getting the error "Thread 1: EXC_BAD_ACCESS...
C++ Error. I'm having trouble with a pointer. I keep getting the
error "Thread 1: EXC_BAD_ACCESS (code=1, address=0x18)"
The objective of the assignment is to revise the public method
add in class template LinkedBag so that the new
node is inserted at the end of the linked chain instead of at the
beginning.
This is the code I have:
linkedBag-driver.cpp
BagInterface.hpp
LinkedBag.hpp
Node.hpp
int main) LinkedBag<string> bag; cout << "Testing array-based Set:" << endl; cout << "The initial bag is...
In java Write a method public void printReverse() that prints the elements of a doubly linked...
In java Write a method public void printReverse() that prints the elements of a doubly linked list in reverse. Write a method public void delete5FromTheEnd() which deletes the 5th element from end of the list. Note that if you reach the end then you have to reverse the direction of counting. In the main() method of the test class, create a randomly generated Doubly-Linked list of 10 Integers. Next, call the delete5FromTheEnd() method and print the lists iteratively until the...
In java Write a method public void printReverse() that prints the elements of a doubly linked...
In java Write a method public void printReverse() that prints the elements of a doubly linked list in reverse. Write a method public void delete5FromTheEnd() which deletes the 5th element from end of the list. Note that if you reach the end then you have to reverse the direction of counting. In the main() method of the test class, create a randomly generated Doubly-Linked list of 10 Integers. Next, call the delete5FromTheEnd() method and print the lists iteratively until the...
Suppose that you have several numbered billiard balls on a pool table. The smallest possible number...
Suppose that you have several numbered billiard balls on a pool table. The smallest possible number on the ball is “1”. At each step, you remove a billiard ball from the table. If the ball removed is numbered n, you replace it with n balls randomly numbered less than n. For example, if you remove the “5” ball, you replace it with balls numbered “2”, “1”, “1”, “4”, and “3”, where numbers 2, 1, 1, 4, and 3 were randomly...
Problem 3 (List Implementation) (35 points): Write a method in the DoublyLList class that deletes the...
Problem 3 (List Implementation) (35 points): Write a method in the DoublyLList class that deletes the first item containing a given value from a doubly linked list. The header of the method is as follows: public boolean removeValue(T aValue) where T is the general type of the objects in the list and the methods returns true if such an item is found and deleted. Include testing of the method in a main method of the DoublyLList class. ------------------------------------------------------------------------------------- /** A...
C++ Error. I'm having trouble with a pointer. I keep getting the
error "Thread 1: EXC_BAD_ACCESS (code=1, address=0x18)"
The objective of the assignment is to revise the public method
add in class template LinkedBag so that the new
node is inserted at the end of the linked chain instead of at the
beginning.
This is the code I have:
linkedBag-driver.cpp
BagInterface.hpp
LinkedBag.hpp
Node.hpp
int main) LinkedBag<string> bag; cout << "Testing array-based Set:" << endl; cout << "The initial bag is...
Most questions answered within 3 hours.
-
With the rise of social media and digital platforms, some say
"Print is dead". So, what...
asked 1 minute ago -
Python Code Question# 1
General Instructions
Create a class called LawnService that takes in the length...
asked 6 minutes ago -
Use the work-energy theorem to find the force required to
accelerate an electron (m=9.11 * 10^-31...
asked 7 minutes ago -
A person throws a 1 kg ball at a wall with a speed of 30.0 m/s....
asked 24 minutes ago -
Given an n-element unsorted array A of n integers and an integer
k, describe and implement...
asked 23 minutes ago -
Using Classes/Objects
Part-1
Create 3 frame/label objects
Place 2 objects side-by-side on top of the screen...
asked 24 minutes ago -
The maximum speed of the pendulum bob in a grandfather clock is
0.60 m/s .
1.If...
asked 31 minutes ago -
Consider the market for education. The marginal social cost of
education (MSC) and the private benefit...
asked 34 minutes ago -
Name the 3 common law duties of corporate directors
AND provide a brief explanation of what...
asked 36 minutes ago -
Listed below are pulse rates (beats per minute) of females
selected in study of body data...
asked 39 minutes ago -
A large rough ramp is inclined φ=35 degrees above the
horizontal. A block of mass m...
asked 41 minutes ago -
According to survey data, the distribution of arm spans for
males is approximately Normal with a...
asked 59 minutes ago