Question

Lab 02, Data Abstractions and Structures, CSE 274, Fall 2019 Linked Bag In this lab, we...

Lab 02, Data Abstractions and Structures, CSE 274, Fall 2019 Linked Bag
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 the next Node. The constructor of Node class receives an integer and assigns it to the data field. It also has a default constructor.
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:
1. public LinkedBag() The default constructor of class LinkedBag.
2. public int getCurrentSize() Gets the current number of entries in this bag.
3. public T[] toArray() Retrieves all entries that are in this bag.
4. public boolean addToHead(T newEntry) Adds the specified new entry to the start of the linked bag.
5. public boolean addToTail(T newEntry) Adds the specified new entry to the end of the linked bag.
6. public T removeHead() Removes and returns the first item from the bag. If the bag has no nodes, returns null.
7. public T removeTail() Removes and returns the last item from the bag.
Implement all the methods in LinkedBag class.
Grading Rubric: Each method is worth 10 points. Total 100 points.
LinkedBag() 5 getCurrentSize() 5 toArray() 20 addToHead(T newEntry) 10 addToTailHead(T newEntry) 20 removeHead() 10 removeTail() 30
Data Next Node
Before getting started: ● Create a new project named Lab2LinkedBag ● Now download the LinkedBagTester class and addi t t o your project. Run a nd test your code. You will have the following output:
======================================== 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: 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
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

/**
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
   {

  
  
   } // 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()
   {

       @SuppressWarnings("unchecked")
               T[] result = (T[])new Object[numberOfEntries];
               // Unchecked cast
               int index = 0;
               Node currentNode = firstNode;
               while((index < numberOfEntries) && (currentNode != null))
               {
                  
               }
;
              
          
  
  
  
  
  
  
  
  
   } // 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;
  
  
   } // end getCurrentSize


   // A class of nodes for a chain of linked nodes.
   private class Node
   {
      
  
      
       private T data;
       // Entry in bag
       private Node next;
       // Link to next node
       private Node(T dataPortion)
       {
       this(dataPortion, null);
       }
       // end constructor
       private Node(T dataPortion, Node nextNode)
       {
       data = dataPortion;
       next = nextNode;

      
   } // end Node

} // end LinkedBag
}

Homework Answers

Answer #1

// LinkedBag.java

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 node = new Node(newEntry);

                // check if bag is empty

                if(firstNode == null)

                       firstNode = node; // set node as firstnode

                else // non-empty bag

                {

                       // make the new node first node

                       node.next = firstNode;

                       firstNode = node;

                }

                numberOfEntries++; // increment the number of entries

                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 node = new Node(newEntry);

                if(firstNode == null) // if empty bag

                       firstNode = node; // set node as firstnode

                else // if non-empty bag

                {

                       Node temp = firstNode;

                       // get the last node

                       while(temp.next != null)

                              temp = temp.next;

                       temp.next = node; // make last node point to the new node

                }

                numberOfEntries++; // increment the number of entries

                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) // empty bag

                       return null;

                else

                {                  

                       T item = firstNode.data; // get the data of firstnode

                       firstNode = firstNode.next; // remove the firstnode

                       numberOfEntries--; // decrement the number of entries

                       return item; // return the item at firstnode

                }

          } // 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) // empty bag

                       return null;

                else

                {

                       Node temp = firstNode;

                       Node prev = null;

                       // loop to get the last node

                       while(temp.next != null)

                       {

                              prev = temp;

                              temp = temp.next;

                       }

                      

                       T item = temp.data; // get the item at last node

                       if(prev == null) // check if bag contains only one node

                       {

                              firstNode = null; // make the bag empty

                       }else

                              prev.next = null; // remove the last node

                       numberOfEntries--; // decrement the number of entries

                       return item; //return the last item

                }

          } // 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()

   {

       @SuppressWarnings("unchecked")

       T[] result = (T[])new Object[numberOfEntries];

       // Unchecked cast

       int index = 0;

       Node currentNode = firstNode;

       // loop to insert the items of the bag in the array

       while((index < numberOfEntries) && (currentNode != null))

       {

          result[index] = currentNode.data;

          index++;

          currentNode = currentNode.next;

       }

       return result;

     } // 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;

      

       } // end getCurrentSize

      

       // A class of nodes for a chain of linked nodes.

          private class Node

          {

                private T data;

              // Entry in bag

              private Node next;

              // Link to next node

              private Node(T dataPortion)

              {

                 this(dataPortion, null);

              }

              // end constructor

              private Node(T dataPortion, Node nextNode)

              {

                    data = dataPortion;

                    next = nextNode;

              }

            

          } // end Node

         

}//end LinkedBag

//end of LinkedBag.java

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Task 1: You will modify the add method in the LinkedBag class.Add a second parameter to...
Task 1: You will modify the add method in the LinkedBag class.Add a second parameter to the method header that will be a boolean variable: public boolean add(T newEntry, boolean sorted) The modification to the add method will makeit possible toadd new entriesto the beginning of the list, as it does now, but also to add new entries in sorted order. The sorted parameter if set to false will result in the existing functionality being executed (it will add the...
this is the book name. Data Structures and Abstractions with Java 1) Description: The sample programs...
this is the book name. Data Structures and Abstractions with Java 1) Description: The sample programs in Chapter 1 of your textbook are not complete. They are used for illustration purpose only. The implementation of Listing 1-1 on page 39 is explained in Chapter 2. And, in order to see the result of using it, we will need the following set of files: i. BagInteface.java – the specification only. ii. ArrayBag.java – the implementation of BagInerface.java. iii. ArrayBagDemo.java – a...
Write a class called Item that has a string field called name and a double field...
Write a class called Item that has a string field called name and a double field called price and an integer field called quantity. In main, create a bag of type Item and place several item objects in the bag. Then in main calculate the total price of items purchased. You may remove each item and add the price to a total variable in a loop. The loop should end when the bag is empty. Using bag algorithms public final...
In java just need work in the billards class it is in bold everything else is...
In java just need work in the billards class it is in bold everything else is done just the sections marked TODO 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,...
(Please use Java Eclipse) QUESTION 1: For the question below, assume the following implementation of LinkedQueue:...
(Please use Java Eclipse) QUESTION 1: For the question below, assume the following implementation of LinkedQueue: public static final class LinkedQueue<T> implements QueueInterface<T> {     private Node<T> firstNode;     private Node<T> lastNode;     public LinkedQueue() {         firstNode = null;         lastNode = null;     }     @Override     public T getFront() {         if (isEmpty()) {             return null;         }         return firstNode.getData();     }     @Override     public boolean isEmpty() {         return firstNode == null;    ...
1. Design and implement a CircularLinkedList, which is essentially a linked list in which the next...
1. Design and implement a CircularLinkedList, which is essentially a linked list in which the next reference of the tail node is set to refer back to the head of the list (rather than null) . Start from the SinglyLinkedList provided in the Lecture (not the built-in Java LinkedList class). 2. Starting from  SinglyLinkedList you will need to modify or complete methods: first(), last(), addFirst(), addLast(), removeFirst(), toString(), and also create a new rotate() method which will move the tail to...
Q1; Write a method in class SLL called public SLL reverse() that produces a new linked...
Q1; Write a method in class SLL called public SLL reverse() that produces a new linked list with the contents of the original list reversed. Make sure not to use any methods like addToHead() or addToTail(). In addition, consider any special cases that might arise. What is the big-O complexity of your method in terms of the list size n Supplementary Exercise for Programming (Coding) [Singly Linked Lists] Download and unpack (unzip) the file SinglyLinkedList.rar. Compile and execute the class...
8.19 LAB: Grocery shopping list (linked list: inserting at the end of a list) PLEASE ANSWER...
8.19 LAB: Grocery shopping list (linked list: inserting at the end of a list) PLEASE ANSWER IN C++ Given main(), define an InsertAtEnd() member function in the ItemNode class that adds an element to the end of a linked list. DO NOT print the dummy head node. Ex. if the input is: 4 Kale Lettuce Carrots Peanuts where 4 is the number of items to be inserted; Kale, Lettuce, Carrots, Peanuts are the names of the items to be added...
(a)   Write a method in class SLL<T> called public SLL<T> reverse() that produces a new linked...
(a)   Write a method in class SLL<T> called public SLL<T> reverse() that produces a new linked list with the contents of the original list reversed. Make sure not to use any methods like addToHead() or addToTail(). In addition, consider any special cases that might arise. (b)   What is the big-O complexity of your method in terms of the list size n. ****** //************************ SLLNode.java ******************************* //           node in a generic singly linked list class public class SLLNode<T> {     public...
public class LinkedStackOfStrings { private Node first; private class Node { private String item; private Node...
public class LinkedStackOfStrings { private Node first; private class Node { private String item; private Node next; } public boolean isEmpty() { return (first == null); } public void push(String item) { // Insert a new node at the beginning of the list. Node oldFirst = first; first = new Node(); first.item = item; first.next = oldFirst; } public String pop() { // Remove the first node from the list and return item. String item = first.item; first = first.next;...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT