前端数据结构

数据从逻辑上 分为 线性表 和 非线性表 数据之间的关系是线性的： 链表、队列、栈、数组 数据之间的关系是非线性的： 树 堆 和 图

数组

用一组连续的内存空间，来存储一组具有相同类型的数据。 由于在内存中是连续存放的，通过下标来随机访问数据效率是非常高的，但是，由于连续性，我们进行 push、pop 操作都会大面积改变数据， 所以平均时间复杂度为 O（n）

链表

物理存储上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接顺序决定的。由于链表的存储空间不是连续的，使用链表添加或者删除一个数据，我们并不需要为了保持内存的连续性而对数据进行搬移，所以在链表中删除和添加数据都是非常高效的。而随机访问的效率很低，平均时间复杂度为 O(n)

对比

随机访问 O(1)	时间复杂度	数组	链表
随机访问	O(1)	O(n)
增加删除	O(n)	O(1)

什么是时间复杂度：

常见的时间复杂度有：O(1),O(n),O(lgn),O(nlogn),O(n^2)

大 O 描述的是算法的运行时间和输入数据之间的关系

值得注意的是 O(n)复杂度并不代表这个算法就比 O(n^2)快，例如：T= 10000n+10000 ，T= 1n*n+0 这个例子中当 n 为 10 可以看到 O（n）反而快，但 n=10000 的时候 O(n^2)就远远慢于 O(n)了，所以时间复杂度又叫做渐进时间复杂度，描述的是 n 趋于无穷的情况。 ————————————————

查找 插入 删除

数组 o(n) o(1) o(n)

有序数组 o(lgn) o(n) o(n)

链表 o(n) o(1) o(n)

有序链表 o(n) o(n) o(n)

二叉树最坏 o(n) o(n) o(n)

二叉树一般 o(lgn) o(lgn) o(lgn)

平衡树 o(lgn) o(lgn) o(lgn)

哈希表 o(1) o(1) o(1)

————————————————