第三章列表、拷贝和切片

type

status

date

slug

summary

Python内建常用数据结构

序列 sequence

字符串str、字节序列bytes、bytearray
列表list、元组tuple

键值对 mapping

集合set、字典dict

可变对象和不可变对象

不可变对象：在不改变该对象内存地址的前提下, 对该对象所指向的内存中的值不能被改变。当改变某个变量时候，由于其所指的值不能被改变，相当于把原来的值复制一份后再改变，这会开辟一个新的地址，变量再指向这个新的地址。

• 可变对象：在不改变该对象内存地址的前提下, 对该对象所指向的内存中的值可以被改变。变量（准确的说是引用）改变后，实际上是其所指的值直接发生改变，并没有发生复制行为，也没有开辟新的出地址，通俗点说就是原地改变。

线性数据结构简介

线性表

线性表（简称表），是一种抽象的数学概念，是一组元素的序列的抽象，它由有穷个元素组成，包含顺序表和链接表。

顺序表：使用一整块连续的内存顺序存储表中的元素，这样实现的表称为顺序表，或称连续表。由于顺序表的在内存中的存储是连续的，故可以通过索引0,1,2…来访问顺序表中元素。

链接表：在存储空间中将分散存储的元素链接起来，这种实现称为链接表，简称链表。链表是线性结构，内存分布上看着不连续，但是内部有指向，前一个元素指向下一个元素，所以它是有明确的顺序。

列表如同地铁站排好的队伍，有序，可以插队、离队，可以索引。

链表如同操场上手拉手的小朋友，有序但排列随意。或者可以想象成一串带线的珠子，随意盘放在桌上。也可以离队、插队，也可以索引。

第二章列表 list

一个排列整齐的队伍，Python采用顺序表实现

列表内的个体称作元素，由若干个元素组成列表

元素可以是任意对象（数字，字符串，对象，列表等）

列表内元素有顺序，可以使用索引

线性的数据结构

使用[]表示

列表是可变的

2.1 初始化及增删改查

2.1.1 初始化

list()函数是Python的内置函数。它可以将任何可迭代数据转换为列表类型，并返回转换后的列表。当参数为空时，list函数可以创建一个空列表。

1. 参数必须是可迭代序列对象。list函数的参数必须是可迭代对象。

2. 无意义的转换——将列表转换为列表。

2.1.2 访问列表元素(索引)

访问列表中的单个元素是通过列表索引方式实现的，list[index]。列表索引支持正索引0~length-1，同时支持负索引-length~-1，索引不可以越界，超界抛出IndexError.在索引的基础上, 可以使用切片的方式访问列表中的多个元素, list[start_index:end_index:step], 步长表示

性能：使用索引可以直接定位列表中的元素，时间复杂度为O(1),效率最高。(O(n)表示时间复杂度是常数，与数据规模n无关，不会随着数据规模n增加而影响效率)

list[index]

访问列表的index索引对应的元素

list[start_index : end_index]

访问列表的从第start_index到第end_index-1索引的连续多个元素

list[start_index : end_index : step]

访问列表的从第start_index到第end_index-1的等间隔为step的多个元素

注：正负索引之间可以相互转化，负索引+长度转正索引；正索引-长度转负索引

2.1.3 查询

list.index(value,[start,[stop]])

通过value值，查找值在列表中的正索引，返回第一个匹配值的索引，匹配不到抛异常，推荐使用in判断替代这个方法。
参数start和stop为索引值(包左不包右)，表示从指定位置开始到指定位置结束进行匹配,

list.count(value)

统计value值在列表中的出现的次数

性能：index和count方法的都需要遍历元素，效率随着数据规模增加而变差，他们的时间复杂度为O(n)，实际编程中不推荐使用。

len(list)

查看列表的长度，时间复杂度为O(1)

in 操作

if [3,4] in [1,2,3,[3,4]]:
for x in [1,2,3,4,5]:

2.1.4 元素修改及索引的相关操作

list[index] = value 修改list列表中index索引对应值为value, 可以实现列表元素的增, 删, 改以及另一个列表的拼接.

注：索引不能超界

2.1.5 添加对象

单个对象添加

list.append(object) 尾部添加一个对象（单个元素or列表等），无返回值，就地修改

list.insert(index,value) 按索引插入单个对象（单个元素or列表等）

多个对象添加

list.extend(iterable) 尾部通过可迭代对象扩展列表,无返回值,就地修改

list1 + list2 → new_list 两列表拼接，生产新列表

本质上调用的是魔术方法__add__()方法

list * num → new_list list列表重复num次，拼接成新列表（复制原理，浅拷贝）

append()方法没有返回值，没有返回值往往表示他自己被改变了，就地修改。其效率高吗？一般情况下，定位追加尾部的时间复杂度为O(1),相当于list[lenght] = value.效率较高。但是列表作为容器是有容量的，当容量满了之后，列表会自动扩大（先会给初始大小容量，不够了扩容，扩增2倍）扩容耗时，如果内存连续空间不够，牵扯到了垃圾回收，效率就低了。

list.insert(index,value) 元素插入到index对应位置的前面。则index = 0时，元素插入到首部。index = length-1时，插入在列表末尾元素前面。而如果index = length时，超出了右边界，插入在列表末尾元素后面，相当于append。左边界也可以超，不妨试一试。效率：插入点之后所有数据向后挪动，效率低下。

重难点：

在Python中一切皆对象，而对象都是引用类型，可以理解为一个地址指针指向这个对象。但是，字面常量字符串、数值等表现却不像引用类型，暂时可以理解为简单类型。而列表、元组、字典，包括以后学习的类和实例都可以认为是引用类型。你可以认为简单类型直接存放在列表中，而引用类型只是把引用地址存放在了列表中。

2.1.6 元素删除

list.remove(value) → None

从左至右查找第一个匹配value的值，并删除该元素，返回None，否则ValueError
效率：O(n)，需要遍历元素，效率低，不推荐。

del list[index]

按照索引删除列表对应的值
del list[i:n] 也可以删除列表第i+1到第n个连续元素
效率：O(1)，对于列表中元素删除操作，推荐用del语句。

list.pop([index]) → item

弹出元素并返回被弹出元素
无index，默认弹出尾部元素，有index，弹出index对应元素
效率：有index时，O(n)，弹出元素后，其余元素挪动，效率的低，无index时弹出尾部，O(1)

list.clear() → None

清空列表中所有元素，返回空列表[]
效率较高，但危险操作，不推荐使用

2.1.7 元素排序

list.reverse() → None

将列表反转；就地修改，返回None
最好不用，可以倒着读取，都不要反转list[::-1]

list.sort([key = None],[reverse=False]) → None

就地修改，返回None
参数reverse默认False，升序排序，True降序；参数key = str，表示元素都转化成str类型进行比较，如果存在int，float等不同类型需要在一起排序用

sort方法会对列表重新排序, 是原位置修改, 没有返回值, 或者说返回值为None. 如果不想对原列表进行修改, 又能达到实现对列表进行某种方式的排序, 然后返回生成一个新列表, 那么此时可以使用sorted函数.

2.1.8 浅拷贝和深拷贝（重理解, 面试题）

shadow copy(浅拷贝) ：

对可变类型: 新开辟一块内存，遇到引用数据类型只拷贝元数据的首地址，通过原数据的首地址去获取内容（相当建立快捷方式）
对不可变类型: 不会给拷贝的对象开辟新的内存, 而只是拷贝了该对象的引用.(和普通的变量赋值效果一样)

deep copy(深拷贝)：

对可变类型: 新开辟一块内存，遇到引用数据类型将被拷贝内容全部拷贝过来（直接独立复制）
对不可变类型: 不会给拷贝的对象开辟新的内存, 而只是拷贝了该对象的引用.(和普通的变量赋值效果一样)

一般情况下，大多数语言提供的默认复制行为都是浅拷贝。

2.1.9 对列表的就地修改

对于列表这类可变对象来说, 调用append, insert, sort或reverse这些原位置修改的运算, 一定是对列表做原位置修改, 但这些方法在列表修改后并不会返回列表.事实上, 它们返回的是None对象,.如果你把这类运算的结果赋值给原先的变量名, 那么只会失去该列表(这列表很可能在此过程中被垃圾回收).

2.2 常见线性结构比较

链表 Linked，栈 Stack，队列 Queue

列表 List

append 尾部添加效率高
insert 中间插入，会引起挪动，效率低
extend 扩展，成批扩展，高
+ 拼接
* 复制原理，浅拷贝

remove 按照value删除，遍历，中间移走，后面数据挪动
pop 弹出，使用索引定位快，后面挪动数据效率低。pop()尾部弹出可以使用
clear 效率高，危险动作

list[index] = value 效率高

index count 都需要遍历，都不高
len O(1)

遍历

O（n）不高

2.3 切片

对于线性结构，可以通过for… in迭代，能通过len(x)获取长度，也可以通过整数下标访问元素，分正索引和负索引。能索引即可切片。

切片的时间复杂度为O(n)，详看后面切片的本质介绍。

通过给定的索引区间获得线性结构的一部分数据

start、stop、step为整数，可以是正整数、负整数、0

start为0时可忽略,stop为末尾可忽略。list[:] 表示全部。

注：关于末尾是由步长正负决定的，正则末尾在右边，负则末尾在左边。故下面x[8::-2] 返回不为空。

2.3.1 正负索引转化

-index + length = +index

+index - length = -index

2.3.2 切片本质

切片为合并本类型对象，然后返回一个新对象。实际上是一个浅拷贝过程（详见2.1.8）。

讨论

上面两种迭代都能实现列表的倒序遍历，但是通过切片形式实现，会多出来拷贝步骤，在数据规模大时不推荐

2.3.3 切片赋值（了解）

切片操作写在等于号左边

被插入的可迭代对象写在等号右边

z = list()、y[:]=x等价于z=x[:]，都是创建x的副本。

切片赋值用作初始化相当于copy，还可以使用。如果用在替换、插入元素，看似语法比较简洁，但是由于列表是顺序表结构，将会引起数据的挪动非常影响性能，应当尽量避免使用。

2.4 在遍历中修改列表的问题

2.4.1 问题产生

上面代码产生疑惑的原因用三句话概括:

不管for循环依次访问的是列表的value还是index, 底层都是按照索引的原理对列表进行访问的

在访问时对列表进行修改, 那么for循环下一次访问列表对象是修改后的列表对象(对动态变化的对象实时访问)

for 循环的索引逻辑永远都是从0开始然后1, 2, 3依次递进, 而不会因为被访问对象的内容变化而变化.

2.4.2 解决方法

解法1：

对列表的中间元素进行删除，后面元素索引自动减一，在while中索引i在遇到删除一个元素时，同步i-1即可

while循环会比基于迭代器的for循环运行速度慢很多（迭代器在Python内部是以C语言的速度运行的，而while循环版本则是通过Python虚拟机运行Python字节码的）

如果可以，尽可能使用for循环来处理数据。

解法2：

在for循环中运用列表索引的浅拷贝原理，遍历浅拷贝过来的元素，删除原列表中元素。对原列表的修改不会影响遍历的结果。

不过列表复制会新开辟一个空间，如果需要操作的对象比较大，显然这种方法是不友好的

解法3：

对列表进行倒序遍历，那么对遍历到的元素即使删除，也不会影响列表前面的元素的索引。

既不会额外开辟空间，浪费内存资源，同时也能以C语言的执行速度处理数据，大样首推此法。

对线性解构一边倒序遍历一边做修改的思想，在Excel自动化中也有这重要的应用

2.4.3 效率问题

2.5 作业

😀

答案

1、打印九九乘法表，要求上下行对其，左右间距对其（进阶：3行代码实现）

2、打印菱形

3、求杨辉三角第n行第k列的值

2.6 列表进阶

2.6.1 列表比较（了解）

两列表之间是可以实现≤, ≥, <, ==, >等比较的，比较原则如下

从开头逐一比较元素大小，直到找到不相等元素位置

如果两列表所有元素都相等，则长度大的列表大

返回True、False

2.6.2 多维列表(了解)

列表元素本身可以是列表，因此可以用列表构建矩阵。

上面代码可以看成构建了一个三行三列的二维矩阵，可以使用下面代码索引二维矩阵的单个元素。

list_name[row_index][column_index]

更进一步，我们可以使用列表推导式来创造任意多维的矩阵，下面构建一个30x20x25的三维列表。