on the instruction you have 4 classes to implement

1. thing class

2. thingnode

3. thinklinkedbag

4.thingbagdriver

each class has methods you have to implement according to the instructions on the pages above you are creating a linked lists from stratch. look closely on the requirements and objectives on the first page and read all the pages.

Objective In this assignment, you are asked to implement a bag collection using a linked list and, in order to focus on the linked list implementation details, we will implement the collection to store only one type of Thing of your choice (i.e., not generic). Important: you cannot use the LinkedList or any such classes from the java library; instead, you have to implement your own linked list as explained below. Requirements In order to complete this project, you need to implement the following classes. The details of each of these classes are explained below Thing: you may use the same Thing you used for the previous assignments. But make sure to look for the requirements below and change your previous implementation as necessary. ThingNode: a linked list node where the data part is of type Thing. ThingLinkedBag: a collection of Things in which the elements are stored in a linked list. ThingLinkedBagDriver: that includes a main method to test the functionality of your collection. class Thing Use the same Thing class that you used in Assignment 3 but make sure all the following requirements are met. Ifthere are mistakes in your implementation, fix them. Your Thing class must have the following: has exactly 3 instance variables such that: o one instance variable must be integer (i.e, int) and this variable will be used to find aggregate information about Things that are stored in a collection class as will be explained later o one instance variable must be String and this variable will be used as a search key. oThe third variable can be either int or String type based on the semantics of your Thing. An implementation of toString method where a Thing is represented in one line. Implement equals methods to test the equality of two things. Implement Comparable interface and include compareTo method. Note 1: do not name your class Thing.java, however, give your class a name that is indicative to the type of elements that you are maintaining. Also, the name of your class should be singular not plural (e.g Car not Cars) because this class is used to represent only one element Note 2: the name of all the other classes must be changed to indicate the type of things you are maintaining. For example, if you chose to implement a collection of cars, then your classes must be named Car, CarNode, CarLinkedBag, and CarLinke dBagDriver. class ThingNode This class represents a node in the linked list. The node class should include the following: two private instance variables: data of type Thing. It is required that the data part to be of a specific Thing type. Do not use a generic node. link of type ThingNode. a constructor that takes two input parameters and use them to initialize the two instance variables. The following instance methods which are the same as in the IntNode class that we discussed in class and also is discussed in the text book (Chapter 4, Section 4.2). You have to change the methods as appropriate to reflect your new type of data. O getData, getLink, setData, setLink, addNodeAfter, removeNodeAfter. The following static methods that are the same as IntNode class. You have to change the methods as appropriate. odisplay, 1ist Position, listLength, and listSearch. class ThingLinkedBag This class is used to manage a collection of things where the things are stored in a linked list (not an array). We discussed how to implement IntLinkedBag in class and this is also discussed in Section 4.4 of the text book. The requirements for this class are as follows: two instance variables: head of type Thing Node: this represent the head of the linked list that stores your collection omanyItems of type int: this represent the size of the linked list. Implement the following instance methods in your collection class. Note that all the method headers below are written in terms of Thing, however, your implementation should replace each Thing with your specific data type. 1. a constructor to create an empty linked list. 2. int size (): returns the number of nodes in the list. void display (): displays the contents of the collection such that each element is 3. displayed on one line. Note that this method displays the list on the screen and does NOT return a String representation of the list. void add (Thing element): a method to add a Thing to the collection void add (int index, Thing element): a method to add an element at a specific index in the collection assuming the head node is at index 1. If the index is greater than the collection length, then the element is added as the last element in the collection. The method does not do anything is index is negative. void addLast (Thing element) : adding an ellement to be the last element in 4. 5. 6. the linked list 7. boolean remove (Thing target): this method removes one occurrence from the target from the list if any. The method returns true if an item is removed and false otherwise. 8. boolean remove (int index) : this method removes the element that is located at position index in the linked list where the head node is at index 1. The method returns true if an item is removed and false if no element is removed because index is negative or beyond the list length. 9. void removeLa st () : this method removes the last node in the linked list. 10. int countRange (Thing start, Thing end): this method counts and returns how many element in the collection falls in the range between start and end inclusive. Note that equality of things are compared using the compare To method. 11. Thing grab (int index): returns the element of the node located at position index in the list or null if index is past the end of the list. Note that this method does not remove the element from the list. 12. int indexor (Thing target): returns the index of the node that contains target assuming that the head node is at index 1. If the target is not found, the method return-1 and if there are more than one occurrence, then the method returns the index of the first occurrence. 13. void set (int index, Thing element): changes the element at position index with the input element. If index is negative or beyond the length of the list, then the method does not do anything 14. boolean replace (Thing oldThing, Thing newThing) : this method takes two Thing inputs, oldThing and newThing. The method then searches the collection for an element that is equal to oldThing. If found, the method replaces (only one occurrence of) oldThing with newThing while maintaining the linked list order (ie, don't delete and then re-insert). On the other hand, if oldThing is not found in the collection, the method does not do anything. The method then returns true or false based on whether a replacement took place or no. 15. int totalValue () : this method returns the sum of all the integer values of all things in the list (remember that it was required that each thing has an integer attribute). 16. ThingNode lessThan (Thing element) : this method takes one Thing as input and returns an output a linked list that includes all elements that are less than or equal to the input element. Note that things are ordered based on the compareTo method 17. ThingNode greaterThan (Thing element): similar to the lessThan method, this method takes one Thing as input and returns an output a linked list that includes all elements that are greater than the input element. Note that things are ordered based on the compareTo method. 18. Thing getMax (): this method returns the maximum Thing in the linked list where things are ordered based on the compareTo method. 19. Thing getMin () : this method returns the minimum Thing in the linked list where things are ordered based on the compareTo method. class ThingLinkedBag Iterator This is an inner class inside the ThinglinkedBag class and it is used to iterate over your linked collection. An implementation of the linked list iterator is discussed in class and can be found in slides# 15 and 16 in Lecture7 -Mar2 and also in Lecture7's code that is posted on D2L. Basically, the header of your class should be as follows: class ThingLinkedBagIterator implements Iterator and add the iterator method that returns an iterator of type ThingLinkedBagI terator. class ThingLinkedBagDriver Write a driver class to test ALL. the methods that you implemented in the ThingNode class and the ThingLinkedBag class. Objective In this assignment, you are asked to implement a bag collection using a linked list and, in order to focus on the linked list implementation details, we will implement the collection to store only one type of Thing of your choice (i.e., not generic). Important: you cannot use the LinkedList or any such classes from the java library; instead, you have to implement your own linked list as explained below. Requirements In order to complete this project, you need to implement the following classes. The details of each of these classes are explained below Thing: you may use the same Thing you used for the previous assignments. But make sure to look for the requirements below and change your previous implementation as necessary. ThingNode: a linked list node where the data part is of type Thing. ThingLinkedBag: a collection of Things in which the elements are stored in a linked list. ThingLinkedBagDriver: that includes a main method to test the functionality of your collection. class Thing Use the same Thing class that you used in Assignment 3 but make sure all the following requirements are met. Ifthere are mistakes in your implementation, fix them. Your Thing class must have the following: has exactly 3 instance variables such that: o one instance variable must be integer (i.e, int) and this variable will be used to find aggregate information about Things that are stored in a collection class as will be explained later o one instance variable must be String and this variable will be used as a search key. oThe third variable can be either int or String type based on the semantics of your Thing. An implementation of toString method where a Thing is represented in one line. Implement equals methods to test the equality of two things. Implement Comparable interface and include compareTo method. Note 1: do not name your class Thing.java, however, give your class a name that is indicative to the type of elements that you are maintaining. Also, the name of your class should be singular not plural (e.g Car not Cars) because this class is used to represent only one element Note 2: the name of all the other classes must be changed to indicate the type of things you are maintaining. For example, if you chose to implement a collection of cars, then your classes must be named Car, CarNode, CarLinkedBag, and CarLinke dBagDriver. class ThingNode This class represents a node in the linked list. The node class should include the following: two private instance variables: data of type Thing. It is required that the data part to be of a specific Thing type. Do not use a generic node. link of type ThingNode. a constructor that takes two input parameters and use them to initialize the two instance variables. The following instance methods which are the same as in the IntNode class that we discussed in class and also is discussed in the text book (Chapter 4, Section 4.2). You have to change the methods as appropriate to reflect your new type of data. O getData, getLink, setData, setLink, addNodeAfter, removeNodeAfter. The following static methods that are the same as IntNode class. You have to change the methods as appropriate. odisplay, 1ist Position, listLength, and listSearch. class ThingLinkedBag This class is used to manage a collection of things where the things are stored in a linked list (not an array). We discussed how to implement IntLinkedBag in class and this is also discussed in Section 4.4 of the text book. The requirements for this class are as follows: two instance variables: head of type Thing Node: this represent the head of the linked list that stores your collection omanyItems of type int: this represent the size of the linked list. Implement the following instance methods in your collection class. Note that all the method headers below are written in terms of Thing, however, your implementation should replace each Thing with your specific data type. 1. a constructor to create an empty linked list. 2. int size (): returns the number of nodes in the list. void display (): displays the contents of the collection such that each element is 3. displayed on one line. Note that this method displays the list on the screen and does NOT return a String representation of the list. void add (Thing element): a method to add a Thing to the collection void add (int index, Thing element): a method to add an element at a specific index in the collection assuming the head node is at index 1. If the index is greater than the collection length, then the element is added as the last element in the collection. The method does not do anything is index is negative. void addLast (Thing element) : adding an ellement to be the last element in 4. 5. 6. the linked list 7. boolean remove (Thing target): this method removes one occurrence from the target from the list if any. The method returns true if an item is removed and false otherwise. 8. boolean remove (int index) : this method removes the element that is located at position index in the linked list where the head node is at index 1. The method returns true if an item is removed and false if no element is removed because index is negative or beyond the list length. 9. void removeLa st () : this method removes the last node in the linked list. 10. int countRange (Thing start, Thing end): this method counts and returns how many element in the collection falls in the range between start and end inclusive. Note that equality of things are compared using the compare To method. 11. Thing grab (int index): returns the element of the node located at position index in the list or null if index is past the end of the list. Note that this method does not remove the element from the list. 12. int indexor (Thing target): returns the index of the node that contains target assuming that the head node is at index 1. If the target is not found, the method return-1 and if there are more than one occurrence, then the method returns the index of the first occurrence. 13. void set (int index, Thing element): changes the element at position index with the input element. If index is negative or beyond the length of the list, then the method does not do anything 14. boolean replace (Thing oldThing, Thing newThing) : this method takes two Thing inputs, oldThing and newThing. The method then searches the collection for an element that is equal to oldThing. If found, the method replaces (only one occurrence of) oldThing with newThing while maintaining the linked list order (ie, don't delete and then re-insert). On the other hand, if oldThing is not found in the collection, the method does not do anything. The method then returns true or false based on whether a replacement took place or no. 15. int totalValue () : this method returns the sum of all the integer values of all things in the list (remember that it was required that each thing has an integer attribute). 16. ThingNode lessThan (Thing element) : this method takes one Thing as input and returns an output a linked list that includes all elements that are less than or equal to the input element. Note that things are ordered based on the compareTo method 17. ThingNode greaterThan (Thing element): similar to the lessThan method, this method takes one Thing as input and returns an output a linked list that includes all elements that are greater than the input element. Note that things are ordered based on the compareTo method. 18. Thing getMax (): this method returns the maximum Thing in the linked list where things are ordered based on the compareTo method. 19. Thing getMin () : this method returns the minimum Thing in the linked list where things are ordered based on the compareTo method. class ThingLinkedBag Iterator This is an inner class inside the ThinglinkedBag class and it is used to iterate over your linked collection. An implementation of the linked list iterator is discussed in class and can be found in slides# 15 and 16 in Lecture7 -Mar2 and also in Lecture7's code that is posted on D2L. Basically, the header of your class should be as follows: class ThingLinkedBagIterator implements Iterator and add the iterator method that returns an iterator of type ThingLinkedBagI terator. class ThingLinkedBagDriver Write a driver class to test ALL. the methods that you implemented in the ThingNode class and the ThingLinkedBag class