Part 1: Raw Linked List The goal of part 1 is to understand the core behavior...

Transcribed Image Text:

Part 1: Raw Linked List The goal of part 1 is to understand the core behavior of singly linked lists. Thus, it is not written in an object-oriented style. Note that all of the methods inside MyRawLinked List are declared static, meaning they belong to the class rather than to an instance of the class. Consequently, you cannot reference this inside any of these methods; the list (s) your methods operate on will be passed through the method parameters. Specifically, each method will be passed a reference of type Node representing the head of the linked list, along with any other additional arguments as needed for the method's functionality. It is important here to understand two things about linked lists: . Consider this definition of singly linked list: a singly linked list is either empty (represented by the value null), or it is a non-null instance of type Node containing a value and a reference to a singly linked list. Notice that we referred to the linked list as a component inside its definition? This is known as a recursive data structure, and the reason it is valid is because it has a base case, i.e. empty /null, which terminates the list. As a consequence of the above point, every single node taken in isolation can be thought of as its own unique linked list, since it does indeed meet the above definition. Conceptually, an object of type Node is a linked list. As another consequence of the definition, every time you have a method that receives a linked list as parameter, you need to handle both possible cases of linked list - either a node or the empty list. However, be careful not to confuse a null list (i.e., the empty list) with a non-null Node with its value field set to null! Yet another consequence of this non-00 design is that this manner of list instantiation does not make sense: My Raw LinkedList myList. = new MyRawLinkedList (); All the methods in this class are static, so MyRawLinked List is acting here just as a convenient place to put all of our methods. Remember, a Node is a list, so you create lists like so: Node list 0 null; // the Node list 1 = new Node ("b", Node list 2 = new Node ("a", empty list, listo list0); // list1 listl); // list2 2 - = (1 [b] [a, b] Again, notice that list 2, listi, and list0 are all distinct lists when taken in isolation, but list 2 contains (points to) list1 which contains (points to) list 0. In order for you to get anything out of this assignment, we require that you do not use arrays anywhere in your implementation, and that you do not use other classes or functions to manipulate the lists. Thus you should not have any import statements at the top of MyRaw Linked List java. You may write your own helper methods as long as they have unique names (do not overload the existing method names). You may also use the methods of the elements (for example: equals and compare To from java.lang. String). Additionally, as noted in the comment blocks above them, do not use the provided implementations of get, contains, or size in your implementation of the three methods below. They are there just to allow our unit tests to run; you may of course use them in your own testing. Activity Implement the following static methods in the MyRaw Linked List.java file: Met hod 1: reverse (Node) This method takes as its parameter a linked list, reverses the order of that list, and returns the node at the head of the reversed list. You may store temporary pointers to Nodes within the list (as in Node n head), but do not create any new instances of Node; in other words, the expression new Node (...) should not appear anywhere in your implementation. Also, do not modify the value field inside each Node; your implementation should reverse the direction of the node pointers, not move values around. Met hod 2: removeMaximum Values (Node, int) This method takes as parameters a linked list and an integer N and returns the linked list from which all instances of each of the N largest values in the input linked list have been removed. If the input value N is zero or negative, this method should simply return the list without modification. The other elements in the list should not be modified and their relative order must not be changed. Removing the N maximum values from an empty list should return the empty list for any value of N; an exception should not be thrown in this case, and in general you shouldn't throw exceptions unless we specify that you do so. Because the values are Strings, you will need to use the String class's compare To method to compare 3 the Strings; see the Java API for help with that method. This method performs lexicographic comparison (similar to how dictionaries are sorted), so "b" is larger than "a", and "aa" is larger than "a", etc. Note that compareTo is undefined if its argument is null and will throw an exception in this case. Your implementation should not attempt to handle/catch that exception. We will not pass a list to your method that contains any nodes with null Strings. For instance, if the list contained the following: DOG GORILLA BANANA CAT GORILLA BEAR Then removeMaximumValues (head, 1) would remove all instances of the largest value, which is "GORILLA", and the linked list would then look like this: DOG BANANA CAT BEAR However, given that same linked list, remov eMaximumValues (head, 2) would remove the two largest values, which are "GORILLA" and "DOG", so the linked list would then look like this: BANANA CAT BEAR Keep in mind that if any of the N largest values appear more than once in the linked list, this method should remove all instances, so it may remove more than N elements overall. So, for instance, if we had: KANGAROO PLATYPUS AARDVARK KANGAROO DONKEY COYOTE and called remove Maximum Values (head, 2), it would remove all instances of the largest value ("PLATYPUS") and all instances of the second-largest value ("KANGAROO") and we would then have this: AARDVARK DONKEY COYOTE As with the previous method, you should not create any new instances of Node; the linked list should be mutated in place. However, it's possible that the head of the original list could have been deleted (or even all the elements of the list might have been wiped out), so you need to ensure that you return whatever is left of the list. Met hod 3: cont ainsSubsequ en ce (Node, Node) This method takes as input two lists, head and other, and determines whether the values stored in the list other are a subsequence of the values stored in the list head. A sequence T is a subsequence of Sif T can be derived from S by deleting zero or more values from S without changing the relative ordering of the values. For example, the sequences (the empty sequence), [b]. [a, c], and [a, b, c, d] are all subsequences of [a, b, c, d] (out of a total 16 possible subsequences). But [b, a] would not be a valid subsequence of [a, b, c, d] since ordering must be preserved. Note that the empty sequence is a subsequence of all possible sequences, therefore if other is the empty list, this method should return true. Also note that you should compare only the values stored in the two lists to determine if other is a subsequence of head. The nodes themselves do not need to be shared between the two lists, only the values stored in those nodes. Part 2: Linked List The goal of part 2 is to understand the implementation of a linked list class as an encapsulated, object-oriented dat a structure. The primary functionality of the methods is the same as part 1, but there are some subtle differences. Each method will work with the object's linked list (head field or this.head) instead of a list pointer passed as a parameter. Changes should apply to the state of the MyLinkedList object instead of a returned list. Additionally you must consider and correctly maintain the object state (head, tail, and size). You may copy your implementations from MyRawLinkedList and adjust as needed, or write entirely new implementations. You may use the existing methods in MyLinkedList, but may not use other classes or utility methods to manipulate the list. You may use the elements' methods (examples: equals and compare To). While we are less concerned about efficiency in this assignment, we also strongly suggest (but do not require) that you avoid using the provided get (int) method (i.e. to get an element at a particular index) in your implementation. An elegant implementation of the required methods below can and should be done without calling get (int), as implementations that use this typically run much slower. There is a key difference between MyRawLinked List and MyLinked List in terms of how the notion of a linked list is defined. A valid raw linked list is a Node that is either null (encoding the empty list) or non-null (encoding a non-empty linked list and containing a value and a reference to another raw linked list); and, you instantiate a new raw linked list by creating a new Node. However, you instantiate a MyLinked List via new MyLinkedList, which internally handles the instantiation of the raw nodes whenever you add values to it. Thus a null-valued variable of type MyLinked List is not the same as an empty linked list, which would be an instance of My Linked List with a size field set to 0 and a head field set to mull. Yet, inside of MyLinked List you still treat a null-valued Node as encoding an empty list, just as you did in MyRaw Linked List, but this detail is hidden to the outside world. This is what is meant by "encapsulation" and it's the reason why to some extent you are able (and encouraged) to copy your implementation from MyRawLinked List and have it just work with only a few modifications. Note that once you understand what distinguishes a raw linked list from its 00/encapsulated form, the adjustments required to get your method implementations in part 1 working for part 2 are very minimal and should only take a few minutes. Expect to spend most of your time just thinking about what the differences are. Activity Implement the following methods in the MyLinked List .java file: Met hod 1: reverse Same behavior as part 1, except that updates should be made to the MyLinkedList instance (i.e. this), instead of returning the reversed list. Don't forget to update both the head and tail fields. Met hod 2: removeMaximumValues Same behavior as part 1, except that updates should be made in-place to the instance instead of returning the list. Remember to update all three instance fields (head, tail, and size) as needed. For the same reason you should generally avoid get (int), we also suggest (but do not require), for the sake of efficiency, that you avoid using the provided remove(int) (i.e. remove an element by index) in your implementation of remove Maximum Values (int). A little repetitive code is preferable to code that is orders of magnitude slower. In part 1, the return type was boolean, with 2 possible output values true and false encoding, respectively, "contains subsequence" and "does not contain subsequence". For part 2, notice that we have written the return type as Boolean. Whereas boolean is a primitive type in Java, Boolean is a class that contains a boolean value field. But, being a class, a variable of type Boolean might not be instantiated (i.e. it can be null). We say that these encapsulated types are "nullable", because they can possibly be null, which primitive types cannot. Consequently, a variable of type Boolean has three possible values: true, false, and null. When other is non-null, our contains Subsequence method should behave exactly the same as part 1 in terms of returning only either true or false. Recall that we said above that a variable of type MyLink ed List with value null is not actually a linked list object at all, and is not the same as an empty linked list. Rather, it is the complete absence of a linked list object. The contains Subsequence operation is undefined if it does not have a linked list object to operate on, so when other is null, the method should return null. Returning null to represent an invalid input is one of several programming styles that we will see throughout this semester. Your method should not throw a NullPointerException or any other exception (either on purpose, or because you forgot to check for null). In a future assignment you will see a different style of error handling in which we do want you to throw an exception. Part 1: Raw Linked List The goal of part 1 is to understand the core behavior of singly linked lists. Thus, it is not written in an object-oriented style. Note that all of the methods inside MyRawLinked List are declared static, meaning they belong to the class rather than to an instance of the class. Consequently, you cannot reference this inside any of these methods; the list (s) your methods operate on will be passed through the method parameters. Specifically, each method will be passed a reference of type Node representing the head of the linked list, along with any other additional arguments as needed for the method's functionality. It is important here to understand two things about linked lists: . Consider this definition of singly linked list: a singly linked list is either empty (represented by the value null), or it is a non-null instance of type Node containing a value and a reference to a singly linked list. Notice that we referred to the linked list as a component inside its definition? This is known as a recursive data structure, and the reason it is valid is because it has a base case, i.e. empty /null, which terminates the list. As a consequence of the above point, every single node taken in isolation can be thought of as its own unique linked list, since it does indeed meet the above definition. Conceptually, an object of type Node is a linked list. As another consequence of the definition, every time you have a method that receives a linked list as parameter, you need to handle both possible cases of linked list - either a node or the empty list. However, be careful not to confuse a null list (i.e., the empty list) with a non-null Node with its value field set to null! Yet another consequence of this non-00 design is that this manner of list instantiation does not make sense: My Raw LinkedList myList. = new MyRawLinkedList (); All the methods in this class are static, so MyRawLinked List is acting here just as a convenient place to put all of our methods. Remember, a Node is a list, so you create lists like so: Node list 0 null; // the Node list 1 = new Node ("b", Node list 2 = new Node ("a", empty list, listo list0); // list1 listl); // list2 2 - = (1 [b] [a, b] Again, notice that list 2, listi, and list0 are all distinct lists when taken in isolation, but list 2 contains (points to) list1 which contains (points to) list 0. In order for you to get anything out of this assignment, we require that you do not use arrays anywhere in your implementation, and that you do not use other classes or functions to manipulate the lists. Thus you should not have any import statements at the top of MyRaw Linked List java. You may write your own helper methods as long as they have unique names (do not overload the existing method names). You may also use the methods of the elements (for example: equals and compare To from java.lang. String). Additionally, as noted in the comment blocks above them, do not use the provided implementations of get, contains, or size in your implementation of the three methods below. They are there just to allow our unit tests to run; you may of course use them in your own testing. Activity Implement the following static methods in the MyRaw Linked List.java file: Met hod 1: reverse (Node) This method takes as its parameter a linked list, reverses the order of that list, and returns the node at the head of the reversed list. You may store temporary pointers to Nodes within the list (as in Node n head), but do not create any new instances of Node; in other words, the expression new Node (...) should not appear anywhere in your implementation. Also, do not modify the value field inside each Node; your implementation should reverse the direction of the node pointers, not move values around. Met hod 2: removeMaximum Values (Node, int) This method takes as parameters a linked list and an integer N and returns the linked list from which all instances of each of the N largest values in the input linked list have been removed. If the input value N is zero or negative, this method should simply return the list without modification. The other elements in the list should not be modified and their relative order must not be changed. Removing the N maximum values from an empty list should return the empty list for any value of N; an exception should not be thrown in this case, and in general you shouldn't throw exceptions unless we specify that you do so. Because the values are Strings, you will need to use the String class's compare To method to compare 3 the Strings; see the Java API for help with that method. This method performs lexicographic comparison (similar to how dictionaries are sorted), so "b" is larger than "a", and "aa" is larger than "a", etc. Note that compareTo is undefined if its argument is null and will throw an exception in this case. Your implementation should not attempt to handle/catch that exception. We will not pass a list to your method that contains any nodes with null Strings. For instance, if the list contained the following: DOG GORILLA BANANA CAT GORILLA BEAR Then removeMaximumValues (head, 1) would remove all instances of the largest value, which is "GORILLA", and the linked list would then look like this: DOG BANANA CAT BEAR However, given that same linked list, remov eMaximumValues (head, 2) would remove the two largest values, which are "GORILLA" and "DOG", so the linked list would then look like this: BANANA CAT BEAR Keep in mind that if any of the N largest values appear more than once in the linked list, this method should remove all instances, so it may remove more than N elements overall. So, for instance, if we had: KANGAROO PLATYPUS AARDVARK KANGAROO DONKEY COYOTE and called remove Maximum Values (head, 2), it would remove all instances of the largest value ("PLATYPUS") and all instances of the second-largest value ("KANGAROO") and we would then have this: AARDVARK DONKEY COYOTE As with the previous method, you should not create any new instances of Node; the linked list should be mutated in place. However, it's possible that the head of the original list could have been deleted (or even all the elements of the list might have been wiped out), so you need to ensure that you return whatever is left of the list. Met hod 3: cont ainsSubsequ en ce (Node, Node) This method takes as input two lists, head and other, and determines whether the values stored in the list other are a subsequence of the values stored in the list head. A sequence T is a subsequence of Sif T can be derived from S by deleting zero or more values from S without changing the relative ordering of the values. For example, the sequences (the empty sequence), [b]. [a, c], and [a, b, c, d] are all subsequences of [a, b, c, d] (out of a total 16 possible subsequences). But [b, a] would not be a valid subsequence of [a, b, c, d] since ordering must be preserved. Note that the empty sequence is a subsequence of all possible sequences, therefore if other is the empty list, this method should return true. Also note that you should compare only the values stored in the two lists to determine if other is a subsequence of head. The nodes themselves do not need to be shared between the two lists, only the values stored in those nodes. Part 2: Linked List The goal of part 2 is to understand the implementation of a linked list class as an encapsulated, object-oriented dat a structure. The primary functionality of the methods is the same as part 1, but there are some subtle differences. Each method will work with the object's linked list (head field or this.head) instead of a list pointer passed as a parameter. Changes should apply to the state of the MyLinkedList object instead of a returned list. Additionally you must consider and correctly maintain the object state (head, tail, and size). You may copy your implementations from MyRawLinkedList and adjust as needed, or write entirely new implementations. You may use the existing methods in MyLinkedList, but may not use other classes or utility methods to manipulate the list. You may use the elements' methods (examples: equals and compare To). While we are less concerned about efficiency in this assignment, we also strongly suggest (but do not require) that you avoid using the provided get (int) method (i.e. to get an element at a particular index) in your implementation. An elegant implementation of the required methods below can and should be done without calling get (int), as implementations that use this typically run much slower. There is a key difference between MyRawLinked List and MyLinked List in terms of how the notion of a linked list is defined. A valid raw linked list is a Node that is either null (encoding the empty list) or non-null (encoding a non-empty linked list and containing a value and a reference to another raw linked list); and, you instantiate a new raw linked list by creating a new Node. However, you instantiate a MyLinked List via new MyLinkedList, which internally handles the instantiation of the raw nodes whenever you add values to it. Thus a null-valued variable of type MyLinked List is not the same as an empty linked list, which would be an instance of My Linked List with a size field set to 0 and a head field set to mull. Yet, inside of MyLinked List you still treat a null-valued Node as encoding an empty list, just as you did in MyRaw Linked List, but this detail is hidden to the outside world. This is what is meant by "encapsulation" and it's the reason why to some extent you are able (and encouraged) to copy your implementation from MyRawLinked List and have it just work with only a few modifications. Note that once you understand what distinguishes a raw linked list from its 00/encapsulated form, the adjustments required to get your method implementations in part 1 working for part 2 are very minimal and should only take a few minutes. Expect to spend most of your time just thinking about what the differences are. Activity Implement the following methods in the MyLinked List .java file: Met hod 1: reverse Same behavior as part 1, except that updates should be made to the MyLinkedList instance (i.e. this), instead of returning the reversed list. Don't forget to update both the head and tail fields. Met hod 2: removeMaximumValues Same behavior as part 1, except that updates should be made in-place to the instance instead of returning the list. Remember to update all three instance fields (head, tail, and size) as needed. For the same reason you should generally avoid get (int), we also suggest (but do not require), for the sake of efficiency, that you avoid using the provided remove(int) (i.e. remove an element by index) in your implementation of remove Maximum Values (int). A little repetitive code is preferable to code that is orders of magnitude slower. In part 1, the return type was boolean, with 2 possible output values true and false encoding, respectively, "contains subsequence" and "does not contain subsequence". For part 2, notice that we have written the return type as Boolean. Whereas boolean is a primitive type in Java, Boolean is a class that contains a boolean value field. But, being a class, a variable of type Boolean might not be instantiated (i.e. it can be null). We say that these encapsulated types are "nullable", because they can possibly be null, which primitive types cannot. Consequently, a variable of type Boolean has three possible values: true, false, and null. When other is non-null, our contains Subsequence method should behave exactly the same as part 1 in terms of returning only either true or false. Recall that we said above that a variable of type MyLink ed List with value null is not actually a linked list object at all, and is not the same as an empty linked list. Rather, it is the complete absence of a linked list object. The contains Subsequence operation is undefined if it does not have a linked list object to operate on, so when other is null, the method should return null. Returning null to represent an invalid input is one of several programming styles that we will see throughout this semester. Your method should not throw a NullPointerException or any other exception (either on purpose, or because you forgot to check for null). In a future assignment you will see a different style of error handling in which we do want you to throw an exception.

Answer rating: 100% (QA)

Given Provided the skeleton code for a doublylinked list implementation Concept Data Structures Doubly Linked List I see that youve provided the skeleton code for a doublylinked list implementation al... View the full answer