作者stu87616 (DoubleLight)
看板C_Sharp
標題[問題] List<T>底層是怎麼實作的？
時間Sat Aug 16 13:41:20 2014
最近在幫朋友解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://webptt.com/m.aspx?n=bbs/C_Sharp/M.1408167686.A.7BB.html
※ 編輯: stu87616 (1.171.245.175), 08/16/2014 13:42:05
1F：→ ssccg: 用array做的，空間不夠就重新allocate新array 08/16 14:49
2F：→ ssccg: List<T>就是ArrayList的generic版啊 08/16 14:49
那如果只是刪除中間幾個項目，或是要插入呢？
難道會把插入點之後的項目都進行搬移嗎？
3F：→ ssccg: C++也不用自己寫啊，用vector就好 08/16 14:51
就是單純很懶...
※ 編輯: stu87616 (1.171.245.175), 08/16/2014 14:55:41
4F：→ ssccg: 沒錯List插入就會把後面的都往後搬，所以要O(n) 08/16 14:57
5F：→ ssccg: 所以通常用List是不太會去用指定index的方法 08/16 14:59
6F：→ ssccg: 的insert/remove 08/16 14:59
顆顆我還蠻常用的說，看來以後要注意一下了
※ 編輯: stu87616 (1.171.245.175), 08/16/2014 15:07:59
7F：→ uranusjr: FWIW, C# 有 LinkedList, 請在合適時選用 08/16 15:34
8F：噓 jackace: c++明明就有list<T> 跟懶有甚麼關係 08/16 18:08
抱歉 我承認我的確只是稍微看一下文件覺得太麻煩就直接自己硬幹了
不過本文的主題還是想問C#的部分啦
如有冒犯還請海涵
※ 編輯: stu87616 (1.162.160.250), 08/16/2014 19:06:12
9F：推 jizang: 都叫做 List，怎麼還會跟 Array 扯上關係！ 08/16 20:35
10F：→ iterator: 直接看 .NET Framework 的 source code 吧! 08/17 02:16
12F：→ iterator: Purpose: Implements a generic, dynamically 08/17 02:18
13F：→ iterator: sized list as an array. 08/17 02:19