Please do CardLinkedList
Fall 2020 Version CS145 – PROGRAMMING ASSIGNMENT #5 PART B CARD LINKED LIST OVERVIEW This program primarily focuses on the implementation of a LinkedList version of the CardList that you did in part 1. INSTRUCTIONS Your deliverable will be to turn in four files. The files will be named Card.java, PremiumCard.java, CardArrayList.java and finally CardLinkedList.java. For this assignment, any use of a data control structure other than an Arrary, String or LinkedList Node will result in no credit. I am aware that this assignment could be done quite simply by the implementation of an existing structure, the point of the assignment is to do it without the standard implementation to get a feel for how they work “under the hood”. Also as this is part B of the assignment, you really should only have to create new one file, the other three files should be copied over from the first part. COLLECTABLE CARD While the primary goal of this assignment will be the implementation and use of a custom LinkedList. The particular implementation we will use will focus on the idea of a simple collectable card game. We will be using the same Card and PremiumCard classes that we used for the first part. So refer to your notes there on their implementation. PROGRAM DESCRIPTION Fall 2020 Version In this assignment you will construct a LinkedList that can manage a set of Cards which includes both normal and premium cards. You will implement the various methods that are required in order to make the LinkedList function. A sample program will be provided for you to test with, but you may want to alter it to check different functionality of your LList. YOUR INSTRUCTIONS You will write the following classes, implementing the necessary methods as appropriate. NECESSARY METHODS – CARD CLASS The Card class will be exactly the same as in part A, so check your notes there for the implementation. NECESSARY METHODS – PREMIUM CARD CLASS The PremiumCard class will exactly the same as in part A, so check your requirements there. NECESSARY METHODS – CARDLINKEDLIST CLASS The CardLinkedList is the primary focus of this assignment. In it you will maintain a list of cards, allowing for all the methods listed below to manage a list of cards. The basic idea of the CardLinkedList will be to keep track of an internal linked list of nodes containing cards as the data type. Should the user try to add a value to the List, then you will need to add new nodes to the list in the appropriate place, maintaining the structure of the list and the size of the list at all times. However, we want to be able to change the type of list in the future, so your CardLinkedList will need to implement the CardList interface in order to work. So while the CardList interface is provided for you, you will need to make sure that your program properly implements it. PUBLIC CARDLINKEDLIST () In the CardLinkedList () constructor should create an initial null pointing head pointer. Fall 2020 Version PUBLIC STRING TOSTRING () The toString() method should print the current values of the arraylist being stored. It should surround the entire arraylist inside [0: :size] with commas between the values. A sample output might look like. [0: [2/3:27],[5/4:38],[4/10:43],{{10/10:55}},[3/4:25],{{8/8:49}} :6] Note the 6 to show the current size. If the array is empty it should print out: [0: :0] PUBLIC INT SIZE () In the size() method, you should return the current number of elements currently being stored in the List. PUBLIC VOID ADD (CARD X) In the add() method, you should add the card provided to the end of the list.. PUBLIC CARD REMOVE () In the remove() method, you should remove and return the last element from the list. Make sure to return the Card as you exit however so it can be used by the internal program. If the list is empty, do not throw an error, return null. PUBLIC CARD GET (INT X) In the get(int x) method, you should return the card located in the array at the x location. This method does not delete the element; it just returns the current value. If x is outside the bounds of the array, throw an appropriate exception. PUBLIC INT INDEXOF (CARD X) In the indexOf() method, you should return the location of the first card that is “equal” to the card that is provided. If it isn’t found, return -1. Note that the card found may not match the card given precisely due to the unusual comparison of cards. Fall 2020 Version PUBLIC VOID ADD (INT L, CARD X) In the add(location,x) method, you should add the card(x) provided to the array list in location x. However because the location is inside the array, you will need to move everything after the location over one spot. So you will need to move everything to make room, then add x into location. Make sure that x is inside the current array OR at the end, do not extend the array more than one value. Make sure to alter the size counter as appropriate. If x is outside the bounds of the array plus one, throw an appropriate exception. PUBLIC CARD REMOVE (INT J) In the remove(int j) method, you should remove the element from the array list in location j and then return it. However in this method, the item may be in the middle of the array, so you will need to store the item, then move everything after the item to the left one spot, then adjust the size counter. If j is outside the bounds of the array in use, throw an appropriate exception. PUBLIC VOID SORT () The sort() method should simply sort the array from smallest to largest. However I want you to implement your own version of the merge sort. This is actually easier with Linked Lists, since pulling from the front is easier. Think about the following pseudo-Code when trying to implement it. • Sort o If the List is size 1 or less, be done. o Make two empty CardLinkedLists (left/right) ▪ Note, use YOUR linked list • CardLinkedList left; • CardLinkedList right. o Find the size of ½ the input list current list as an int. o Use a for loop to fill the left with ½ the data, while removing the data from the input list. o Use a while loop to fill the right with the remainder of the input list until it is empty. o Sort the left o Sort the right. o Merge left + right into the original list. • Merge o While (size of left) + (size of right) > 0 ▪ If the left is empty remove from right and add to main list. ▪ If the right is empty remove from the left and add to main list ▪ If the item in the front of left is smaller than the item in front of right, add from left ▪ If none of the above, add from right. Note that unlike the array version, you will destroy the original list when splitting the original list into left and right, but rebuild it in merge. Fall 2020 Version PUBLIC VOID SHUFFLE() The shuffle() method should shuffle the array into a non-ordered arrangement. One way of doing this is picking two random numbers within the size of the list, and then swapping those two values. Then repeat this process a bunch of times. (For example five times the number of elements in the list). PRIVATE VOID SWAP(INT A, INT B) A good idea for your class is to create a private swap(a,b) method that will swap two cards around as necessary. Helpful for methods above (shuffle). Note that this method used ints as inputs. So you might just find a pointer to the a'th element, a pointer to the b'th element and then move the DATA from a into b and b into a. Don't try to rearrange the nodes. Just move the data. PUBLIC VOID CLEAR() The clear() method should reset your size and array back to an initial state, basically deleting the entire List. NOTES Chapter 16 contains a number of ideas on how to implement an LinkedList of numbers, so do not be afraid to consult the chapter for hints/ideas. The testing program is divided up into stages. Comment out the stages that you haven’t finished and work on things step by step. STYLE GUIDELINES AND GRADING: Part of your grade will come from appropriately utilizing object methods. Your class may have other methods besides those specified, but any other methods you add should be private. You should follow good general style guidelines such as: making fields private and avoiding unnecessary fields; declaring collection variables using interface types; appropriately using control structures like loops and if/else; properly using indentation, good variable names and types; and not having any lines of code longer than 100 characters. Comment your code descriptively in your own words at the top of your class, each method, and on complex sections of your code. Comments should explain each method's behavior, parameters, return, and exceptions. Spring 2021 Version Ver 3.1 CS145 – PROGRAMMING ASSIGNMENT CARD ARRAY LIST OVERVIEW This program primarily focuses on the implementation of a ArrayList type interface and the necessary methods to implement the ArrayList. It also includes polymorphism and class comparison. INSTRUCTIONS Your deliverable will be to turn in three files. The files will be named Card.java, PremiumCard.java and the last file will be called CardArrayList.java. For this assignment, any use of a data control structure other than a simple Arrary or String will result in no credit. I am aware that this assignment could be