# 前端数据结构

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

## 数组

用一组连续的内存空间，来存储一组具有相同类型的数据。 由于在内存中是连续存放的，通过下标来随机访问数据效率是非常高的，但是，由于连续性，我们进行 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= 1000&#x30;_&#x6E;+10000 ，T= &#x31;_&#x6E;\*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)

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