c++ - 更简单的链表遍历的指针对指针技术是什么？

Question

十年前，我看到了一种遍历链表的技术:您使用的是双指针(指针对指针)，而不是使用单指针。

通过消除检查某些边界/边缘情况的需要，该技术产生了更小、更优雅的代码。

有人知道这种技术到底是什么吗？

Answer 1

我认为您的意思是“指向指针的指针”中的双指针，这对于在单链表或树结构的末尾插入非常有效。这个想法是，一旦找到结尾(NULL 指针)，您就不需要特殊情况或“尾随指针”来跟随您的遍历指针。因为您可以将指针取消引用到要插入的指针(它指向 到最后一个节点的下一个指针!)。像这样的:

T **p = &list_start;
while (*p) {
   p = &(*p)->next;
}
*p = new T;

而不是这样的:

T *p = list_start;
if (p == NULL) {
    list_start = new T;
} else {
    while (p->next) {
        p = p->next;
    }
    p->next = new T;
}

注意:它对于为单链表制作有效的删除代码也很有用。在任何时候执行 *p = (*p)->next 都会删除您正在“查看”的节点(当然您仍然需要清理节点的存储)。