This assignment aims to present practical knowledge of data structures and algorithms. The app has been created as a
Gradle project. The source files are located in
/src/main/java/com/ca2 the unit tests are located in /src/test/java/com/ca2.
The first requirement was to create its own Generics list based on the given interface IList. The two lists have been created GenericArrayList and GenericLinkedList.
Both lists accept generic types amd implemented itteration, for example:
import com.ca2.GenericArrayList;
import com.ca2.GenericLinkedList;
GenericArrayList<Integer> arrayListInt=new GenericArrayList<>();
arrayListInt.add(1);
GenericArrayList<String> arrayListStr=new GenericArrayList<>();
arrayListStr.add("String");
// interate over arrayListInt
for(item:arrayListInt){
System.out.println(item);
}
GenericLinkedList<Integer> linkedListInt=new GenericLinkedList<>();
linkedListInt.add(1);
GenericLinkedList<String> linkedListStr=new GenericLinkedList<>();
linkedListStr.add("String");
// interate over linkedListInt
for(item:linkedListInt){
System.out.println(item);
}The next requirement was to create its own GenericStack based on given interface IStack and GenericQueue based on given interface IQueue.
GenericStack and GenericQueue accepts GenericArrayList (default) and GenericLinkedList in constructor. Both generic class are able to iterate by returns GenericIteratorStackQueue in their iterate methods.
This requirement was to create the Infix calculator using an operator Stack and an operand Stack. The tester class which reads expression from the keyboard is located in InfixCalculatorTester, this class calls evaluate static method located in InfixCalculator.
Evaluate method throws the Exception if infix expression does not begin with an open bracket and not ends with a close bracket.
INVALID EXPRESSION:
(10 + 3) * 4
VALID EXPRESSION:
((10 + 3) * 4)
The app is parsing the expression and removes the white spaces and all not digit symbols.
GenericCollections class contains static methods that operate on collections, such as GenericArrayList and GenericLinkedList.
One of the requirement was to return the maximum element of the given collection. The Person class have been used to test this functionality. The tester app is available in GenericCollectionsTester. The next requirement was to implement rotate method in GenericCollections class.
This requirement was to add rotate method to the IList interface and implement those methods to GenericArrayList and GenericLinkedList. Then the next requirement was to provide a performance analysis of the differences in the rotate methods applied to GenericArrayList and GenericLinkedList.
To measure the execution times the classes below have been used:
- AnalysisListMethods - the app generates the MD file contains a table with execution times for add, remove, set and get methods performed on IList
- RotateAnalysis - the app generates the MD file contains a table with execution times for rotate, GenericCollection.rotate and GenericCollection.rotate2 methods performed on IList
- Analysis - it returns the execution times for the methods
- AnalysisTable - generates the table in md format
- FileManagement - generates the file
- Timer - measures the time
The generated MD files are located in Methods execution times analysis and Rotate execution times analysis
The rotate method in both IList classed execute two operations remove and add at position 0. In GenericArrayList, remove operation takes O(n) time. The list must be iterated to find the element for removal and update the position of the rest items. Add method in GenericArrayList takes O(n) time to add an element on the first position the iteration must be performed to update the position of the rest items.
In GenericLinkedList, remove operation takes O(n) time. The list must be iterated to update the nodes' positions. Add method in GenericLinkedList takes O(1) time to add an element at the first position. Which makes the GenericLinkedList faster than GenericArrayList by calling the rotate method directly from the list.
GenericCollection.rotate calls twice, get and set methods. In GenericArrayList get takes O(1) time, and set method takes O(n) time. In GenericLinkedList, get and set methods takes O(1) time. GenericArrayList is usually faster than GenericLinkedList when called in the GenericCollection rotate method. The table below shows the operation time for the methods.
| add(0) | remove(index) | get(index) | set(index) | |
|---|---|---|---|---|
| GenericArrayList | O(n) | O(n) | O(1) | O(n) |
| GenericLinkedList | O(1) | O(n) | O(n) | O(n) |