列表的链接列表或数组实现的优点和缺点

列表的链接列表实现具有优于基于数组的实现和副作用的优点是什么？列表的链接列表或数组实现的优点和缺点

对于初学者，我知道链表使用了比数组多的空间，因为它必须使用额外的4个字节的空间来存放对下一个节点的引用，并且数组不需要这样做。所以阵列使用更少的空间。

优点linked-list在数组上的实现是数组在初始化时具有固定的大小，并且您必须编写代码来增加数组的大小，因此与链接列表实现相比可能是不利的。

对于其他优势缺点的任何想法？

http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list –

对于数组，如果有索引（恒定时间复杂度O（1）），则可以访问任何元素。但是对于一个列表，尽管有索引（时间复杂度为O（n）），但您必须逐个访问才能访问。有关列表，插入和删除元素需要一个固定时间（O（1））。但对于数组，插入和删除需要O（n）时间。

对于排序，列表实现比数组实现要好。

2013-10-07 07:04:22 SRF

我喜欢你的答案，因为你做了更彻底的分析列表的2个实现之间的比较。推荐的SO帖子在数组和链接列表之间进行了更多的比较，这与我的直接问题略有不同。 – user2838559

回答