Python顺序表

18. 顺序表

18.1 线性结构的实际存储方式 线性表

18.1.1 顺序表

• 将元素顺序的存放在一块连续的存储区里

18.1.2 链表

• 将元素存放在通过链接构造起来的一系列存储块中
• 非连续

18.2 存储数据

• 一体式结构

• 分离式结构

• 获取地址操作时的时间复杂度

  • O(1)

18.3 完整信息结构

• 数据区

• 信息区

  • 即元素存储区的容量和当前表中已有的元素个数

18.4 扩充

18.4.1 每次扩充增加固定数目的存储位置

• 特点

  • 节省空间
  • 扩充操作频繁
  • 操作次数多

18.4.2 每次扩充容量加倍

• 特点

  • 减少扩充执行次数
  • 浪费空间资源
  • 以空间换时间

18.5 增加和删除元素

18.5.1 增加

• 尾端加入

  • O(1)

• 保序加入

  • O(n)

• 非保序加入

  • O(1)

18.5.2 删除

• 尾端删除

  • O(1)

• 保序删除

  • O(n)

• 非保序删除

  • O(1)