最近翻出了之前学Python时的笔记，正好把列表、元组、集合、字典这四大基础容器重新梳理了一遍。这里整理一下重温的内容，暂时不涉及其他序列或容器类型。需要说明的是，当前看到的源码是基于Python 3.16版本。

列表

列表其实就是我们常说的数组，也就是方括号 [] 括起来的那一串。和普通数组最大的区别在于——它是可以修改的。在Python底层，列表存储的是一个连续的指针数组，每个指针指向实际存储内容的地址。正因如此，Python列表才能同时塞进不同类型的数据。

 复制代码struct PyListObject { 
    PyObject_VAR_HEAD 
    PyObject *ob_item[]; // 指针数组：每个元素存对象地址 
    Py_ssize_t ob_allocated; // 分配总容量（预留空间） 
};

列表增长方式

Python列表自带自动扩缩容机制，具体实现可以参考源码中 list_resize 方法（line 104）。当数组增长时，它会自动调用这个方法分配新的内存空间。增长方式很有意思，不是简单的翻倍，而是走一条平滑的曲线：0, 4, 8, 16, 24, 32, 40, 52, 64, 76……

 复制代码new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

新容量大致按这个公式计算：

• newsize：实际需要的元素数
• newsize >> 3：额外加上 1/8 的余量
• + 6：小列表时再多给一点空间
• & ~3：向下对齐到 4 的倍数

所以最终的容量大约是 1.125 倍加上一个常数，这样既能保证扩容效率，又不会浪费太多内存资源。

列表的方法

（参考源码 list_methods[]，line 3597）

• append(x)
• clear()
• copy()
• count(x)
• extend(iterable)
• index(x[, start[, stop]])
• insert(i, x)
• pop([i])
• remove(x)
• reverse()
• sort(*, key=None, reverse=False)

append(x)

向列表末尾添加元素 x。源码实现在 list_append_impl（line 1232）。

 复制代码    list.append(a)

 复制代码list1 = ['a', 'b', 'c']  
list1.append('d')  
print ("更新后的列表 : ", list1)
# 更新后的列表 :  ['a', 'b', 'c', 'd']

clear()

清空列表中的所有元素。源码实现在 list_clear_impl（line 873）。

 复制代码    list.append(a)

 复制代码
list1 =  ['a', 'b', 'c', 'd']
list1.clear()
print ("列表清空后 : ", list1)
# 列表清空后:[]

copy()

复制列表。源码实现在 list_slice_lock_held（line 696）。

 复制代码    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }

 复制代码
list1 =  ['a', 'b', 'c', 'd']
liest2 = list1.copy()
print ("list2列表 : ", list2)
#  list2列表 ：['a', 'b', 'c', 'd']

本质上是创建了一个新的内存空间，然后把每个元素逐一复制进去。因为用的是赋值操作（=），所以如果列表里面还嵌套了列表，那这就只是浅拷贝。

来看个例子：

 复制代码a=[0,1,2,3,4,5]
b=a
c=a.copy()del a[1]  
'''
   各变量值为：
   a=[0, 2, 3, 4, 5]
   b=[0, 2, 3, 4, 5]
   c=[0, 1, 2, 3, 4, 5]
'''b.remove(4)
'''
   各变量值为：
   a=[0, 2, 3, 5]
   b=[0, 2, 3, 5]
   c=[0, 1, 2, 3, 4, 5]
'''
c.append(9)
'''
   各变量值为：
   a=[0, 2, 3, 5]
   b=[0, 2, 3, 5]
   c=[0, 1, 2, 3, 4, 5, 9]
'''

这里能清楚看到，a和b的修改是互相影响的——因为b = a 只是把a的内存地址复制给了b，所以两者指向同一块内存。而使用 copy() 会创建新的内存地址，再把老列表的内容逐一复制进去，所以 c 和 a、b 的变化毫无关系。

但问题来了：如果列表里面套了数组或对象，copy() 就只能管到第一层，里面的嵌套内容它管不了。

 复制代码x = []
a = [x]
b = a.copy()   # 浅拷贝
x.append(1)
# a == [[1]], b == [[1]]

那怎么才能做到每层都拷贝到呢？有两种方式：

方法一：直接用标准库

 复制代码import copy; 
copy.deepcopy(obj)

方法二：手写一个深拷贝函数

 复制代码#手写深拷贝
def deep_copy(obj, memo=None):
    # memo：缓存已经拷贝过的对象，解决循环引用
    if memo is None:
        memo = {}    # 如果该对象已经拷贝过，直接返回副本，避免循环引用死循环
    if id(obj) in memo:
        return memo[id(obj)]    # 1. 基础不可变类型，直接返回自身
    basic_types = (int, float, str, bool, type(None))
    if isinstance(obj, basic_types):
        return obj    # 2. 列表
    if isinstance(obj, list):
        new_list = []
        memo[id(obj)] = new_list  # 先存入缓存，处理内部循环引用
        for item in obj:
            new_list.append(deep_copy(item, memo))
        return new_list    # 3. 字典
    if isinstance(obj, dict):
        new_dict = {}
        memo[id(obj)] = new_dict
        for k, v in obj.items():
            new_dict[deep_copy(k, memo)] = deep_copy(v, memo)
        return new_dict    # 4. 集合
    if isinstance(obj, set):
        new_set = set()
        memo[id(obj)] = new_set
        for item in obj:
            new_set.add(deep_copy(item, memo))
        return new_set    # 5. 元组（不可变，但内部有可变元素也要递归拷贝）
    if isinstance(obj, tuple):
        temp = [deep_copy(item, memo) for item in obj]
        new_tuple = tuple(temp)
        memo[id(obj)] = new_tuple
        return new_tuple    # 6. 自定义类实例通用拷贝
    if hasattr(obj, "__dict__"):
        # 创建空实例
        new_obj = obj.__class__()
        memo[id(obj)] = new_obj
        # 递归拷贝所有属性
        for attr_name, attr_val in obj.__dict__.items():
            setattr(new_obj, attr_name, deep_copy(attr_val, memo))
        return new_obj    # 其他不识别对象直接返回原对象
    return obj

count()

计算列表中某个元素出现的次数，本质就是 for 循环遍历计数。源码在 list_count_impl（line 3366）。

 复制代码aList = [123, 'Google', 'Runoob', 'Taobao', 123];  
  
print ("123 元素个数 : ", aList.count(123))  
print ("Runoob 元素个数 : ", aList.count('Runoob'))'''
123 元素个数 :  2
Runoob 元素个数 :  1
'''

extend()

在列表末尾追加新的可迭代内容。实际逻辑在 _list_extend，入口是 list_extend_impl（line 1457）。

 复制代码
list1 = ['a', 'b', 'c']
list2=list(range(5)) # 创建 0-4 的列表
list1.extend(list2)  # 扩展列表
print ("扩展后的列表：", list1)
# 
扩展后的列表： ['a', 'b', 'c', 0, 1, 2, 3, 4]

 复制代码# 语言列表
language = ['French', 'English', 'German']
 
# 元组
language_tuple = ('Spanish', 'Portuguese')
 
# 集合
language_set = {'Chinese', 'Japanese'}
 
# 添加元组元素到列表末尾
language.extend(language_tuple)
 
print('新列表: ', language)
 
# 添加集合元素到列表末尾
language.extend(language_set)
 
print('新列表: ', language)

这里有个细节：如果 extend 里面传入的是字典，它会按照字典的迭代顺序，把 key 依次追加到列表尾部。

 复制代码a = [1, 2]
d = {"x": 10, "y": 20}
a.extend(d)
# a == [1, 2, "x", "y"]

index(x[, start])

返回 x 在列表中第一次出现的下标（可以在 start:stop 范围内查找）。找不到就抛出 ValueError。源码在 list_index_impl（line 3325），本质就是通过 for 循环逐个比较内容来取下标。

 复制代码
list1 = ['a', 'b', 'c']
print ('a 索引值为', list1.index('a'))
print ('b 索引值为', list1.index('b'))
'''
a 索引值为 0
b 索引值为 1
'''
list1 = ['a', 'b', 'c', 'd', 'e']  
# 从指定位置开始搜索  
print ('b 索引值为', list1.index('b',1))# b 索引值为 1

insert(i, x)

源码在 list_insert_impl（实际调用 ins1，line 1183）。在下标 i 处插入元素 x，原下标 i 及后面的所有元素整体向后移位一位，原地修改列表。

• 先判断当前分配容量 allocated 是否还有空位；
• 无空位则调用 list_resize 自动扩容；
• 使用内存拷贝，把 i 到末尾的指针整体向后挪一格；
• 把新元素指针写入 ob_item[i]，长度 +1

 复制代码lst = ['a', 'b', 'c']
# 下标0插入元素
lst.insert(0, 'start')
print(lst)  # ['start', 'a', 'b', 'c']# 下标2插入
lst.insert(2, 'mid')
print(lst)  # ['start', 'a', 'mid', 'b', 'c']# 插入到末尾，等价 append()
lst.insert(len(lst), 'end')
print(lst)  # ['start', 'a', 'mid', 'b', 'c', 'end']# 下标超出长度，自动插在最后
lst.insert(999, 'last')
print(lst)
'''
['start', 'a', 'b', 'c']
['start', 'a', 'mid', 'b', 'c']
['start', 'a', 'mid', 'b', 'c', 'end']
['start', 'a', 'mid', 'b', 'c', 'end', 'last']
'''

pop([i])

源码在 list_pop_impl（line 1326）。删除并返回下标 i 对应的元素；不传参数则默认删除最后一位。

• pop()：直接取最后一个元素，长度 -1，均摊 O(1)；
• 指定下标 pop(i)：取出元素后，i+1 到末尾的指针整体向前移位；
• 删除后如果实际长度不足分配容量的一半，会触发缩容释放内存。

 复制代码lst = [10, 20, 30, 40]
# 默认删末尾
res1 = lst.pop()
print(res1, lst)  # 40 [10, 20, 30]# 删除下标1
res2 = lst.pop(1)
print(res2, lst)  # 20 [10, 30]# 下标不存在抛 IndexError
# lst.pop(99)

remove(x)

源码在 list_remove_impl（line 1403）。原地删除列表中第一个匹配 x 的元素；遍历完没找到则抛出 ValueError。

• 从头 for 循环遍历列表，逐个对比元素；
• 找到第一个匹配项后，后续元素指针前移覆盖；
• 找不到直接抛出异常

 复制代码lst = [2, 5, 3, 5, 1]
lst.remove(5)
print(lst)  # [2, 3, 5, 1]# lst.remove(99)  # ValueError: list.remove(x): x not in list

reverse()

源码在 list_reverse_impl（line 3276）。原地反转列表元素顺序，无返回值，不生成新列表。

实现方式就是双指针：左指针从头、右指针从尾，交换两边指针指向的值，直到两指针相遇。

 复制代码lst = [1, 2, 3, 4]
lst.reverse()
print(lst)  # [4, 3, 2, 1]# 对比切片反转（生成新列表，不修改原列表）
lst2 = [1, 2, 3]
new_lst = lst2[::-1]
print(lst2, new_lst)  # [1,2,3] [3,2,1]

sort(*, key=None, reverse=False)

源码在 list_sort_impl（line 3424）。原地稳定排序，无返回值。

 复制代码nums = [5, 2, 9, 1]
nums.sort()
print(nums)  # [1, 2, 5, 9]nums.sort(reverse=True)
print(nums)  # [9, 5, 2, 1]# key 自定义排序
words = ["banana", "apple", "pear"]
# 按字符串长度排序
words.sort(key=lambda s: len(s))
print(words)  # ['pear', 'apple', 'banana']