如何建立排序列(Sorted list)

我在寫JavaMudX時，需要用到排序的List，因為這樣可以讓list中的物件在顯示時有某種序列。但是我發現Java標準的API中並沒有自動排序的List，只有用Collections.sort(List)或Collections.sort(List, Comparator)來執行排序！
眾所皆知，任何排序動作都需要O(n ln n)的時間，因此使用Collections.sort(...)來排序是不切實際的，若是在insert method of List執行sort，那每次insert至少都要花O(n ln n)的時間，這真是浪費！因此我便在網路上尋找可排序的其他種方法。

後來我在某家網路文件上看到合理又簡單的建立sorted list方法：

//假設這是個已經排序的List，因此對此List進行BinarySearch是很合理的
//此index回傳的是此物件在此List上的序數，若是此物件不在List上，
//則會回傳一個負數
int index = Collections.binarySearch(itemList, item);
//若index為負數，將它插入-index-1的位置
if(index < style="color: rgb(153, 153, 153);">//否則，插入他尋找到的index
else itemList.add(item);

因此，在一個內容為 ["aaa", "bbb", "ccc", "ddd"]的List上，若您要add的是"ccc"，則它會被插入 index= 3的地方；若要add("czz")的話，index會很神奇地回傳-5，則插入動作把"czz"放在-(-5)-1 = 4的地方！
如此我們就完成了可排序的add行為。若能保證此List的開始狀態就是已經sorted(例如empty List) 的話，則之後的add/remove都不會破壞已排序的特性。

且此add()耗費的時間只是從O(1)提升到O(e * lnn)+O(c)而已！
(e:equals花費的時間　n:List的大小　e * ln n:Binary Search的時間　c:add(item, index) 的時間)
非常划算！