与数组比较
链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。
链表与顺序表的操作复杂度:
顺序表 | 单链表 | 双链表 | |
---|---|---|---|
访问元素 | O(1) | O(n) | O(n) |
头部插入/删除 | O(n) | O(1) | O(1) |
尾部插入/删除 | O(1) | O(n) | O(1) |
中间插入/删除 | O(n) | O(n) | O(n) |
注意虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。
存储类别 | 顺序存储结构 | 链表 |
---|---|---|
存储分配方式 | 用一段连续的存储单元依次存储线性表的数据元素 | 采用链式存储结构,用一组任意的存储单元存放线性表的元素 |
时间性能 | 查找O(1)、插入和删除O(n) | 查找O(n)、插入和删除O(1) |
空间性能 | 需要预分配存储空间,大了浪费,小了上溢 | 不需要预先分配存储空间 |
附Python代码
import time
class SingleLinklist:
...
...
# 单链表头部插入
start = time.time()
a = SingleLinklist()
for i in range(1000):
a.add(i)
end = time.time()
print('LinkList Run ',end-start,' s!')
# 顺序表头部插入
start = time.time()
a = []
for i in range(1000):
a.insert(0,i)
end = time.time()
print('List Run ',end-start,' s!')
## 输出
LinkList Run 0.21707868576049805 s!
List Run 7.2271728515625 s!