I currently have a use case where I need a List data structure. The requirements are that both insertion and deletion at the head and tail need to be optimized, and the ability to optimally get an item at any index is also required.
I know that if I use a LinkedList, insertion and deletion at both the head and tail are O(1), but the get operation at a specific index is O(n).
On the other hand, if I use an ArrayList, insertion and deletion at the head are O(n).
I am aware that a circular array, ArrayDeque in Java, could fit my use case. However, ArrayDeque doesn't implement the List interface, and thus it doesn't have the get method.
My question:
How can I best handle this use case in Java?