Python 中的 list 类型应该是我们平时用的最多一个数据类型，如果仅从操作方式上看，列表像是数组和链表的综合体，除了按索引访问外，还支持插入、追加、删除等操作，完全可以当作队列或栈来使用，因此，如果不考虑性能问题，列表是一种易用且功能完善的理想数据结构。
列表的内部结构由两部分构成：(1) 保存元素数量和内存分配计数的头部，(2) 存储元素指针的独立数组。所有的元素使用该数组来保存指针引用，并不嵌入实际的内容。
作为使用频率最高的数据结构之一，列表的性能优化很重要。固定长度的头部结构，很容易实现内存复用。创建时，优先从复用区获取；被回收时，除非超出复用数量限制（80），否则会被放回复用区。每次真正需要分配和释放的是指针数组。
用数组而非链表存储元素项引用，也有实际考虑。从读操作来看，无论是遍历还是基于序号访问，数组的性能总是最高的。尽管插入、删除等变更操作须移动内存，但也仅仅是指针复制，无论元素大小，不会有太高消耗。如果列表太大，或写操作远多于读操作，那么应该使用针对性的数据结构，而非通用设计的内置列表类型。
另外，指针数组内存分配算法基于元素数量和剩余空间大小，按相应比率进行扩容或收缩，非逐项进行。如此，可以避免太过频繁的内存分配操作。
构建列表
显示指定元素的构建语法最为常用，也可基于类型创建实例，接收可迭代对象作为初始内容。不同于数组，列表仅存储指针，而对元素内容并不关心，故可以是不同类型混合。
>>> [1, "abc", 3.14] # 显示指定类型
[1, 'abc', 3.14]
>>> list("abc")
['a', 'b', 'c']
>>> list(range(3))
[0, 1, 2]
另有被称为推导式（comprehension）的语法，同样使用方括号，但以 for 循环初始化元素，并可选用 if 表达式作为过滤条件。PS：一旦将推导式两边的方括号改为小括号，推导式就变成了生成器。
>>> [i for i in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> [i for i in range(10) if i % 2 == 0]
[0, 2, 4, 6, 8]
>>> (i for i in range(10) if i % 2 == 0) # 生成器
<generator object <genexpr> at 0x102216f10>
>>> l = []
# 推导式的行为等同与以下代码
>>> l = []
>>> for i in range(10):
... if i % 2 == 0:
... l.append(i)
...
>>> l
[0, 2, 4, 6, 8]
专有名词 Pythonic 的基本意思就是写出简洁优雅的 Python 代码，而推导式就算是其中的一种。
无论是历史原因，还是实现方式，内置类型关注性能要多过设计。如要实现自定义列表，书的作者建议基于 collections.UserList 包装类型来实现，因为除了统一的 collections.abc 体系外，最重要的是该类型重载并完善了相关运算符方法。
>>> list.__bases__
(<class 'object'>,)
>>> import collections
>>> collections.UserList.__bases__
(<class 'collections.abc.MutableSequence'>,)
# 以加法运算符为例，继承不同的类型，运算会有不同的结果
>>> class A(list): pass
>>> type(A("abc") + list("de"))
<class 'list'>
>>> class B(collections.UserList): pass
>>> type(B("abc") + list("de"))
<class '__main__.B'>
最小接口设计是个基本原则，所以应该慎重考虑列表这种功能丰富的类型是否适合作为基类。
操作
列表支持用加法连接多个列表，乘法运算符复制内容。但同是加法（或乘法）运算，但结果却不相同。
>>> a = [1, 2]
>>> b = a
>>> a = a + [3, 4] # 新建列表，然后与 a 关联
# a、b 结果不同，确定 a 指向新对象
>>> a
[1, 2, 3, 4]
>>> b
[1, 2]
>>> a = [1, 2]
>>> b
[1, 2]
>>> b = a
>>> a += [3, 4] # 直接修改 a 内容
# a、b 结果相同，确认修改原对象
>>> a
[1, 2, 3, 4]
>>> b
[1, 2, 3, 4]
>>> a is b
True
编译器将 += 运算符处理成 INPLACE_ADD 操作，也就是修改原数据，而非新建对象。其效果类似于执行 list.extend 方法。PS：+= 运算符调用的是 __iadd__ 方法，没有该方法时，再尝试调用 __add__ 方法；+ 运算符调用的是 __add__ 方法，该方法会返回一个新的对象，原对象不修改。
判断元素是否存在，习惯使用 in，而非 index 方法。
>>> 2 in [1, 2]
True
至于删除操作，可用索引序号指定某个元素，或切片指定删除某个范围的元素。
>>> a = [1, 2, 3, 4, 5]
>>> del a[4] # 删除单个元素
>>> a
[1, 2, 3, 4]
>>> del a[1:3] # 删除某个范围内的元素
>>> a
[1, 4]
通过切片的方式创建新的列表对象时，会复制相关的指针数据到新数组。除了所引用的目标相同外，对列表自身的修改（插入、删除等）互不影响。
>>> a = [0, 2, 4, 6]
>>> b = a[:2]
>>> a[0] is b[0] # 复制引用，依然指向同一对象
True
>>> a.insert(1, 1) # 对 a 列表操作，不会影响 b
>>> a
[0, 1, 2, 4, 6]
>>> b
[0, 2]
复制的是指针（引用），而非目标元素对象。
对列表自身的修改互不影响，但对目标元素对象的修改是共享的。
利用 bisect 模块，可向有序列表插入元素。它使用二分法查找适合的位置，可以用来实现优先级队列或一致性哈希算法。
>>> d = [0, 2, 4]
>>> import bisect
>>> bisect.insort_left(d, 1) # 插入新元素后，依然保持有序状态
>>> d
[0, 1, 2, 4]
>>> bisect.insort_right(d, 3)
>>> d
[0, 1, 2, 3, 4]
自定义复合类型，可通过重载比较运算符（ __eq__、__lt__ 等）实现自定义排序条件。
元组
尽管两者并没有直接关系，但在操作方式上，元组可被当作列表的只读版本使用。
因元组是不可变类型，它的指针数组无须变动，故一次性完成内存分配。系统会缓存复用一定长度的元组内存（含指针数组）。创建时，按所需长度提取复用，没有额外的内存分配。从这一点上来看，元组的性能要好于列表。
Python 3.6 缓存复用长度在 20 以内的 tuple 内存，每种 2000 上限。
# IPyton
>>> %timeit [1, 2, 3]
53.7 ns ± 1.49 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit (1, 2, 3)
12.9 ns ± 0.027 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)
元组支持与列表类似的运算符操作，但不能修改，每次操作都是返回新的对象。
>>> a = [1, 2, 3]
>>> id(a)
4529921800
>>> a += [4, 5]
>>> id(a)
4529921800
>>> b = (1, 2, 3)
>>> id(b)
4537321872
>>> b += (4, 5)
>>> id(b)
4537253648
列表因为支持插入、删除等修改操作，所以序号无法与元素对象构成固定映射。但元组不同，相同序号总是返回同一对象，故可为序号取个“别名”(namedtuple)。
>>> import collections
>>> User = collections.namedtuple("User", "name,age") # 创建 User 类型，指定字段
>>> issubclass(User, tuple) # tuple 子类
True
>>> user = User("Min", 22)
>>> user.name, user.age # 使用字段名访问
('Min', 22)
>>> user[0] is user.name # 或依旧使用序号
True
对于自定义纯数据类型，显然 namedtuple 要比 class 简介。关键在于，名字要比序号可读性更强并且更易维护，其类似于数字常量维护。
数组
数组与列表、元组的本质区别在于：元素单一类型和内容嵌入。详细使用方式请看：8.7. array — Efficient arrays of numeric values
>>> import array
>>> a = array.array("b", [0x11, 0x22, 0x33, 0x44])
>>> memoryview(a).hex() # 使用内存视图查看，内容嵌入而非指针
'11223344'
>>> a = array.array("i")
>>> a.append(100)
>>> a.append(1.23)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: integer argument expected, got float
数组可直接存储包括 Unicode 字符在内的各种数字。
但复合类型须用 struct、marshal、pickle 等转换为二进制字节后再进行存储。
数组于列表类似，长度不固定，按需扩张或收缩内存。
>>> a = array.array("i", [1, 2, 3])
>>> a.buffer_info() # 返回缓冲区的内存地址和长度
(4480106800, 3)
>>> a.extend(range(100000)) # 追加大量内容后，内存地址和长度发生变化
>>> a.buffer_info()
(4487446528, 100003)
由于可指定更紧凑的数字类型，故数组可节约更多内存。再者，内容嵌入也避免了对象的额外开销，减少了活跃对象的数量和内存分配的次数。