[toc]
Python 中的 list 和 tuple 两种采用了顺序表的实现技术, 具体前面讨论的顺序表的所有性质.
tuple 是不可变类型, 即不变的顺序表, 因此不支持改变其内部状态的任何操作, 而其他方面, 则与 list 的性质类似.
Python 标准类型 list 就是一种元素个数可变的线性表, 可以加入和删除元素, 并在各种操作中维持已有元素的顺序 ( 即保序 ), 而且还具有以下行为特征:
1. 基于下标 ( 位置 ) 的高效元素访问和更新, 时间复杂度应该是 O(1):
为满足该特征, 应该采用顺序表技术, 表中元素保存在一块连续的存储区中.
2. 允许任意加入元素, 而且在不断加入元素的过程中, 表对象的标识 ( 函数 id 得到的值 ) 不变.
为满足该特征, 就必须能跟换元素存储区, 并且保证跟换存储区时 list 的标识 id 不变, 只能采用分离式实现技术.
在 Python的官方实现中, list 就是一种采用分离式技术实现的动态顺序表. 这就是为什么用 list.append(x) ( 或 list.insert(len(list), x), 即尾部插入元素效率高的原因.
在 Python 的官方实现中, list 实现采用了如下的策略: 在建立空表 ( 或者很小的表 ) 时, 系统分配一块能容纳 8 个元素的存储区. 在执行插入操作 ( insert 或 append ) 时, 如果元素存储区满就换一块 4 倍大的存储区. 但如果此时的表已经很大 ( 目前的阈值为 50000 ), 则改变策略, 采用加 1 倍的方法. 引入这种改变策略的方式, 是为了避免出现过多空闲的存储位置.
