计算机的内存储存
- 计算机将一项数据存储到内存时,需请求计算机提供存储空间,计算机给一个储存地址
- 需要储存多项数据时,有两种基本方式:数组和链表。他们有各自优缺点
数组
- 结构特点:
数组在内存中是相连的,为了实现这一点,数组需要让计算机预先分配“预留空间”,这会导致两个问题:
- 存在浪费的空间
- 如果超出存的空间,那就需要转移内存地址
- 读取: 数组知道每个元素的地址(因为连在一起,只需要用加法),所以如果想读取其中一个元素,那效率很高
- 在中间插入: 必须将后面的元素向后移动,如果没有足够空间,还需将整个数组转移到其他整块地方
- 删除: 必须将后面的元素向前移动
- 应用:
- 特别适合快速随机访问,常常和循环语句相结合,实现二分查找、斐波那契数列等,稠密的矩阵也可以用多维数组表示
- 但数组不适合插入和删除
链表
- 结构特点: 链表中的元素,可以在内存中的任何地方,链表中每个元素都储存了下一个元素的地址,从而使一系列随机的内存地址串在一起。
- 读取: 在需要读取最后一个元素时,不能直接读取,需要读取完所有的元素。但如果需要读取所有元素,那效率很高。
- 在中间插入: 其他元素不用动,只需要修改前面元素指向的地址。在中间插入时,首选链表
- 删除: 其他元素不用动,只需要修改前一个元素指向的地址。删除时,首选链表
- 应用:
- 链表不必首先规定数据的数量,也不需要保存无效值。当数据很稀疏时,可以有效利用空间。稀疏的矩阵可以用多维链表表示。此外,也可以表示图论模型中比如多叉图、无向图、有向图。
- 链表不适合快速地随机访问
时间复杂度
\ | 数组 | 链表 |
---|---|---|
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |
简单分析python的数据结构的底层构造
python中list和元组的底层数据结构是? 答案:都是数组。详见:python笔记1-准确掌握列表和元组