单链表删除节点的技巧

单链表删除节点的技巧

     -- 注：删除节点非尾节点！
 

---

在此分享一个小小技巧，在单向链表中删除节点时不必知道其前面节点（若存在前面节点的话），亦可高效地完成删除节点。

===

从一篇别人的博文说起吧，引用自这里，内容很少，仅此如下：

标题：学习数据结构的感想

在链表中删除动作比较多的时候，用双联表比用单链表效率要高，双链表不用从头开始遍历去删除，而是可以直接删除。

用单链表删除的时候，每次知道需要删除元素的前一个指针就好了。不过这个好像很难知道。

我是在无意之间，看到那位朋友的上面问题，先是无意间网上搜到他转载了我的一篇博文《STL稳定排序源码分析》，好奇之下到了他的csdn博客的。

所以我就一时兴致勃勃回复了其问题，与之讨论，内容如下：

===

单向链表删除节点时候，可做到不需要知道（若有的话）上一个节点同样完成删除操作。你可以这么做，描述如下：
原来的链表 ... A -> B[b_ptr] -> C[c_ptr] -> D[d_ptr] ...

现在要删除节点 B，其对于指针为b_ptr（注：删除节点非尾节点，重要）。

首先你可以使用B得到C，D指针，c_ptr和d_ptr，然后你可以用C去覆盖掉B，即*b_ptr = *c_ptr，那么这时你可以删除C即可达到你要的结果即删除节点B。具体操作：
*b_ptr = *c_ptr;
b_ptr->next = d_ptr;
delete c_ptr;

结果的链表 ... A -> C[b_ptr] -> D[d_ptr] ...

按照以上的操作，这样就不需要从头去遍历链表定位上一个节点A了，简单有效吧☺。

===

但是，删除节点不应该为尾节点（链表的最后一个节点），因为B作为尾节点，虽然你可以删除节点B，但无法给节点A的next赋值NULL。若删除的节点为尾节点，那就得老老实实从头遍历链表了，将其前面节点A的next赋NULL。

===

当然你说的“用双（向）链表比用单链表效率要高”，是对的。确切说应该叫实用性高吧，但是其实现的逻辑要复杂不少，可参见STL链表的实现源码。像C++ STL里面的链表（包括单向双向）底层的实现都是以双向链表形式的。可以参考sgi stl源码，std::list，std::slist。

（完）