列表
- 一个队列，一个排序整齐的队伍
- 列表内的个体称为元素，由若干元素组成列表
- 元素可以是任意对象（数字，字符串，对象，列表等）
- 列表内元素有顺序，可以使用索引
- 线性的数据结构
- 使用[]表示
- 列表是可变的
列表、链表、queue（队列）、stack（栈）的差异
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
queue
队列是一种特殊的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
stack
栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。
由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。
列表list定义 初始化
- list() -> new empty list
- list(iterable) -> new list initialized from iterable's items
- 列表不能一开始就定义大小
列表查询
-
index(value, [start, [stop]])
- 通过值value，从指定区间查找列表内的元素是否匹配
- 匹配第一个就立即返回索引
- 匹配不到，抛出异常ValueError
-
count(value)
- 返回列表中匹配value的次数
-
时间复杂度
- index和count方法都是O(n)
- 随着列表数据规模的增大，而效率下降
列表增加、插入元素
-
append(object) -> None
- 列表尾部追加元素，返回None
- 返回None就意味着没有新的列表产生，就地修改
- 时间复杂度是O(1)
-
insert(index, object) -> None -- insert object before index
在制定的索引index出插入元素object
返回None就意味着没有新的列表产生，就地修改
时间复杂度是O(n)
-
索引
- 超过上界，尾部追加5
- 超过下届，头部追加
-
extend(iterable) -> None -- extend list by appending elements from the iterable
将可迭代对象的元素追加进来，返回None
就地修改
-
+ -> list
- 连接操作，将两个列表连接起来
- 产生新的列表，原列表不变
- 本质上调用的是add()方法
-
* -> list
- 重复操作，将本列表元素重复n次，返回新的列表
列表删除元素
-
remove(value) -> None -- remove first occurrence of value.
- 从左至右查找第一个匹配value的值，移除该元素，返回None
- 就地修改
- 效率O(n)，每删除一个元素其后面的元素都要往前移动
-
pop([index]) -> item -- remove and return item at index (default last).
- 不指定索引index，就从列表尾部弹出一个元素
- 指定索引index，就从索引出弹出一个元素，索引超界抛出IndexError错误
- 效率O(1)，指定索引的时间复杂度O(n)，不指定索引O(1)
-
clear() -> None -- remove all items from L
- 清除列表所有元素，剩下一个空列表
