如何完成一个链表
Varsion

Ruby的简单的单链表实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 单链表节点
class Node
attr_accessor :value , :next
def initialize(value)
@value = value # 节点值
@next = nil # 指向下个节点
end
end

# 新建节点
node1 = Node.new(1)
node2 = Node.new(2)
node3 = Node.new(3)

# 连接节点
node1.next = node2
node2.next = node3

方法一:理解指针或引用的含义

有些语言有“指针”的概念,比如 C 语言;有些语言没有指针,取而代之的是“引用”,比如 Java、Python。不管是“指针”还是“引用”,实际上,它们的意思都是一样的,都是存储所指对象的内存地址

对于指针或引用的理解,

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量

node1.next = node2:指的就是将node1next引用到(指向)node2节点的value的内存地址,从而实现链表结构。

方法二:警惕指针丢失或内存泄漏

使用单链表实例来展示指针丢失的情况,参考上面的代码,我们现在又ndoe1->node2->node3三个节点,现在在node1node2之间插入nodeX节点

1
2
3
4
nodeX = Node.new('x')

node1.next = nodeX # node1的next指向X
nodeX.next = node1.next # X的next指向node2

一般来讲的错误,是第二步直接进行 nodeX.next = node1.next 因为此时,node1.next 已经是 nodeX 了相当于自己指向自己,整个链表也就断成了两半,从 nodeX 往后的所有结点都无法访问到了。

对于有些语言来说,比如 C 语言,内存管理是由程序员负责的,如果没有手动释放结点对应的内存空间,就会产生内存泄露。

所以,插入结点时,应当要注意操作的顺序,要先将结点 x 的 next 指针指向结点 node2 ,再把结点 node1 的 next 指针指向结 nodeX ,这样才不会丢失指针,导致内存泄漏。

1
2
nodeX.next = node1.next
node1.next = nodeX

同理,删除链表结点时,也一定要记得手动释放内存空间,否则,也会出现内存泄漏的问题。当然,对于像 Java 这种虚拟机自动管理内存的编程语言来说,就不需要考虑这么多了。

方法三:利用哨兵简化实现难度

当我们要向一个空链表中插入第一个结点,刚刚的代码逻辑就不能用了。

需要对头节点进行判断

1
2
3
if head == null do
head = Node.new('value')
end

删除结点时,操作边的更为简单了。删除node2节点

1
node1.next = node1.next.next

但是,如果要删除链表的末尾结点,仍然需要进行判断

1
2
3
if node3.next == null do
node3 = null
end

所以,针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这里,引入“哨兵”的概念,这里说的哨兵也是解决“边界问题”的,不直接参与业务逻辑

如果我们引入哨兵结点,在任何时候,不管链表是不是空,head 指针都会一直指向这个哨兵结点。把这种有哨兵结点的链表叫带头链表。相反,没有哨兵结点的链表就叫作不带头链表

带头链表

哨兵结点是不存储数据的。因为哨兵结点一直存在,所以插入第一个结点和插入其他结点,删除最后一个结点和删除其他结点,都可以统一为相同的代码实现逻辑了。

实际上,这种利用哨兵简化编程难度的技巧,在很多代码实现中都有用到,比如插入排序、归并排序、动态规划等。

方法四:重点留意边界条件处理

软件开发中,代码在一些边界或者异常情况下,最容易产生 Bug。链表代码也不例外。要实现没有 Bug 的链表代码,一定要在编写的过程中以及编写完成之后,检查边界条件是否考虑全面,以及代码在边界条件下是否能正确运行。

经常用来检查链表代码是否正确的边界条件有这样几个:

  • 如果链表为空时,代码是否能正常工作?
  • 如果链表只包含一个结点时,代码是否能正常工作?
  • 如果链表只包含两个结点时,代码是否能正常工作?
  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?

当完成链表代码之后,除了看下你写的代码在正常的情况下能否工作,还要看下在上面我列举的几个边界条件下,代码仍然能否正确工作。如果这些边界条件下都没有问题,那基本上可以认为没有问题了。


  • Post title:如何完成一个链表
  • Post author:Varsion
  • Create time:2020-08-01 18:47:22
  • Post link:https://blog.varsion.cn/post/da9173bf.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments