Java代写：COMS228 An Adaptive List

使用Linked List，根据要求代写Adaptive List，并通过测试。

Introduction

This assignment gives you an opportunity to work with a linked data structure by implementing the java.util.List and java.util.ListIterator interfaces through an adaptive list. This adaptive list is a doubly linked list complemented by an array for indexed read operations (like get(int pos)) and indexed write operations (like set(int pos, E obj)). The adaptive list is much more efficient than the doubly linked list for supporting a long sequence of indexed read/write operations flanked by add() and remove() operations.

Requirements of the AdaptiveList class

Write a generic linked list class named AdaptiveList. Your class must implement the java.util.List interface. You may find it helpful to read the Javadoc for the interface along with its iterator subinterface. All the methods except subList method in the interface as well as a few additional methods must be implemented without throwing an UnsupportedOperationException. You may throw an UnsupportedOperationException for the subList method. Note that for some of the methods, we provide their implementations as examples for you to study or for showing the list/array created by your code; you just need to implement the other methods with the comment line // TODO. You are not allowed to use any Collection class in your implementation.

The AdaptiveList class has a non-static inner class named ListNode whose instances serve as nodes in the doubly linked list. The inner class has three member variables: data of generic type E, link of type ListNode, prev of type ListNode, No additional member variables in the ListNode class are allowed. The link field of a node refers to its successor node in the list if the successor node exits and is null otherwise. The prev field of a node refers to its predecessor node in the list if the predecessor node exits and is null otherwise. Every AdaptiveList list must have two dummy nodes named head and tail along with normal nodes. The list is empty if it has no normal nodes. If the list is empty, then head is the predecessor of tail and tail is the successor of head. Otherwise, head is the predecessor of the first normal node and the first normal node is the successor node of head; tail is the successor of the last normal node and the last normal node is the predecessor of tail. The data fields of head and tail are always null. The prev field of head and the link field of tail are always null.

Write a private inner class named AdaptiveListIterator to implement the ListIterator interface. You should implement all methods in the ListIterator interface without throwing any UnsupportedOperationException. There is no need to keep a coherent list if there is concurrent modification to the list. In other words, the iterator does not have to be a failfast iterator.

In addition to the doubly linked list, the AdaptiveList class keeps an array of type E elements for implementing the get(int pos) and set(int pos, E obj) methods efficiently. This is done as follows. The class keeps two boolean fields named linkedUTD and arrayUTD (UTD stands for Up To Date): linkedUTD is true if the doubly linked list is used to represent the current sequence of data items and false otherwise; arrayUTD is true if the array is used to represent the current sequence of data items and false otherwise. At any time, the current sequence of data items is represented either by the doubly linked list or by the array; so at least one of linkedUTD and arrayUTD is true. The doubly linked list is used to implement all methods except for the get(int pos) and set(int pos, E obj) methods, which are implemented by using the array. These implementations are facilitated by using two helper methods: The updateLinked() method creates a new doubly linked list with numItems normal nodes by coping the current sequence of data items from the array to the doubly linked list and setting linkedUTD to true, whereas the updateArray() method creates a new array of length numItems by coping the current sequence of data items from the doubly linked list to the array and setting arrayUTD to true. If a method is to be implemented by using the doubly linked list but linkedUTD is false, then updateLinked() needs to be called before the implementation and at the end arrayUTD needs to be set to false if the doubly linked list is modified by the method so that the array is no longer up to date. Similarly, if a method is to be implemented by using the array but arrayUTD is false, then updateArray() needs to be called before the implementation and at the end linkedUTD needs to be set to false if the array is modified by the Set() method (see the following example).

AdaptiveList[String] seq = new AdaptiveList[String](); // code
seq.add("B");
seq.add("A");
seq.add("C");
System.out.println("After the three seq.add() operations:");
System.out.println("linkedUTD: " + seq.getlinkedUTD());
System.out.println("arrayUTD: " + seq.getarrayUTD());
System.out.println(seq.toString()); // show both linked list and array
System.out.println( seq.get(1) );
System.out.println("After the seq.get(1) operation:");
System.out.println("linkedUTD: " + seq.getlinkedUTD());
System.out.println("arrayUTD: " + seq.getarrayUTD());
System.out.println(seq.toString());
System.out.println(seq.set(1, "D") );
System.out.println("After the seq.set(1, 'D') operation:");
System.out.println("linkedUTD: " + seq.getlinkedUTD());
System.out.println("arrayUTD: " + seq.getarrayUTD());
System.out.println(seq.toString()); seq.add("E");
System.out.println("After the seq.add('E') operation:");
System.out.println("linkedUTD: " + seq.getlinkedUTD());
System.out.println("arrayUTD: " + seq.getarrayUTD());
System.out.println(seq.toString());

After the three seq.add() operations:

linkedUTD: true
arrayUTD: false
A sequence of items from the most recent array:
[]
A sequence of items from the most recent linked list:
(B, A, C)
A
After the seq.get(1) operation:
linkedUTD: true
arrayUTD: true
A sequence of items from the most recent array:
[B, A, C]
A sequence of items from the most recent linked list:
(B, A, C)
A
After the seq.set(1, 'D') operation:
linkedUTD: false
arrayUTD: true
A sequence of items from the most recent array:
[B, D, C]
A sequence of items from the most recent linked list:
(B, A, C)
After the seq.add('E') operation:
linkedUTD: true
arrayUTD: false
A sequence of items from the most recent array:
[B, D, C]
A sequence of items from the most recent linked list:
(B, D, C, E)

Submission

You are required to include, in your submission, the source code for each of the classes: A short template is given in package cs228hw3.zip. You need to write proper documentation with Javadoc for each method that you implement.

Write your class so that its package name is edu.iastate.cs228.hw3. Your source files (.java files) will be placed in the directory, as defined by the package specified above. Be sure to put down your name after the @author tag in each class source file. Your zip file should be named Firstname Lastname HW3.zip. You may submit a draft version of your code early to see if you have any submission problem with Blackboard Learn. We will grade only your latest submission.