What happens if I merge ArrrayList and LinkedList?
After studying the collections, namely such implementations
List, such as
LinkedList, an idea arose, and why not combine these data structures into one and see what will come of it.
Why is this necessary?
ArrayList- it has an initial default size of
DEFAULT_CAPACITYor the preset size
initialCapacity, when this size is exceeded, a new array of a larger size is created, where data from the old array is copied there, which is very expensive in time, and this gives the algorithmic complexity of
in the worst case. O (n)
LinkedList- here, on the contrary, add a new element, it's just add a new link (create another
Nodeand add a link to it), but the operation of getting the element by the index is very costly, because it will be necessary to go through the entire list from the beginning, which is very costly and gives
What if you create such a data structure that inserts and receives any element in a constant time. I will use technology
ArrayList Without rebuilding the array, which of course loses on memory, but wins in speed, because memory is cheap and there is a lot of it, I consider the performance gain to be a priority.
In order to link them to each other, I will use a doubly connected list:
The project can be viewed at