链表
2021-05-03 本文已影响0人
张_何
-
动态数组有个明显的缺点就是可能会造成内存空间大量浪费（每次数组的扩容都是以当前的容量剩以一个系数重新申请内存的）。链表就不会有上述缺点
-
链表是一种链式存储的线性表。所有元素的内存地址不一定是连续的
image.png
-
链表中第一个元素中的节点称为头结点，最后一个元素中的节点称为尾结点，单向链表中尾结点存放的内容是空
-
判断一个链表中是否有环：
1、采用快慢指针思想，如同两个人在操场跑步，一个跑的快一个跑的慢，那么两人总会再重逢 -
双向链表
image.png
-
双向链表和动态数组比较
image.png
-
单向循环链表
image.png
image.png
-
双向循环列表
image.png
