如何完成一个链表

Ruby的简单的单链表实例：

# 单链表节点
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:指的就是将node1的next引用到（指向）node2节点的value的内存地址，从而实现链表结构。

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

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

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 ，这样才不会丢失指针，导致内存泄漏。

nodeX.next = node1.next
node1.next = nodeX 

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

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

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

需要对头节点进行判断

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

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

node1.next = node1.next.next

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

if node3.next == null do
  node3 = null
end

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

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

带头链表

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

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

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

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

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

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

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

---