链表总结

链表分类

链表主要分为一下几类:

• 单链表
• 循环链表
• 双链表

​

各个链表比较

开发中最常用的链表就是 循环双链表

循环链表和单链表对比起来，循环链表有如下几个优点:

• 通过任意一个节点即可以遍历所有的节点

单链表和双链表对比起来，双链表有如下几个优点:

• 可以轻松获取一个节点的前后节点
• 双链表的删除和插入节点效率更高更方便
• 双链表遍历更方便，可以从一个节点开始可以往前往后遍历

​

链表和数组的比较

随机访问

数组支持随机访问，随机访问的时间复杂度为O(1)，但是链表不支持随机访问，如果要访问指定位置的节点必须遍历前面所有的节点，时间复杂度为O(n)

查找元素

链表和数组查找元素的时间复杂度都是O(n) ，但是对于一个有序的数组可以使用二分查找来加快速度，此时时间复杂度为O(logn)，但是对于链表就没有办法进行二分了

对于元素的插入和删除，链表的时间复杂度为O(1)，而数组则为O(n)，因为数组需要进行元素的移动，链表只需要改变指针即可

总结

如果是需要频繁进行随机访问的时候可以使用数组，如果需要频繁进行增加和删除则可以考虑使用链表