作者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/cn.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