基本数据结构:数组/链表

192 阅读2分钟

计算机的内存储存

  • 计算机将一项数据存储到内存时,需请求计算机提供存储空间,计算机给一个储存地址
  • 需要储存多项数据时,有两种基本方式:数组和链表。他们有各自优缺点

数组

  • 结构特点: 数组在内存中是相连的,为了实现这一点,数组需要让计算机预先分配“预留空间”,这会导致两个问题:
    1. 存在浪费的空间
    2. 如果超出存的空间,那就需要转移内存地址
  • 读取: 数组知道每个元素的地址(因为连在一起,只需要用加法),所以如果想读取其中一个元素,那效率很高
  • 在中间插入: 必须将后面的元素向后移动,如果没有足够空间,还需将整个数组转移到其他整块地方
  • 删除: 必须将后面的元素向前移动
  • 应用:
    • 特别适合快速随机访问,常常和循环语句相结合,实现二分查找、斐波那契数列等,稠密的矩阵也可以用多维数组表示
    • 但数组不适合插入和删除

链表

  • 结构特点: 链表中的元素,可以在内存中的任何地方,链表中每个元素都储存了下一个元素的地址,从而使一系列随机的内存地址串在一起。
  • 读取: 在需要读取最后一个元素时,不能直接读取,需要读取完所有的元素。但如果需要读取所有元素,那效率很高。
  • 在中间插入: 其他元素不用动,只需要修改前面元素指向的地址。在中间插入时,首选链表
  • 删除: 其他元素不用动,只需要修改前一个元素指向的地址。删除时,首选链表
  • 应用:
    • 链表不必首先规定数据的数量,也不需要保存无效值。当数据很稀疏时,可以有效利用空间。稀疏的矩阵可以用多维链表表示。此外,也可以表示图论模型中比如多叉图、无向图、有向图。
    • 链表不适合快速地随机访问

时间复杂度

\ 数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

简单分析python的数据结构的底层构造

python中list和元组的底层数据结构是? 答案:都是数组。详见:python笔记1-准确掌握列表和元组