主題
前言：
在上一篇【Unity C#小工具】簡單通用物件池 中提出的GCManager腳本，感謝@派大星教授的指導，今天做了些修正後更新在Github上了。最近讀優化的東西剛好看到ArrayList竟然是O(1)，當下還懷疑自己有沒有看錯，所以藉機了解一下。
主要修正的點：
以前回收語法是：
LinkedListNode<object> to_remove_obj = dicts[_key].Find(obj);
如同@派大星教授說的：
《上面這樣.Find()又要尋找整個Linklist, 時間依舊O(N), 使用Linkedlist時正確應該是把Node給使用者自行管理》
原本是希望有了這個工具，使用者就可以透過Key去取得物件就好，如果還多了"保存"的義務的話，勢必要多些使用者的麻煩。所以我就加了個dict去保管node。
static Dictionary<string, Vector2> s_m_registerScale = new Dictionary<string, Vector2>();
以內容物為key，在Instancitate時更新對應的node。
在回收時能直接使用。
因此使用者呼叫方法依舊，不用做其他改變。
[1]. When to use linkedlist over arraylist in java
LinkedList ：
使用doubly-linked list結構 (頭接著上一個的尾端)get(int index)： O(n)、平均 n / 4。 只讀頭尾是O(1) 。add(int index, E element)：O(n)，平均n/4。只寫頭尾是O(1) 。remove(int index) ：O(n)，平均n/4。 只刪頭尾是O(1) 。適合重複使用的資料鏈，且需頻繁插入、移除。比ArrayList 多一些overhead，所以占用比較多的空間。
ArrayList ：
Dynamically re-sizing array.
get(int index) ：O(1)。
原理：假設一個int是4 bytes，起頭位址是1000，則若要訪問第20個，1000+4*20=1080，只要算一次。。
理論上ArrayList 平均會比LinkedList 快一些，但差距不太大。add(E element)： 攤銷O(1)，Array擴充最遭情況是O(n)。因為每次擴充都要安排一個新的、更大的array，然後把舊的資料複製到新的array上。add(int index, E element)：O(n)、平均O(n/2)remove(int index)：O(n)，平均O(n/2)。一開始要多給更空的空間，不然新增空間很慢。
使用LinkedList 的好處是刪除頭尾是O(1)，ArrayList 是O(n)。
如果記憶體大小很重要，請避免使用LinkedList 。
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
後記:
了解兩者差別後，以Object pool來說，是大量生成一定數量的物件，之後就是取值而已，照理來說應該用ArrayList而不是LinkedList
參考資料：
[1]. when to use linkedlist over arraylist in java:https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java
[2]. ArrayList Get Operation O(1). How? https://stackoverflow.com/questions/19011779/arraylist-get-operation-o1-how
