链表的概念
链表和数组的区别：
两者的区别：
- 数组静态分配内存，链表动态分配内存。
- 数组在内存中是连续的，链表是不连续的。
- 数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素，查找的时间复杂度是O(N)。
- 数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删除不需要移动其他元素，时间复杂度是O(1)。
数组的优点
- 随机访问性比较强，可以通过下标进行快速定位。
- 查找速度快
数组的缺点
- 插入和删除的效率低，需要移动其他元素。
- 会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合适，就会造成内存的浪费。
- 内存空间要求高，创建一个数组，必须要有足够的连续内存空间。
- 数组的大小是固定的，在创建数组的时候就已经规定好，不能动态拓展。
链表的优点
- 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
- 内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。
链表的缺点
查找的效率低，因为链表是从第一个节点向后遍历查找。
单链表和双链表的区别：
- 单链表的每一个节点中只有指向下一个结点的指针，不能进行回溯，适用于节点的增加和删除。
- 双链表的每一个节点给中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点，适用于需要双向查找节点值的情况。
双链表相对于单链表的优点：
链表环问题
判断是否有环
定义一个快指针和一个慢指针，快指针一次走两步，慢指针一次走两步，会出现两种情况，情况一指针走到了空的位置，那就说明这个链表不带环。情况二两个指针相遇，说明这个链表带环。
获得入环节点
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/205282.html原文链接：https://javaforall.net
