数组 Array： 内存里连续的一组空间。

数组（左下标，右 内存地址【示意】）

数组可以随机访问内存中的数据（根据下标），其时间复杂度是O(1)。 

数组的常见操作有查询（随机访问），插入，删除。

数组插入和删除

因为是连续内存，插入或删除。需要挪位置。 比如图中的 插入。 元素D需要插入到数组下边为3的地方，而数组下标后边的元素需要依次向后移除。所以插入的时间复杂度是O(N).

 当然了如果你插入的是数组中最后一个元素,后面没有元素需要挪动，那么时间复杂度是O(1).

  如果你插入的是数组中第一个元素,后面元素都需要挪动，那么时间复杂度是O(N).

所以平均复杂度是O(n/2), 而n不是具体数字，还是一个概数，所以复杂度也就是O(N)。喜欢钻牛角尖的同学可以仔细理解一下这里的复杂度。

同理删除也是如此。

数组相关操作的复杂度

链表 linked list

链表数据结构示意图

使用场景： 

1.在插入和删除比较多的情况下使用。（时间复杂度为O(1)，快于数组的O(N)）

2.不知道有多少个原始元素。

链表还有一些变种：

变种链表

链表的常见操作有 插入，删除。

链表数据结构示意图

很显然，插入和删除只需要将相关节点的next的指针调整。复杂度为O(1)。

但是他的查找就需要一个个找了，复杂度为O(N)。

所以需要根据实际业务场景选择合适的数据结构。

另外上面说的是单链表，还有常见的双向链表，如下图

双链表

双链表既有前驱，也有后继。在查询链表的时候回更加方便。

双链表的相关操作复杂度

这里暂时了解即可。

本篇结束。