形式

• 基本顺序表

  • 元素存放空间大小相同

  • 存储的是元素的值
    

• 元素外置顺序表

  • 解决元素存放空间大小不一致
  • 索引
  • 存储的是元素的地址
    

公式L_n = L₀ + n*c

• L_n第n个元素首地址
• n是偏移量 c是固定长度
• L₀ 初始位置
• 从1开始,则L_n=L₁ + (n-1) * c , CPU会多进行一次减法运算

结构

• 一体式结构

  • 表头和数据区,连续
  • 表头：容量，已存储个数
  • 数据区：元素值
    

• 分离式结构

  • 表头和数据区,分离
  • 表头：容量，已存储个数，存储区地址
  • 数据区：可以在内存中连续空闲位置
    

• 存储区替换

  • 一体式若存储空间不够，需整体搬迁，整个对象替换
  • 分离式存储空间不够，只需重新生成数据区，顺序表对象不变

这个就可以解释python列表，用append，insert等新增元素，但整体的列表对象id不变

• 存储区扩充策略

  • 线性扩充，每次扩充固定长度

    • 节省空间，但是扩充操作频繁,操作次数多

  • 加倍扩充

    • :减少了扩充操作的执行次数,但可能会浪费空间资源。以空间换时间,推荐的方式

      • python列表存储，达到阈值，变为1倍，防止过度浪费

• 增加元素

  • 末尾插入O(1)

    • python列表append

  • 非保序O(1)

  • 保序，插入后保持原有顺序O(n)

    • Python列表Insert

  • 可以看出append比insert效率高

• 删除元素

  • 末尾删除O(1)
  • 非保序O(1)
  • 保序O(n)

Python列表

• 采用分离式结构，元素外置的形式
• 存储区扩充，前期加倍，达到阈值，改为加1倍
• append效率比insert高