用于更简单地遍历链表的指针对指针技术是什么? [英] 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屋!