数据结构与算法--02链表-如何轻松写出链表代码
写好链表并不是件容易的事情,尤其是一些复杂的链表操作,如链表反转、有序链表合并等等。即使能够写出代码,但及其容易出错。所以付出一定量的精力是前提条件,另外还需要掌握一些必要的技巧。
1.理解指针或引用的含义
有些语言如C语言,具有指针的概念,而其他语言如Java、Python则使用“引用”来代替指针。但本质上都一样,都是存储所指对象的内存地址。
所谓指针的使用,其实就是将某个变量的地址赋值给指针,或者可以理解为指针中存储了该变量的内存地址,通过指针就能找到该变量。
链表中指针的使用:
- p->next = q,表示p点的next指针存储了q结点的内存地址。
- p->next = p->next->next,表示p结点的next指针存储了p结点的下下一个结点的内存地址。
2.注意指针丢失和内存泄漏
例如插入链表结点的操作:
p->next = x;
x->next = p->next;
上述代码完成第1行代码后,已经指向了结点想。第2行相当于将x赋值给了x->next,自己指向了自己,因此整个链表断开为两半,发生指针丢失和内存泄漏。把上述1、2行代码代码互换即可:
x->next = p->next;
p->next = x;
删除链表结点与插入同理。
对于C语言,内存管理是有程序员负责的,需要手动释放内存空间。而像Java这种虚拟机自动管理内存的编程语言来说,就不需要考虑这么多了。
3.利用哨兵简化实现难度
针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。但这样代码实现起来就会很繁琐,不简洁。那么我们使用“哨兵”来解决这个问题。
我们这里说的哨兵也是解决“边界问题”的,不直接参与业务逻辑。在任何时候,不管链表是不是空,head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反,没有哨兵结点的链表就叫作不带头链表。
4.重点留意边界条件处理
在编写完一段代码后,我们需要对边界问题进行检查,以保证代码的稳定性。那么链表的边界条件有以下几个:
- 如果链表为空
- 如果链表只宝行一个结点
- 如果链表只宝行两个结点
- 代码逻辑在处理头结点和尾结点的情况
5.举例画图,辅助思考
在实现每一个复杂需求之前,最好先通过画图的形式梳理整个逻辑流程,然后看图写代码就会容易很多。而且遇到bug时,解决起来也会方便很多。
6.多写多练
多些多练,孰能生巧。几个常见的链表操作。
- 单链表反转
- 链表中环的检测
- 两个有序链表的合并
- 删除链表倒数第n个结点
- 求链表的中间结点
以上只是对链表操作进行的技巧总结,剩下的就是实战敲代码练习了。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)