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

This question already has an answer here:

这个问题在这里已有答案：

An interesting C linked list idiom 11 answers
一个有趣的C链表成语11个答案

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?

有谁知道这种技术究竟是什么？

5 个解决方案

#1

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:

我认为你的意思是指向“指针指针”的双指针，它非常有效地插入单链表或树结构的末尾。我们的想法是，一旦找到结束（NULL指针），就不需要特殊情况或“尾随指针”来跟踪遍历指针。因为您可以将指针取消引用指向要插入的指针（它指向最后一个节点的下一个指针！）。像这样的东西：

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

注意：它对于为单个链接列表制作有效的删除代码也很有用。在任何时候做* p =（* p） - > next会删除你正在“查看”的节点（当然你还需要清理节点的存储）。

#2

By "double-pointer", I think you mean "pointer-to-pointer". This is useful because it allows you to eliminate special cases for either the head or tail pointers. For example, given this list:

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

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

struct node *head;

If you want to search for a node and remove it from the list, the single-pointer method would look like:

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

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;
         }
    }
}

Whereas the pointer-to-pointer method is much simpler:

而指针指针方法更简单：

struct node **cur;

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

#3

I think you mean doubly-linked lists where a node is something like:

我认为你的意思是双链表，其中一个节点是这样的：

struct Node {
(..) data // The data being stored in the node, it can be of any data type
Node *next; // A pointer to the next node; null for last node
Node *prev; // A pointer to the previous node; null for first node
}

#4

I agree with the comments about using the STL containers for handling your list dirty work. However, this being Stack Overflow, we're all here to learn something.

我同意有关使用STL容器处理列表脏工作的意见。然而，这就是Stack Overflow，我们都在这里学习一些东西。

Here's how you would normally insert into a list:

以下是通常插入列表的方法：

typedef struct _Node {
    void * data;
    Node * next;
} Node;

Node * insert( Node * root, void * data ) {
    Node * list = root;
    Node * listSave = root;

    while ( list != null ) {
        if ( data < list->data ) {
            break;
        }

        listSave = list;
        list = list->next;
    }

    Node * newNode = (Node*)malloc( sizeof(Node) );
    newNode->data = data;
    /* Insert at the beginning of the list */
    if ( listSave == list ) {
        newNode->next = list;
        list = newNode;
    }
    /* Insert at the end of the list */
    else if ( list == null ) {
        listSave->next = newNode;
        newNode->next = null;
        list = root;
    }
    /* Insert at the middle of the list */
    else {
        listSave->next = newNode;
        newNode->next = list;
        list = root;
    }

    return list;
}

Notice all the extra checking you have to do depending on whether the insertion occurs at the beginning, end or middle of the list. Contrast this with the double pointer method:

请注意您必须执行的所有额外检查，具体取决于插入是在列表的开头，结尾还是中间。与双指针方法对比：

void insert( Node ** proot, void * data ) {
    Node ** plist = proot;

    while ( *plist != null ) {
        if ( data < (*plist)->data ) {
            break;
        }

        plist = &(*plist)->next;
    }

    Node * newNode = (Node *)malloc( sizeof(Node) );
    newNode->data = data;
    newNode->next = *plist;
    *plist = newNode;
}

As Evan Teran indicated, this works well for singly linked lists, but when it's doubly linked, you end up going through just as many if not more manipulations as the single pointer case. The other draw back is that you're going through two pointer dereferences for each traversal. While the code looks cleaner, it probably doesn't run as quickly as the single pointer code.

正如Evan Teran所指出的，这适用于单链表，但是当它双重链接时，你最终会经历与单指针情况一样多的操作。另一个缺点是你要经历每次遍历的两个指针解引用。虽然代码看起来更干净，但它可能不像单指针代码那样快速运行。

#5

You probably mean a doubly-linked list, with one of the pointers going forward and the other going backward. This allows you to get to the next and previous nodes for a given node without having to remember the last one or two nodes encountered (as in a singly-linked list).

你可能意味着一个双向链表，其中一个指针前进而另一个指向后退。这允许您到达给定节点的下一个和上一个节点，而不必记住遇到的最后一个或两个节点（如在单链接列表中）。

But the one thing I discovered which made the code even more elegant was to always have two dummy elements in the list at all times, the first and the last. This gets rid of the edge cases for insertion and deletion since you're always acting on a node in the middle of the list.

但是我发现的使代码更优雅的一件事是始终在列表中有两个虚拟元素，第一个和最后一个。这样可以消除插入和删除的边缘情况，因为您始终在列表中间的节点上执行操作。

For example, an empty list is created:

例如，创建一个空列表：

first = new node
last = new node
first.next = last
first.prev = null
last.next = null
last.prev = first
// null <- first <-> last -> null

Obviously, traversing the list is slightly modified (forward version shown only):

显然，遍历列表略有修改（仅显示转发版本）：

curr = first.next
while curr <> last:
    do something with curr
    curr = curr.next

The insertions are much simpler since you don't have to concern yourself with whether you're inserting at the start or end of the list. To insert before the current point:

插入更简单，因为您不必关心是否在列表的开头或结尾插入。要在当前点之前插入：

if curr = first:
    raise error
add = new node
add.next = curr
add.prev = curr.prev
curr.prev.next = add
curr.prev = add

Deletions are also simpler, avoiding the edge cases:

删除也更简单，避免边缘情况：

if curr = first or curr = last:
    raise error
curr.prev.next = curr.next
curr.next.prev = curr.prev
delete curr

All very much cleaner code and at the cost of only having to maintain two extra nodes per list, not a great burden in today's huge memory space environments.

所有非常清晰的代码，代价是每个列表只需要维护两个额外的节点，而不是当今巨大的内存空间环境中的巨大负担。

Caveat 1: If you're doing embedded programming where space still might matter, this may not be a viable solution (though some embedded environments are also pretty grunty these days).

警告1：如果您正在进行嵌入式编程，而空间仍然可能很重要，这可能不是一个可行的解决方案（尽管现在某些嵌入式环境也非常繁琐）。

Caveat 2: If you're using a language that already provides linked list capabilities, it's probably better to do that rather than roll your own (other than for very specific circumstances).

警告2：如果您使用的语言已经提供了链接列表功能，那么最好这样做而不是自己动手（除了非常具体的情况）。

#1

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