数组与链表结构的优缺点

Question

大佬详细讲一下，数组与链表结构的优缺点，谢谢了

Answer 1

在比较两种数据结构优缺点的时候一般看存取方式和使用效率，目前在很多语言都可以直接使用数组和链表结构，所以代码实现的部分就直接略过了，先重点来说明一下结构的特点。

数组：在初始化以后长度固定，是一整块连续的空间，说白了就是存储元素的地址是连续的，所以我们只要知道首个元素的位置，就可以顺次知道其他元素的存储地址，这就很适合使用索引下标的方式来操作。

链表：链表是顺序表的一种，以链式的方式来进行存储，所以在每个节点中除了要保存集合元素外，还要存储下一个链表元素的位置信息或终止标识。（双向链表等可能需要存储更多信息）对于链表结构来说，增加或减少元素的个数都是很容易的，只需要节点之间的指向信息就可以了。

在实际的使用中，由于很多语言都已经对结构进行了封装，使用起来很方便，而且调用的方法也没多大却别，如：ArrayList，LinkedList。所以需要重点关注的就是使用效率，在各种场景下如何选择。对于数据量比较小的场景，千条或者万条数据时这种差异是微乎其微的。

对于集合的操作，主要是元素取用，插入，删除，替换。对于数组来说，由于本身结构的限制，如果删除或添加某一元素，必须重新构建一个数组，并将其他元素进行串位，才能保证结构的完备性，在使用时一定要注意这一点。所以可以看出，如果我们使用数组结构，涉及到元素的更新（插入、删除）时效率是很低的，但是由于存储连续，根据位置快速定位一个元素是很容易的。所以数组更适合元素的按位提取，不适合大量元素的增删。

对于链表结构，特点刚好和数组相反，如果想在任何一个位置插入或删除一个元素，都只要修改节点中指向信息就可以了。加入目前链表中有a、c、d三个元素，a节点中存储了c元素的位置，c节点中存储了d节点的位置。如果想要在a与c中插入一个b元素，只需要构建一个元素内容为b的节点，然后将a指向b，b指向c就可以，删除也是同样修改指向。但是在进行元素查找时，由于元素存储位置并不是连续的，存储在每一个节点中，在按位置取出元素的时候需要逐个找下去。所以链表更适合元素的增删，不适合元素的按位提取。