What happens if I merge ArrrayList and LinkedList?

Greetings!
 
After studying the collections, namely such implementations List , such as ArrayList and LinkedList , an idea arose, and why not combine these data structures into one and see what will come of it.
 

Why is this necessary?


 
  •  
  • Problem ArrayList - it has an initial default size of DEFAULT_CAPACITY or 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)  
  • Problem LinkedList - here, on the contrary, add a new element, it's just add a new link (create another Node and 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 O (n)  

 

Solution


 

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:
 
What happens if I merge ArrrayList and LinkedList?
The project can be viewed at

+ 0 -

Add comment