### Python中的順序表 Python中的list和tuple兩種類型采用了順序表的實現技術，具有前面討論的順序表的所有性質。 tuple是不可變類型，即不變的順序表，因此不支持改變其內部狀態的任何操作，而其他方面，則與list的性質類似。 #### list的基本實現技術 Python標準類型list就是一種元素個數可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征： * 基于下標（位置）的高效元素訪問和更新，時間復雜度應該是O(1)；為滿足該特征，應該采用順序表技術，表中元素保存在一塊連續的存儲區中。 * 允許任意加入元素，而且在不斷加入元素的過程中，表對象的標識（函數id得到的值）不變。為滿足該特征，就必須能更換元素存儲區，并且為保證更換存儲區時list對象的標識id不變，只能采用分離式實現技術。 在Python的官方實現中，**list就是一種采用分離式技術實現的動態順序表**。這就是為什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。 在Python的官方實現中，list實現采用了如下的策略：在建立空表（或者很小的表）時，系統分配一塊能容納8個元素的存儲區；在執行插入操作（insert或append）時，如果元素存儲區滿就換一塊4倍大的存儲區。但如果此時的表已經很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現過多空閑的存儲位置。