用于更简单地遍历链表的指针指向技术是什么?

十年前，有人向我展示了一种遍历链表的技术:您使用了双指针(pointer-to-pointer)而不是单指针.

该技术无需检查某些边界/边缘情况，从而生成更小、更优雅的代码.

有人知道这个技术到底是什么吗?

解决方案

我认为你的意思是双指针，就像指向一个指针的指针"一样，这对于在单向链表的末尾插入非常有效

strong> 或树结构.这个想法是，一旦找到结尾(空指针)，您就不需要特殊情况或尾随指针"来跟随您的遍历指针.因为您可以将指针取消引用到要插入的指针(它指向 到最后一个节点的下一个指针！).像这样:

T **p = &list_start;而 (*p) {p = &(*p)->next;}*p = 新 T;

而不是这样的:

T *p = list_start;如果(p == NULL){list_start = 新 T;} 别的 {而(p->下一个){p=p->下一个；}p->next = 新 T;}

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

Ten years ago, I was shown a technique for traversing a linked list: instead of using a single pointer, you used a double pointer (pointer-to-pointer).

The technique yielded smaller, more elegant code by eliminating the need to check for certain boundary/edge cases.

Does anyone know what this technique actually is?

解决方案

I think you mean double pointer as in "pointer to a pointer" which is very efficient for inserting at the end of a singly linked list or a tree structure. The idea is that you don't need a special case or a "trailing pointer" to follow your traversal pointer once you find the end (a NULL pointer). Since you can just dereference your pointer to a pointer (it points to the last node's next pointer!) to insert. Something like this:

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

instead of something like this:

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

NOTE: It is also useful for making efficient removal code for a singly linked list. At any point doing *p = (*p)->next will remove the node you are "looking at" (of course you still need to clean up the node's storage).