The goal of this exercise is to give you experience in implementing the data structures mentioned in the lecture and allow a better understanding of such structures. In addition The exercise shows how, in addition to the basic functionality, some data structures may implement functionality that is specific to them.
Allowing an ArrayList, for example, to be resizable (see Part A) allows for such structures to be more useful and usable.
As an overview:
- you will implement your code in a class that extends (in this case)
MyArrayList. This means that you will have to override the appropriate methods (in this caseadd(int index, T value)) in a way that addresses the requirements in the task. - the task has some tests associated with it, that test said functionality. These tests assume that you implemented the functionality correctly and in the appropriate method.
- To access the tests, you will have to write an appropriate test class that extends (in this case) the
class
MyListTestTemplate. This includes a number of tests that assess the behaviours of lists. - there is an override you need to do in your test class, in order to ensure the correct behaviour.
- NOTE that all the parts that ask you to create implementations of list also use the same test template:
MyListTestTemplate. The different parts will require different implementations and will have the appropriate details. But they all have to fulfill the basic functionality of a List, and that is what the test template assesses.
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.
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.
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.
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.