[TOC]

列表

存储结构

在Python中，列表（List）是一种动态数组。

列表的存储结构是基于数组实现的，每个元素在内存中都是连续存储的。

当创建一个列表时，Python会为其分配一块连续的内存空间来存储元素，列表的长度可以根据需要动态增长或缩小，如果该列表没有连续的内存空间剩余，则会在内存其他空闲位置重写开辟一块内存，并深复制到其中。

还会分配另外一块内存空间来存储索引数组。索引数组中的每个元素对应着相应元素在列表内存空间中的位置。

  • 时间复杂度

    在列表末尾调用pop时，操作是常数阶的，在列表头一个元素或中间某处调用pop时，则是n阶的

    image-20230905121647246

切片

列表切片是通过创建一个新的列表对象，然后浅拷贝其中的元素。但列表中的元素仍然是原始列表中元素的引用。修改切片后的列表元素也会影响到原始列表的对应位置元素，因为它们指向的是同一个内存地址。这意味着对于带嵌套的列表，其中的复合对象无法做到数据隔离。

1
2
3
4
5
6
7
8
9
10
11
# 切片(浅拷贝)
original_list = [1, 2, 3, 4, 5]
sliced_list = original_list[1:4]

print(original_list)  # 输出: [1, 2, 3, 4, 5]
print(sliced_list)  # 输出: [2, 3, 4]

sliced_list[0] = 99

print(original_list)  # 输出: [1, 2, 3, 4, 5]
print(sliced_list)  # 输出: [99, 3, 4]

列表可以通过copy方法实现深拷贝，它能逐层拷贝列表，实现数据隔离。

1
2
3
4
5
6
7
8
9
10
original_list = [1, 2, 3, 4, 5]
copied_list = original_list.copy()  #或者使用 copied_list = list(original_list)

print(original_list)  # 输出: [1, 2, 3, 4, 5]
print(copied_list)  # 输出: [1, 2, 3, 4, 5]

copied_list[0] = 99

print(original_list)  # 输出: [1, 2, 3, 4, 5]
print(copied_list)  # 输出: [99, 2, 3, 4, 5]

字典

存储结构

字典（Dictionary）是一种无序的键值对集合，它的存储结构是基于哈希表（Hash Table）实现的

哈希表是一种高效的数据结构，它通过将键（Key）映射到一个唯一的索引位置来实现快速的查找和插入操作。在字典中，每个键都必须是唯一的，而值（Value）可以是任意类型的对象。

当创建一个字典时，Python会为其分配一块内存空间来存储键值对。字典的长度可以根据需要动态增长或缩小，这使得字典非常灵活。

  • 时间复杂度

image-20230905170410714