[問題] List<T>底層是怎麼實作的？

[stu87616 (DoubleLight)]

最近在幫朋友解C++的問題，常常動不動就手癢用LinkedList存東西

應該是C#的List<T>太方便，用太多的後遺症

但是C++的東西都要自己親自寫(我知道是有套件，但是用起來也是麻煩，乾脆自己寫)

辛苦實作之餘，我不禁想了想，C#的List<T>底層到底都是怎麼實作的呢？


從資料結構的課程來分析，

資料存放的方式有兩大種，陣列和串列，

陣列的優點是存取各項目非常方便迅速，缺點則是增減項目非常麻煩，

串列則剛好顛倒過來

而List<T>可以用像陣列一樣直接用index存取每個項目，

但增刪項目似乎也只需要簡單的調用方法就好(Add、Remove)

整個看起來就是Magic (?)


不過看過MSDN之後，發現List<T>好像來源跟ArrayList差不多，

所以List<T>是基於陣列的架構下實作的結構嗎？

那又是怎麼克服增刪項目的困難呢？

(莫非看起來很簡單的方法，底層其實是一堆髒碼嗎?)



因為實在想不明白，就上來問問各位前輩



--
我覺得Ｃ＃是世界上最強的語言了              紅膠咖咖希希Ｃ    ◥▁▁▁▁ ◢ 麥 
其他的應該廢除                              寶水啡啡嘉  ＃    ◤ ██ ／-   科 
                                            石  腳  嘉          □–□◢◤  舒 
如果各位有興趣的話，可以現在開始學              本             ▼ㄑ     ◢  服 
但是要安裝VisualStudio　    　　      　                        ▼ㄧ  ／◣  特 
因為我們只會支援精英IDE，絕對不會接受垃圾    ψ              ◢ /◣– ◤ /█◣ 

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.245.175
※ 文章網址: http://www.ptt.cc/bbs/C_Sharp/M.1408167686.A.7BB.html
※ 編輯: stu87616 (1.171.245.175), 08/16/2014 13:42:05
→ ssccg: 用array做的，空間不夠就重新allocate新array
→ ssccg: List<T>就是ArrayList的generic版啊
那如果只是刪除中間幾個項目，或是要插入呢？
難道會把插入點之後的項目都進行搬移嗎？
→ ssccg: C++也不用自己寫啊，用vector就好
就是單純很懶...
※ 編輯: stu87616 (1.171.245.175), 08/16/2014 14:55:41
→ ssccg: 沒錯List插入就會把後面的都往後搬，所以要O(n)
→ ssccg: 所以通常用List是不太會去用指定index的方法
→ ssccg:                                    的insert/remove
顆顆我還蠻常用的說，看來以後要注意一下了
※ 編輯: stu87616 (1.171.245.175), 08/16/2014 15:07:59
→ uranusjr: FWIW, C# 有 LinkedList, 請在合適時選用
噓 jackace: c++明明就有list<T> 跟懶有甚麼關係
抱歉 我承認我的確只是稍微看一下文件覺得太麻煩就直接自己硬幹了
不過本文的主題還是想問C#的部分啦
如有冒犯還請海涵
※ 編輯: stu87616 (1.162.160.250), 08/16/2014 19:06:12
推 jizang: 都叫做 List，怎麼還會跟 Array 扯上關係！
→ iterator: 直接看 .NET Framework 的 source code 吧!
→ iterator: http://tinyurl.com/pd8ma9j    list.cs
→ iterator: Purpose: Implements a generic, dynamically
→ iterator:          sized list as an array.