Reimplement the bag class from Figure 4.17 so that the items of the bag are stored with a new technique. Here’s the idea: Each node of the noefw linked list contains two integers. The first integer is called the count, and the second integer is called the data. As an example, if a node has a count of 6 and data of 10, then this means that the bag has six copies of the number 10.

The nodes of the linked list should be kept in order from the smallest data (at the head of the list) to the largest (at the tail of the list). You should never have two different nodes with the same data, and if the count in a node drops to zero (meaning there are no copies of that node’s data), then the node should be removed from the linked list.

The public member functions of your new class should be identical to those in Figure 4.17.

Figure 4.17

Transcribed Image Text:

// FILE: IntLinkedBag.java from the package edu.colorado.collections // Documentation is available in Figure 4.12 on page 216 or from the IntLinkedBag link at // http://www.cs.colorado.edu/-main/docs/. package edu.colorado.collections; import edu.colorado.nodes.IntNode; public class IntLinkedBag implements Cloneable { // INVARIANT for the Bag ADT: // 1. The elements in the Bag are stored in a linked list. // 2. The head reference of the list is in the instance variable head. // 3. The total number of elements in the list is in the instance variable manyNodes. private IntNode head; private int manyNodes; public IntlinkedBag( ) { head = null; manyNodes = 0; public void add(int element) { head = new IntNode (element, head); manyNodes++; } public void addA11 (IntlinkedBag addend) IntNode[ ] copyInfo; if (addend - null) throw new IllegalArgumentException("addend is null."); if (addend.manyNodes > 0) { copyInfo = IntNode.listCopyWithTail(addend.head); copyInfo[1].setLink (head); // Link the tail of the copy to my own head.. head = copyInfo[0]; manyNodes += addend.manyNodes; // and set my own head to the head of the copy.