算法图解 数组与链表
算法图解 数组与链表
最近在看算法图解，顺便将个人学习过程中的提炼，沉底一哈
导语：算法之路–数组与链表
爱好： Americano More Ice !
数组
- 特点：在内存地址中相连
- 优点：执行效率高
- 缺点：初始化占用多余空间，浪费内存
由于数组的缺点，引出“链表”
- 优点：元素可存储在内存的任何地方
- 原因：每个元素存储下一个元素的地址，从而使一系列随机的内存地址串在一起
- 缺点：若元素需要跳跃，效率极差
- ex：当访问最后一个元素，需访问从第一个查起，效率极差
| 数组(array) | 链表(list) | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
需要注意的“术语”
元素的位置为索引，索引从0开始到N
O(1)=线性时间
O(n)=常量时间
场景1：中间插入元素
- 数组：
- 1.若中间插入元素，必须将后面的数组后移
- 2.若中间插入元素且没有足够空间，需要移动整个数组
- 链表：
- 1.只需要修改前面一个元素的指向地址
场景2：删除某个元素
- 数组：
- 1.若删除某个元素，必须所有元素向前移动一位
- 链表：
- 1.若删除某个元素，只需要修改前一个元素指向地址即可
| 数组(array) | 链表(list) | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
实际使用
使用次数：数组>链表
为啥呢？
- 原因：
- 数组支持随机访问，读取速度快
访问方式有两种：随机访问 和 顺序访问
- 随机访问：可直接访问任一元素
- 顺序访问：访问必须从第1个元素开始访问
有没有一个最优解呢？“数组链表”
画了个简图hhh
数组链表：将同类构成链表，放入数组中，成为一个多链表的数组，达到了性能最大化，也就是最优解！