什么是指针链接列表更简单遍历的指针技术？

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将删除你"看"的节点(当然你仍然需要清理节点的存储).

Answer 2

通过"双指针",我认为你的意思是"指向指针".这很有用,因为它允许您消除头部或尾部指针的特殊情况.例如,给定此列表:

struct node {
    struct node *next;
    int key;
    /* ... */
};

struct node *head;

如果要搜索节点并将其从列表中删除,单指针方法将如下所示:

if (head->key == search_key)
{
    removed = head;
    head = head->next;
}
else
{
    struct node *cur;

    for (cur = head; cur->next != NULL; cur = cur->next)
    {
        if (cur->next->key == search_key)
        {
            removed = cur->next;
            cur->next = cur->next->next;
            break;
         }
    }
}

而指针指针方法更简单:

struct node **cur;

for (cur = &head; *cur != NULL; cur = &(*cur)->next)
{
    if ((*cur)->key == search_key)
    {
        removed = *cur;
        *cur = (*cur)->next;
        break;
    }
}