Python順序表

18. 順序表

文章目錄

• • 18. 順序表
  • • 18.1 線性結構的實際存儲方式 線性表
    • • 18.1.1 順序表
      • 18.1.2 鏈表
    • 18.2 存儲數據
    • 18.3 完整信息結構
    • 18.4 擴充
    • • 18.4.1 每次擴充增加固定數目的存儲位置
      • 18.4.2 每次擴充容量加倍
    • 18.5 增加和刪除元素
    • • 18.5.1 增加
      • 18.5.2 刪除

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)