在内存中是一段连续的存储空间。

数组操作的时间复杂度分析

insert: O(n) --> 最坏情况下，需要将整个数组向后移动一位

delete: O(n) --> 最坏情况下，删除第一位元素，需要将第一位元素之后的所有元素往前移动一位

update: O(1) --> 因为是连续的内存结构，因此可以直接定位到指定下标的元素，然后更新

query: O(1)

不是一段连续的存储空间。

链表的时间复杂度分析

insert: O(1)

delete: O(1)

update: O(1) --> 增、删、改时间复杂度为 O(1)，前提是已经知道目标节点，不考虑查找的情况。增删只需操作链表的前驱节点，后驱节点。

query: O(n) --> 需要从头节点，依次往后查找。最快情况下，目标元素恰好是最后一位元素。

跳表的作用是为了，加速普通链表的查询速度，它要求链表本身是有序的。

原理是通过在原始的链表基础上添加一级、二级等等索引，通过查询索引的方式快速定位到目标元素。 应用到的核心思想就是：“空间换时间”

查询的时间复杂度为 O(logn)

特点：先进后出，可采用数组，链表基础数据结构来实现。

增、删的时间复杂度为 O(1)

查询的时间复杂度为 O(n)

特点: 先进先出，可采用数组，链表基础数据结构来实现。

增、删的时间复杂度为 O(1)

查询的时间复杂度为 O(n)

两端都可以进出的队列。

增、删的时间复杂度为 O(1)

查询的时间复杂度为 O(n)