python学习笔记（10）算法（3）列表

一、列表

列表（list）是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历
等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。
‧ 链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。
‧ 数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。
当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要
存储多少数据，从而难以选择合适的列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则
会造成内存空间浪费。
为解决此问题，我们可以使用动态数组（dynamic array）来实现列表。它继承了数组的各项优点，并且可以
在程序运行过程中进行动态扩容。
实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的，例如 Python 中的 list 、Java 中的
ArrayList 、C++ 中的 vector 和 C# 中的 List 等。在接下来的讨论中，我们将把“列表”和“动态数组”视
为等同的概念。

1.初始化列表

我们通常使用“无初始值”和“有初始值”这两种初始化方法：

nums=[]

nums=[1,2,3,4,5]

2.访问元素

列表本质上是数组，因此可以在 𝑂(1) 时间内访问和更新元素，效率很高。

# 访问元素
num = nums[1]
# 访问索引 1 处的元素
# 更新元素
nums[1] = 0
# 将索引 1 处的元素更新为 0

3.插入与删除元素

相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 𝑂(1) ，但插入和删除
元素的效率仍与数组相同，时间复杂度为 𝑂(𝑖) 。

# 清空列表
nums.clear()
# 在尾部添加元素
nums.append(1)
nums.append(3)
nums.append(2)
nums.append(5)
nums.append(4)
# 在中间插入元素
nums.insert(3, 6)
# 在索引 3 处插入数字 6
# 删除元素
nums.pop(3)
# 删除索引 3 处的元素

4.遍历列表

与数组一样，列表可以根据索引遍历，也可以直接遍历各元素。

# 通过索引遍历列表
count = 0
for i in range(len(nums)):
count += nums[i]
# 直接遍历列表元素
for num in nums:
count += num

5.拼接列表

给定一个新列表 nums1 ，我们可以将其拼接到原列表的尾部。

nums1= [6, 8, 7, 10, 9]
nums += nums1
# 将列表 nums1 拼接到 nums 之后

6.排序列表

完成列表排序后，我们便可以使用在数组类算法题中经常考查的“二分查找”和“双指针”算法。

nums.sort()
# 排序后，列表元素从小到大排列

7.补充

python学习笔记（11）算法（4）列表补充-CSDN博客