使用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 AdaptiveListString; // 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.
