title: Maintain a sorted list with performance
body: <p><strong>Summary of my question:</strong> I need a list that can quickly be iterated and sorted (either by sorting method or adding/removing object).</p>
  
  <p>I'm coding a game in which there are a lot of "collision zones", that are checked every frame. For optimization, I have a idea of sorting them depends on their X position. The problem is not all collision zones are static, because some of them can move around.</p>
  
  <p>I have managed to handles all the changes, but to maintain the <code>ArrayList</code> (or <code>ConcurrentLinkedQueue</code>) sorted using <code>Collections.sort()</code> is too slow.</p>
  
  <p>So I got a new idea: I may use a Tree, and whenever a zone's X is changed, instead of sorting all elements again, I can just remove then re-add it from the tree. However, I think that adding and removing operator in TreeList are expensive too. Moreover, iterating through Tree is not as effective as <code>ConcurrentLinkedQueue</code>, <code>LinkedList</code> or <code>ArrayList</code>.</p>
  
  <p>Please tell me if there is any built-in data structure that satisfy my need. If there is no such data structure, I intend to extend <code>ArrayList</code> class, override the <code>add</code> method to ensure the order (by using overload <code>add(index, item)</code>. If you think this is the best way, please give me the best way to find the index. I already use BinarySearch but I think there is a bug:</p>
  
  <pre><code>@Override
  public boolean add(T e) {
      // Find the position
      int left = 0;
      int right = this.size() - 1;
      int pos = right / 2;
      if (e.compareTo(this.get(0)) &lt;= 0) {
          pos = 0;
      } else if (e.compareTo(this.get(this.size() - 1)) &gt;= 0) {
          pos = this.size();
      } else {
          // Need: e[pos - 1] &lt;= e[pos] &lt;= e[pos + 1] 
          boolean firstCondition = false;
          boolean secondCondition = false;
  
          do {
              firstCondition = this.get(pos - 1).compareTo(this.get(pos)) &lt;= 0;
              secondCondition = this.get(pos).compareTo(this.get(pos + 1)) &gt;= 0;
  
              if (!firstCondition) {
                  right = pos - 1;
                  pos = (left + right) / 2;
              } else if (!secondCondition) {
                  left = pos + 1;
                  pos = (left + right) / 2;
              }
          } while (!(firstCondition &amp;&amp; secondCondition));
      }
  
      this.add(pos, e);
  
      return true;
  }
  </code></pre>