title: a collection data structure to keep items sorted
body: <p>I got a program which is using an <code>ArrayList&lt;T&gt;</code> and that type T also implements <code>Comparable&lt;T&gt;</code>. I need to keep that list sorted.</p>
  
  <p>For now, when I insert a new item, I add it to the <code>ArrayList</code> and then invoke <code>Collections.sort(myArrayList)</code>. </p>
  
  <p>Is sorting with <code>Collections.sort</code> every time I insert a new item seriously hurt run time complexity? </p>
  
  <p>Is there a better suited data structure I can use to always keep the list sorted? I know of a structure called a <code>PriorityQueue</code> but I also need to be able to get the list's elements by index.</p>
  
  <p>EDIT:
  In my specific case, inserting a new item happens much less than geting an already existing item, so eventually a good advice could also be to stay with the <code>ArrayList</code> since it got a constant time complexity of getting an item. But if you know of anything else...</p>