For this question, you are required to design and implement your own version of the Position ADT and the Node List ADT. You are not allowed to use any of the built-in classes or interfaces provided by Java, which provide similar operations. You are however allowed to use any provided Java methods to find/calculate execution times. To simplify your task, the elements stored in the nodes are assumed to only be integer values. Here are the details of the ADTs:
The Position ADT (or the class implementing it) has one single method as follows: element( ): Returns the element (integer) stored at this position.
Your implementation of the Node List ADT must include at least all the methods indicated below. In addition, this class must use arrays as its underlying supportive structure to perform and achieve what is needed. This array, its implementation and manipulations, should never be seen by the user of the Node List ADT; rather it is only known to the developer of this ADT (you!). In addition, since the number of nodes in this Node List is not known and can dynamically change, your implementation of this array must allow for dynamic expansion of the array size once the Node List becomes 80%, or more, full. An expansion would either double the size of the array, or increase it by a constant amount of 10 additional array elements, based on some configuration as will be explained below. You are free to use any naming convention to assign the names of the positions (i.e. A, B, C, etc. or P1, P2, P3, etc., nonetheless, this has to be scalable).
- first(): Returns the position of the first element; error if list is empty;
- last(): Returns the position of the last element; error if list is empty;
- prev(p): Returns the position preceding position p in the list; error if p is first position;
- next(p): Returns the position following position p in the list; error if p is last position;
- set(p, e): Replaces the element at position p with e , and return the old element at position p;
- addFirst(e): Inserts a new element e as the first element and returns the position object;
- addLast(e): Inserts a new element e as the last element and returns the position object;
- addBefore(p, e): Inserts a new element e before position p and returns the position object;
- addAfter(p, e): Inserts a new element e after position p and returns the position object;
- delete(p): Removes and return the element at position p. This also invalidates that position p in the list;
- swap(p1, p2): Swaps the elements pointed by p1 and p2;
- truncate( ): Truncates the underlying array size to the exact number of current positions in the Node List;
- SetExpansionRule ( ): Accepts a single character as a parameter ('d' for doubling the size of the underlying array, or 'c' for increasing the size of the underlying array by constant value, which is 10). By default, the expansion rule should be set for doubling the size. Further calls to SetExpansionRule ( ) would change the expansion rule from one rule to another according to the passed parameter.