用于更简单地遍历链表的指针对指针技术是什么? [英] What is the pointer-to-pointer technique for the simpler traversal of linked lists?

问题描述

十年前，向我展示了一种遍历链接列表的技术:您没有使用单个指针，而是使用了双指针(指针到指针).

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?

推荐答案

我认为您的意思是在指向指针的指针"中使用双指针，这对于在单链接列表的末尾插入非常有效或树结构.这样的想法是，一旦找到结束符(NULL指针)，就不需要特殊情况或跟踪指针"来跟随遍历指针.由于您只需将指针取消引用到要插入的指针(它指向，指向最后一个节点的下一个指针！)即可.像这样:

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;

而不是像这样的东西:

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都会删除您正在查看"的节点(当然，您仍然需要清理该节点的存储).

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).

这篇关于用于更简单地遍历链表的指针对指针技术是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！