- A+

链表 不是一块连续的空间,它是通过“指针”将一组零散的内存块串联起来使用。
我们来看看链表与数组的差异

很明显,数组在内存中是一连串相邻的区域组成的,而链表则是由不连续的指针而组成的。
链表的分类
链表分为最常见的三种类型:单链表、循环链表和双向链表。
单链表

单链表如图所示,除了data中存储数据结构以外,还有一个next元素,为指向下一个节点内存地址的后继指针。单链表有两个特殊节点,一个是头节点,一般可以使用头节点循环遍历整个单链表。一个是尾节点,尾节点属于单链表的最后一个节点,所以一般为null。
单链表的插入和删除
数组在插入与删除操作时(由于是一连串的内存地址)需要进行一些列的搬迁工作,所以效率很低,时间复杂度为O(n)但是链表的插入和操作,只需要更改相邻节点的指针,时间复杂度为O(1),所以很高效。

循环链表
循环链表其实是一个特殊的单链表,它与单链表的区别就是尾节点,我们知道单链表的尾节点为null,而循环链表的尾节点对应链表的头节点,形成了一个循环的状态,所以称为循环链表。

双向链表
它有两个方向的指针,分别是前驱指针指向前一个节点,与后继指针指向后面一个节点。

双向链表由于多一个指针用来指向前一个节点,所以势必会在空间上比单链表占用更多内存,但是双向链表可以支持在O(1)复杂度下找到前驱节点,所以在某种情况下,删除与插入比单链表更加高效,简单。
双向循环链表
顾名思义就是双向链表的循环版本,尾节点的next指针指向头节点的data元素,头节点的前驱节点prev指向尾节点的data元素。

链表与数组的性能对比

如上图
数组由于是一连串的内存空间,所以在进行元素插入和删除时,往往会进行数据搬移工作,这样就会造成性能上的损耗,所以时间复杂度为O(n),而数组在访问某一个元素时,可以通过下标位置访问元素单元,不需要进行循环查找,所以时间复杂度为O(1)。
链表在是一连串不连续的内存空,在元素插入和删除时,可以通过元素的前驱节点或者后继节点直接查询到元素的所在位置,可以通过更改元素的前驱节点或者后续节点的指针指向,所以时间消耗几乎很小,对性能影响微乎其微,所以时间复杂度为O(1),而在查找元素时恰恰与数组相反,链表需要通过头节点,依次遍历所有节点查找元素,故时间复杂度为O(n)。
所以,在项目中,要根据场景的不同,择优选择是使用数组还是链表。
如何写好正确的链表代码?
一 、理解指针或引用
将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。
例如: p -> next = q 这段代码的意思就是 p节点中的next指针存储了q节点的内存地址。
p -> next = p -> next -> next 这段代码的意思就是 p节点的next指针存储了p节点的下下一个节点的内存地址。
二、警惕指针丢失和泄露
插入节点时,要注意操作的顺序
删除节点时,要手动释放内存空间
三、利用哨兵简化难度
哨兵节点,在任何时候,不管链表是不是空,head指针都会一直指向这个哨兵节点,把这种带有哨兵节点的链表叫做带头链表。相反,没有哨兵节点的链表叫做不带头链表。

四、重点留意边界条件处理
在写链表代码时一定要注意边界问题,如果不处理边界问题可能引起程序抛出空指针异常甚至崩溃。此处总结几点需要注意的地方
- 如果链表为空时,代码是否能正常工作
- 如果链表只包含一个节点时,代码是否能正常工作
- 如果链表只包含两个节点时,代码是否能正常工作
- 代码在处理头节点和尾节点时,是否能正常工作
五、举例画图,辅助思考
六、多写多练,反复思考
5个常见链表操作
单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点
- 我的微信
- 加好友一起交流!
-
- 微信公众号
- 关注公众号获取分享资源!
-
2019年6月21日 下午6:44 沙发
good good study, day day up…
2019年6月21日 下午6:46 板凳
good good study, day day up
2019年6月21日 下午6:49
@小小名 加油!