Write a class called MyArrayListResizable that extends MyArrayList.
Override the method add(int index, T value) in a way that, if the internal array is full,
then such array should be doubled in size before inserting the new element.
Write a test class called MyArrayListResizableTest that extends MyListTestTemplate,
where the instance of MyArrayListResizable is initialized with capacity of 1
(i.e., the size for the internal array).
If your implementation of MyArrayListResizable#add is correct, then all tests should pass.
Write a class called MyRingArrayQueue that implements MyQueue.
Internally, it should be similar to the implementation of MyQueueArray,
but with a fundamental performance improvement.
When by adding many elements the tail index reaches the end of the internal array,
instead of shifting elements to the left or copying over to a new larger array,
the tail should start back from 0, unless of course head==0.
The idea is to reuse the empty spaces before head when head>0.
Note, when head==0, or when tail increases so much that it reaches head, then it would
mean that the array is completely full, and you need to copy over to a new internal array.
Write a MyRingArrayQueueTest that extends MyQueueTestTemplate.
If your implementation is correct, all tests should pass.
Run the tests with code coverage enabled, and verify that all of the instructions in your
code are covered. If not, add new tests to MyRingArrayQueueTest.
Using MyLinkedList as a starting point, create a new class called MyBidirectionalLinkedList.
Here, besides a next link, each node also has a previous link pointing to the previous node in
the list. All insert/delete operations need to properly handle and update such previous links.
When inserting/deleting/getting a node at position index, the algorithm should decide if rather start
the search from head using next links, or from tail using the previous links.
If index <= size()/2, it makes sense to start from head.
On the other hand, when index > size()/2 it would be more efficient to start from tail.
Write a MyBidirectionalLinkedListTest that extends MyListTestTemplate.
If your implementation is correct, all tests should pass.
Write a new class MyMiddleBidirectionalLinkedList that extends MyList, using MyBidirectionalLinkedList as starting point.
However, besides having a link to the head and the tail of the list, you need to have a 3rd link, pointing to the middle of the list.
When you need to access an element (e.g., with a get), then you need to minimize the number of nodes to traverse.
For example, assume a list with 100 elements, and you need to delete the element at position 40.
Then, the most efficient way would be to start from the middle link, and go backwards following the previous links till position 40.
On the other hand, if accessing at position 20, it would be more efficient to start from head and follow the next links.
In other words, all indices in the range 25%-75% of the size of the list should be accessed starting from the middle link.
Pay particular attention at the fact that, at each delete and add operation, the value of middle will likely need to be updated.
Note: in case of list with an even number of elements, the middle could have 2 values, choose the lower.
For example: length=1 and length=2 would have middle at position 0, whereas length=3 and length=4 would have it at position 1, length=5 at 2, and so on.
Write a MyMiddleBidirectionalLinkedListTest that extends MyListTestTemplate.
If your implementation is correct, all tests should pass.
Study the source code of MyLinkedList, MyStackLinkedList and MyQueueArray.
Once you think you fully understand them, write their implementation
on paper (e.g., using a pen), without looking at the source code.
Once done, compare what you wrote with the actual implementations.
Solutions to this exercise can be found in the solutions
module, under the org.pg4200.sol02 package.