| 顺序表 | 链表 | |
|---|---|---|
| 存储空间 | 连续地分配空间。预先分配，可能闲置或溢出 | 动态地分配空间，不会闲置或溢出 |
| 存储密度 | 1 | 小于1，每个节点的指针域需额外占用存储空间 |
| 存取元素 | 随机存取，按位置访问元素的时间复杂度为 |
顺序存取（非随机），按位置访问元素的时间复杂度为 |
| 插入、删除 | 平均需要移动表中约一半元素， |
不需移动元素，确定插入、删除位置后，只需改变指针指向， |
| 适用场景 | 需要频繁查找，很少插入或删除；事先知道大致长度 | 频繁插入或删除，很少查找；元素个数变化较大 |
列表内置操作的时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| index[] | 按索引直接定位 | |
| index[] = a | 按索引直接赋值 | |
| append() | 在尾部追加 | |
| pop() | 从尾部往外弹 | |
| pop(i) | 从指定位置弹出，n是列表长度。O(n)为在头部弹出的最坏情况 | |
| insert(i, item) | 从指定位置插入，n是列表长度。O(n)为在头部插入的最坏情况 | |
| contains (in) | 遍历一遍列表，看指定值是否在列表中 | |
| get slice [x:y] | 定位到x是O(1)，然后一个个取，取到y前面，共k个元素 | |
| del slice | 删除中间的切片后，后面的元素需要全部往前移 | |
| set slice | 先删除，再补充 | |
| concatenate | 连接。在尾部添加是O(1)，添加k个 | |
| sort | 与排序算法有关 | |
| multiply | k是乘的次数 |
字典内置操作的时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| copy | 所有元素都考贝一份 | |
| get item | 通过键可以直接取到值 | |
| set item | 设置 | |
| delete item | 删除某个字典元素 | |
| contains (in) | 包含 |
