算法-实现链表代码

发表于   |   分类于   |  

理解指针或引用的含义

对于指针的理解可以用一句话概括

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

比如下面的代码

p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

警惕指针丢失和内存泄露（单链表）

插入结点

如下图结构

linked_listx

假设在结点A和结点B之间插入一个结点X，目前A结点的下一个结点是结点B，而当前指针P指向结点A。造成指针丢失和内存泄露的代码如下

1
2
P->next = X;
X->next = P->next;

显然这会导致结点X的后继指针指向自身。为什么？在操作的时候，链表是连续的还没有中断，而指针P指向的是结点A，此时结点A的下一个结点还是结点B，当执行了第一段代码 P->next = X; 相当于把A结点的下一个结点指向了节点X，这里是没有问题的，关键是下一行代码 X-next = P->next; 需要注意的是 P->next 经过第一步的操作后变为了结点X，此时在赋值给 X->next 相当于给结点X的下一个结点指向的还是结点X，因此整个链表就会中断掉，从结点B开始以后的节点都不能访问了。

现在只需要把2行代码换个位置即可解决问题。也就是

1
2
X->next = P->next;
P->next = X;

这样写就是先给结点B前面增加了一个结点X，然后在把结点A的下一个结点指向结点X，这样就完成了链表的结点插入。

利用 “哨兵” 简化链表实现

什么是哨兵

链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。

哨兵处理

如果在p节点后插入一个节点，只需2行代码即可搞定：

1
2
new_node—>next = p—>next;
p—>next = new_node;

但，若向 空链表 中插入一个节点，则代码如下：

1
2
3
if (head == null) {
	head = new_node;
}

如果要删除节点p的后继节点，只需1行代码即可搞定： p—>next = p—>next—>next; 但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：

1
2
3
if (head—>next == null) {
	head = null;
}

从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入 哨兵 节点来解决这个问题。

哨兵结点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点都可以统一为相同的代码实现逻辑了。因为在逻辑上是第一个结点，而实际实现上我们其实已经有一个哨兵结点在内了，所以就不存在空的情况了，所有的结点操作都是一样的 无需额外的判断。

linked_listx2

哨兵应用场景

哨兵最大的作用就是简化边界条件的处理。别的不知道了。

链表边界处理

经常用来检查链表是否正确的边界4个边界条件：

1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个节点时，代码是否能正常工作？
3.如果链表只包含两个节点时，代码是否能正常工作？
4.代码逻辑在处理头尾节点时是否能正常工作？

同样平时写代码的时候也可以用这4个问题来检查自己的代码

-------------The End-------------