引入
我们基本学习了如何创建、删除、插入、修改一个单链表,那么单链表跟顺序表比真的高效嘛?单链表又适用于什么情况呢?单链表跟顺序表的优缺点呢?我们一起来看看!
效率观察
我们发现,无论是插入还是删除单链表中的元素,其实就分两步
- 遍历查找第 i 个元素
- 实现插入和删除
从算法的角度很容知道它们的时间复杂度都是 O(n);
那么单链表和顺序表岂不是都一样了?既然都是 O(n),那链表的优势在哪呢?
对比
从第 i 个位置开始,连续插入10个元素
对于顺序存储结构
- 没插入一个都要移动 n-i 个位置
- 每次都是 O(n)
对于链表
- 找到第 i 个位置的指针,此时时间复杂度为 O(n)
- 接下来的赋值移动指针的时间复杂度为 O(1)
所以,对于删除和操作频繁
的操作,单链表
的效率就越高。