顺序表、链表与字典的区别

	顺序表	链表
存储空间	连续地分配空间。预先分配，可能闲置或溢出	动态地分配空间，不会闲置或溢出
存储密度	1	小于1，每个节点的指针域需额外占用存储空间
存取元素	随机存取，按位置访问元素的时间复杂度为 $O(1)$	顺序存取（非随机），按位置访问元素的时间复杂度为 $O(n)$ 。查找一个元素时，需要从开始节点一个个查找
插入、删除	平均需要移动表中约一半元素， $O(n)$	不需移动元素，确定插入、删除位置后，只需改变指针指向， $O(1)$
适用场景	需要频繁查找，很少插入或删除；事先知道大致长度	频繁插入或删除，很少查找；元素个数变化较大

操作	时间复杂度	说明
index[]	$O(1)$	按索引直接定位
index[] = a	$O(1)$	按索引直接赋值
append()	$O(1)$	在尾部追加
pop()	$O(1)$	从尾部往外弹
pop(i)	$O(n)$	从指定位置弹出，n是列表长度。O(n)为在头部弹出的最坏情况
insert(i, item)	$O(n)$	从指定位置插入，n是列表长度。O(n)为在头部插入的最坏情况
contains (in)	$O(n)$	遍历一遍列表，看指定值是否在列表中
get slice [x:y]	$O(k)$	定位到x是O(1)，然后一个个取，取到y前面，共k个元素
del slice	$O(n)$	删除中间的切片后，后面的元素需要全部往前移
set slice	$O(n+k)$	先删除，再补充
concatenate	$O(k)$	连接。在尾部添加是O(1)，添加k个
sort	$O(nlogn)$	与排序算法有关
multiply	$O(nk)$	k是乘的次数