title: What is a data structure that has O(1) for append, prepend, and retrieve element at any location?
body: <p>I'm looking for Java solution but any general answer is also OK.</p>
  
  <p>Vector/ArrayList is O(1) for append and retrieve, but O(n) for prepend.</p>
  
  <p>LinkedList (in Java implemented as doubly-linked-list) is O(1) for append and prepend, but O(n) for retrieval.</p>
  
  <p>Deque (ArrayDeque) is O(1) for everything above but cannot retrieve element at arbitrary index. </p>
  
  <p>In my mind a data structure that satisfy the requirement above has 2 growable list inside (one for prepend and one for append) and also stores an offset to determine where to get the element during retrieval.</p>