Array 与Linked List有什么区别，分别适用于哪一些场景？ #4

数据结构中有线性表与非线性表之分，线性表主要有Array,Linked List,Queue,Stack，非线性表有Graph,Tree，其中 Array 与 Linked List 都属于数据结构线性表。
先说说Array与Linked List 的特性吧~

Array（数组）

什么是数组呢？
数组是一种线性数据结构，它用一组连续的内存空间来存储具有相同类型的数据。

• 线性数据结构
• 用一组连续的内存空间进行存储相同类型的值

因为有了第二点的支持，让数组有一个天然的优势就是支持任意访问，也就是可以通过索引直接获取到对应的储存数据，可以说是数组的杀手锏，但是这个杀手锏是数组的亮点的同时也暴露了数组的弊端，那就是如果要支持任意访问这一特性的话就得保证数据类型一致性和内存的连续性。这使得数组在删除或者插入数据的时候为了保证连续性而做大量的数据迁移工作；

假设有一个数组[1,2,3,4,5,6],我们对它分别进行插入，删除操作：

插入操作

1. 如果我们要把0插入到数组的第三个位置的话，就得把3,4,5,6都往后移动。
2. 如果我们在数组的第一个位置插入新的数据，那么原先数组的每个数组都得完后迁移。
3. 如果我们是在数组的尾部插入数据，此时因为新增元素后面没有元素存在，并不重要对数据进行迁移。

可以看出数组插入元素的复杂度是O(n)。

删除操作

删除操作同插入操作差不多，复杂度也是O(n)。

但是虽然数组的插入和删除复杂度是O(1),但是对于一些特殊的场景我们还是可以优化成O(1)。例如插入操作中，如果数组不看重有序度的话可以将新元素即将插入的位置中的原数组迁移到数组尾部后再进行插入，这样就不用进行大量的数据迁移啦；对于删除操作我们可以先标记删除的元素，待到数组储存个数即将到达上限时在一次性对删除的元素进行删除。

可以看出数组的优点在于它强大的任意访问，缺点在于插入和删除过于低效，所以这个时候就可以用到我们另外一个大兄嘚Linked List（链表）。

Linked List（链表）

相比数组而言，链表储存数据不需要连续的内存空间，链表的每个节点是一个内存块（JS中可以理解为对象）它比数组占用的内存会更大，但是可以通过节点中指针将一组散乱的内存块关联在一起，通过节点的指针进行遍历和访问所关联的节点。

常见的链表的类别：单链表，双向链表和循环链表。

因为链表的储存空间对内存连续性并没有要求，所以在插入和删除操作更为简单粗暴，复杂度是O(1),但是它有一个缺点，就是没有数组天然的任意访问特性，导致它的查找操作复杂度为O(n)。

对于大数据链来说如果频繁插入或者操作的话，链表比数组更为友好写，但是如果是任意访问的话，数组更为证据优势，不过链表也可以做一些优化提升的，例如可以使用跳表做到复杂度为O(logN)的访问，不过代价是空间复杂度是O(n),对内存的消耗会大一些。

Array 和 Linked List 都更有自己的优点和缺点，如果对内存允许的情况下可以考虑空间换时间，如果内存比较紧缺的时候可以考虑时间换空间，每一种方案都有自己的亮点。

复杂度对比

另外注意一点就是随意访问并非是查找，你就算要查找并且访问元素，用二分法的复杂度也得O(logN)，访问数组中的某个元素必须找到它的位置的前提，虽然说数组的随机访问为O(1)，不过查找某个元素之前得明确它在数组中的位置才可以通过寻址地址访问到对应的元素呀。