Linked Lists 1 Setup 1. Begin by downloading the CIT594-linkedlists.zip file from Canvas. This contains the unimplemented methods for the code that you will write in this assignment. CIT 5940

Module 2 Programming Assignment 2. Compile this code before making any changes. This will ensure your local environment is configured correctly. 3. Review the currently implementation. You'll want to understand the various parts of the code and how they work together before making changes! 2 Requirements 2.1 Structure and Compiling 1. You MUST use a Java Development Kit (JDK) version of 17 or higher. 2. You MAY use a JDK version higher than 17, but you MUST set the Java language level to 17 for compatibility with Codio. 3. You MUST NOT change any of method signatures for any of the provided methods. This includes the parameter lists, names, and return value types, etc. 4. You MUST leave the MyLinkedList and MyRawLinkedList classes in the default pack- age. 5. You MUST NOT create additional . java files for your solution. 6. You SHOULD create JUnit tests to help validate your code. These tests SHOULD NOT be a part of your solution. The starter code includes a partial JUnit test file as a refresher. We do expect you to test your code thoroughly with additional JUnit tests. 7. You MUST follow our directives in the starter code comments. This means if we ask you to not change a variable's value, you MUST NOT change that variable's value. 8. You MAY create additional helper functions, as long as they meet the other requirements of the assignment (e.g. doesn't crash with invalid inputs, etc.). 9. You MUST fill out the required Academic Integrity signature in the comment block at the top of your submission file. Functionality Specifications 2.2.1 General Requirements 1. Your method MUST NOT crash if a user enters an invalid input. Remember you do not have control over what a user inputs as arguments. For example, all methods should handle null inputs gracefully or as specified. 4 Linked Lists 2. You MUST NOT overload any of the provided methods. 3. You MUST NOT use arrays anywhere in your solution. 4. You MUST NOT have any import statements in your solution. This implies that you MUST NOT use any other classes or utility functions to manipulate lists. 5. You MUST NOT use the provided implementations of get, contains, OR size in your solution. These are for our unit testing purposes only. CIT 5940 Module 2 Programming Assignment 6. You MAY use methods of the elements, for example equals or compare To from java.lang. String. 7. You MUST NOT throw any exceptions, either deliberately or by failing to handle them, unless otherwise specified in these instructions 8. You MAY create your own helper methods. 2.2.2 Raw Linked List with Static Methods This first part is designed to help you learn the core behaviour of singly linked lists. It is NOT written in an object-oriented style. So you won't be able to instantiate a new linked list like this: /// not valid when using static methods! MyRawLinkedList myRawList new MyRawLinkedList (); = = Instead, you will create individual Nodes as follows: Node list0 Node list1 Node list 2 null; // the empty list, list- new Node ("b", list0); // listl new Node ("a", listl); // list2 // this is valid! Node list 3 new Node (null, list2); // list3 = = 5 [ = "I "b ] Note specifically that list2 "contains" listl, which in turn "contains" list 0. Be careful to not mix up a null list (representing an empty list) with a linked list containing a single element with value null. The following example is valid and MUST be handled appropri- ately: [ "a "b" ] [ null, "a", "b" ] Additionally, you must follow these requirements for all methods in this section: 1. You MUST NOT reference this any where in your code. This is because all the methods are static. 2. Each method MUST take at least a Node as an argument. This represents the head of some linked list. 3. You MUST consider a null Node argument as a linked list containing no Nodes (that is, the empty list). Linked Lists CIT 5940 Module 2 Programming Assignment 4. The end of any linked list MUST have a final Node containing the value null. This signifies the end of the linked list. The empty list is the ONLY exception. 5. You MUST handle both of the following scenarios for each method: (a) The Node is the empty list (i.e. null) (b) The Node is a non-empty list 6. You MUST NOT create new instances of Nodes. That is, you should not have new Node (...) in your solution 7. You MAY create temporary pointers to Nodes within the list 8. You MUST implement the following methods according to their specific specifications 2.2.2.1 reverse (Node) You MUST implement the reverse (Node) method as follows: 1. it MUST take the following parameters: (a) Node head: the head of a linked list 2. it MUST reverse the order of the original list 3. it MUST return the Node representing the head of the reversed list 4. it MUST NOT modify the value field. That is, you MUST NOT simply reverse the values of each Node 5. As an example, assume the list with head Node contains the following: DOG BANANA → CAT →→ BEAR Calling reverse (head) should return this reversed list: BEARCAT → BANANA → DOG 2.2.2.2 removeMaximumValues (Node, int) You MUST implement the removeMaximumValues (Node, it) method as follows: 1. it MUST take the following parameters: (a) Node head: the head of a linked list (b) int N: the number largest values to remove 2. it MUST use the compareTo method to determine which value is the largest. 6 Linked Lists 3. it MUST remove ALL nodes containing each of the N largest values. If the largest value appears more than once in the list, this method MUST remove all such Nodes. CIT 5940 Module 2 Programming Assignment 4. the MUST return the Node representing the head of the linked list with the required elements removed 5. if N is either zero or negative, then this method MUST return the original list unmodified 6. it MUST NOT change the order of the unremoved Nodes 7. it MUST return the empty list from the empty list, for any value of N 8. it MUST gracefully handle scenarios where the original head Node was removed 9. it MUST gracefully handle scenarios where all Nodes were removed 10. it MUST gracefully handle scenarios you try to remove more Nodes than the list contains 11. As an extended example, assume the list with head Node called head contains the following: DOG GORILLA → BANANA → CAT → GORILLA → BEAR Calling removeMaximumValues (head, 1) would remove all instances of the largest value, which is GORILLA, and the returned linked list would be: DOG BANANA → CAT → BEAR However, given that same original linked list, removeMaximumValues (head, 2) would remove the two largest values, which are GORILLA and DOG, so the linked list would be: BANANA →→ CAT BEAR Finally, consider this second list: KANGAROO → PLATYPUS → AARDVARK → KANGAROO → DONKEY → COYOTE Calling removeMaximumValues (head, 2), it would remove all instances of the largest value PLATYPUS) and all instances of the second-largest value KANGAROO. The returned list in this scenario would be: AARDVARK → DONKEY → COYOTE 2.2.2.3 contains Subsequence (Node, Node) You MUST implement the contains Subsequence (Node, Node) method as follows: 1. it MUST take the following parameters: (a) Node head: the head of a linked list 7 Linked Lists CIT 5940 Module 2 Programming Assignment (b) Node other: the head of another linked list 2. it MUST return true if head contains a subsequence of values that matches the list in other. A valid subsequence is defined as follows: (a) the subsequence can be derived by removing zero or more elements from the original sequence (b) the relative order of elements remains unchanged 3. it MUST return false otherwise 4. it MUST compare ONLY the values in the lists. You MUST NOT check if the Node itself matches 5. it MUST consider the empty sequence as a valid subsequence for all possible sequences 6. it MUST handle scenarios in which either or both list contain Nodes that contain null values. 7. As an example, consider the original sequence [A, B, C, D] Valid subsequences are [ ]; [A]; [A, B]; [B, D]; [A, B, D] [B, A] is invalid because the order changed [A, B, C, D, E] is invalid because E does not appear in the original