Assignment: An Adaptive List - Topic: Computer Science (data structure java)

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))andindexedwriteoperations(like set(int pos, E obj)). The adaptive list is much more e!cient than the doubly linked list for supporting a long sequence of indexed read/write operations ?anked 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 iteratorsubinterface. All the methods except subList method in the interface as well as a few additional methods must be implemented with-out 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 in- stances 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 exists 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 modi?cation 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), set(int pos, E obj) and reverse() methods efficiently. Note that the reverse() method swaps the elements at indexes 0 and n ! 1, at indexes 1 and n ! 2, and so on, so that the order of the elements in the array of length n is reversed. The method returns false if n ≤ 1 and true otherwise. This method needs to be implemented without using any additional array.

The doubly linked list and the array are alternately used as follows. The class keeps two boolean ?elds 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), set(int pos, Eobj) and reverse() 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 copying 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 copying 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 modi?ed 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 modi?ed by the Set() or reverse() method (see the following example).

Attachment:- Assignment Files.rar