In a file named LLBag.java, write a class called LLBag that implements the Bag interface using a linked list instead of an array. You may use a linked list with or without a dummy head node.
Bag interface code:
/*
* Bag.java
*
* Computer Science 112, Boston University
*/
/*
* An interface for a Bag ADT.
*/
public interface Bag {
/*
* adds the specified item to the Bag. Returns true on success
* and false if there is no more room in the Bag.
*/
boolean add(Object item);
/*
* removes one occurrence of the specified item (if any) from the
* Bag. Returns true on success and false if the specified item
* (i.e., an object equal to item) is not in the Bag.
*/
boolean remove(Object item);
/*
* returns true if the specified item is in the Bag, and false
* otherwise.
*/
boolean contains(Object item);
/*
* returns the number of items in the Bag.
*/
int numItems();
/*
* grab - returns a reference to a randomly chosen item in the Bag.
*/
Object grab();
/*
* toArray - return an array containing the current contents of the bag
*/
Object[] toArray();
}
LLBag skeleton:
public class LLBag {
public static void LLBag()
//implement Bag interface using a Linked List
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
//LLBag.java
public class LLBag implements Bag {
// pointer to the head
private Node head;
private int size; // current size
// default constructor
public LLBag() {
head = null;
size = 0;
}
// method to insert an element to the list
public boolean add(Object value) {
// creating a Node object
Node newNode = new Node(value);
Node temp = head;
// adding as the head node if head is null
if (temp == null) {
head = newNode;
} else {
// finding the last node
while (temp.next != null) {
temp = temp.next;
}
// appending to the last node
temp.next = newNode;
}
// updating size
size++;
return true; // always true since linked list's capacity is indefinite
}
// method to check if a value exists on the list
public boolean contains(Object value) {
Node temp = head;
// looping through list
while (temp != null) {
if (temp.data.equals(value)) {
// found
return true;
}
temp = temp.next;
}
// not found
return false;
}
// method to delete an element from list
public boolean remove(Object value) {
if (head != null && head.data.equals(value)) {
// removing head node
head = head.next;
// updating size
size--;
return true;
}
Node temp = head;
// finding the node to delete
while (temp.next != null) {
if (temp.next.data.equals(value)) {
// found, deleting the node
temp.next = temp.next.next;
// updating size
size--;
return true;
}
temp = temp.next;
}
// not found
return false;
}
// returns a String representation of the list
public String toString() {
// returns a String representation of the list
String data = "[";
Node temp = head;
while (temp != null) {
data += temp.data;
temp = temp.next;
if (temp != null) {
data += ", ";
}
}
data += "]";
return data;
}
// returns the number of items
public int numItems() {
return size;
}
// returns a random item from the list
public Object grab() {
if (size == 0) {
return null; // empty
}
// generating a random index
int randIndex = (int) (Math.random() * size);
Node temp = head;
// returning item at position randIndex
for (int i = 0; i < randIndex; i++) {
temp = temp.next;
}
return temp.data;
}
// returns an array containing all items
public Object[] toArray() {
// creating an array
Object array[] = new Object[size];
Node temp = head;
// adding each element one by one to the array
for (int i = 0; i < size; i++) {
array[i] = temp.data;
temp = temp.next;
}
return array;
}
// main method for testing
public static void main(String[] args) {
// creating a Bag and testing some methods
LLBag bag = new LLBag();
bag.add("Oliver");
bag.add("John");
bag.add("Kevin");
System.out.println(bag); // [Oliver, John, Kevin]
System.out.println(bag.contains("Oliver")); // true
System.out.println(bag.contains("Tommy")); // false
System.out.println("Random item: " + bag.grab()); // either
// Oliver/John/Kevin
bag.remove("Oliver"); // Oliver will be removed
System.out.println(bag); // [John, Kevin]
}
}
/**
* class to represent a Node in the list. should be placed within
* LLBag.java
*/
class Node {
Object data;
Node next;
public Node(Object data) {
this.data = data;
}
}
/*OUTPUT*/
[Oliver, John, Kevin]
true
false
Random item: Kevin
[John, Kevin]
In a file named LLBag.java, write a class called LLBag that implements the Bag interface using...
Can you help with the merge method? This method should create and return an ArrayBagcontaining one occurrence of any item that is found in either the called object or the parameter other. For full credit, the resulting bag should not include any duplicates. Give the new ArrayBag a maximum size that is the sum of the two bag’s maximum sizes. import java.util.*; /** * An implementation of a bag data structure using an array. */ public class ArrayBag { /**...
Load to the IDEA the remaining classes from the provided Lab02.zip file. Repeat the previous project inside the ArraySetWithArray class. As shown in the UML diagram below ArraySetWithArray class does not utilize ResizableArrayBag object as its instance variable, it has setOfEntries defined as an array which should be dynamically resized if more room needed (double the size). displaySet method should check if the set is empty and display appropriate message; if the set is not empty should display the number...
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; //...
Part I: Create a doubly linked circular list class named LinkedItemList that implements the following interface: /** * An ordered list of items. */ public interface ItemList<E> { /** * Append an item to the end of the list * * @param item – item to be appended */ public void append(E item); /** * Insert an item at a specified index position * * @param item – item to be...
instructions: Write a non-member method named bagScaler, which removes from a Bag all elements that occur less than N times . The method returns the number of copies removed. For example, if B = {Bob, Joe, Bob, Ned, Bob, Ned, Kim}, then calling bagScaler(B, 3) removes Joe, Ned, and Kim making B = {Bob, Bob, Bob}, and returns 4 because it removed 2 copies of Ned, one of Joe, and one of Kim. Note: There's no iterator, but there is...
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...
Complete an Array-Based implementation of the ADT List including a main method and show that the ADT List works. Draw a class diagram of the ADT List __________________________________________ public interface IntegerListInterface{ public boolean isEmpty(); //Determines whether a list is empty. //Precondition: None. //Postcondition: Returns true if the list is empty, //otherwise returns false. //Throws: None. public int size(); // Determines the length of a list. // Precondition: None. // Postcondition: Returns the number of items in this IntegerList. //Throws: None....
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...
please write code in java, assignment is due soon Thanks. public interface Named The Named interface is a simple interface which applies to anything which has a name. The only thing required is the following method: String name() which returns the name of the instance. public interface MessageSink, It includes: void deliver(Named sender, String message) delivers the specified message from the given sender. public interface Sharable, which is Named, It includes no method. public abstract class GeneralCapability It incudes: The...
Given the Interface Code write a java class that implements this interface and show the working functionality in the main method: public interface CustomList<T> { /** * This method should add a new item into the <code>CustomList</code> and should * return <code>true</code> if it was successfully able to insert an item. * @param item the item to be added to the <code>CustomList</code> * @return <code>true</code> if item was successfully added, <code>false</code> if the item was not successfully added (note: it...