本次代写是Java数据结构的一个Programming assignment

In this assignment, you will implement methods that perform functions on a linked list and adapt
those methods to a linked list class implementation similar to the one seen in this module’s videos.

Learning Objectives

In completing this assignment, you will:

• Become familiar with the implementation and behavior of linked lists
• Become familiar with the implementation of an object-oriented linked list class
• Apply what you learned about how linked lists store data
• Develop algorithms for modifying linked list content

Getting Started

Download the provided java files. MyRawLinkedList.java contains the structures, methods that
you will fill in for the first part of this assignment, and some additional example code to help get
you started. MyLinkedList.java contains the starter code for part 2, a simple LinkedList class
implementation similar to those shown in the course videos and seen in the textbook. This class also
contains stubs for the same three methods for you to reimplement or adapt to fit the encapsulated
object oriented LinkedList class.

As you work on this assignment, please do not change the signatures of any of the methods (their
parameter lists, names, and return value types), do not add a “package” declaration, and do not
create any additional .java files for your solution.

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 MyRawLinkedList 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-OO design is that this manner of list instantiation does not
make sense:

MyRawLinkedList myList = new MyRawLinkedList ( ) ;

All the methods in this class are static, so MyRawLinkedList 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 l i s t 0 = nul l ; // the empty l i s t , l i s t 0 = [ ]
Node l i s t 1 = new Node ( “b” , l i s t 0 ) ; // l i s t 1 = [ b ]
Node l i s t 2 = new Node ( “a” , l i s t 1 ) ; // l i s t 2 = [ a , b ]

Again, notice that list2, list1, and list0 are all distinct lists when taken in isolation, but list2
contains (points to) list1 which contains (points to) list0.

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 MyRawLinkedList.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
compareTo 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 MyRawLinkedList.java file:

Method 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.

Method 2: removeMaximumValues(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.