什么是指针链接列表更简单遍历的指针技术？
十年前，我看到了一种遍历链表的技术：使用双指针（指向指针），而不是使用单个指针。
通过消除检查某些边界/边缘情况的需要，该技术产生了更小，更优雅的代码。
有谁知道这种技术究竟是什么？
我认为你的意思是指向“指针指针”的双指针，它非常有效地插入单链表或树结构的末尾。 我们的想法是，一旦找到结束（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会删除你正在“查看”的节点（当然你还需要清理节点的存储）。
通过“双指针”，我认为你的意思是“指向指针”。 这很有用，因为它允许您消除头部或尾部指针的特殊情况。 例如，给定此列表：
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; } }
我认为你的意思是双链表 ，其中一个节点是这样的：
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 }
我同意有关使用STL容器处理列表脏工作的意见。 然而，这就是Stack Overflow，我们都在这里学习一些东西。
以下是通常插入列表的方法：
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; }
请注意您必须执行的所有额外检查，具体取决于插入是在列表的开头，结尾还是中间。 与双指针方法对比：
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; }
正如Evan Teran所指出的，这适用于单链表，但是当它双重链接时，你最终会经历与单指针情况一样多的操作。 另一个缺点是你要经历每次遍历的两个指针解引用。 虽然代码看起来更干净，但它可能不像单指针代码那样快速运行。
你可能意味着一个双向链表，其中一个指针前进而另一个指向后退。 这允许您到达给定节点的下一个和上一个节点，而不必记住遇到的最后一个或两个节点（如在单链接列表中）。
但是我发现的使代码更优雅的一件事是始终在列表中有两个虚拟元素，第一个和最后一个。 这样可以消除插入和删除的边缘情况，因为您始终在列表中间的节点上执行操作。
例如，创建一个空列表：
first = new node last = new node first.next = last first.prev = null last.next = null last.prev = first // null <- first <-> last -> null
显然，遍历列表略有修改（仅显示转发版本）：
curr = first.next while curr <> last: do something with curr curr = curr.next
插入更简单，因为您不必关心是否在列表的开头或结尾插入。 要在当前点之前插入：
if curr = first: raise error add = new node add.next = curr add.prev = curr.prev curr.prev.next = add curr.prev = add
删除也更简单，避免边缘情况：
if curr = first or curr = last: raise error curr.prev.next = curr.next curr.next.prev = curr.prev delete curr
所有非常清晰的代码，代价是每个列表只需要维护两个额外的节点，而不是当今巨大的内存空间环境中的巨大负担。
警告1：如果您正在进行嵌入式编程，而空间仍然可能很重要，这可能不是一个可行的解决方案（尽管现在某些嵌入式环境也非常繁琐）。
警告2：如果您使用的语言已经提供了链接列表function，那么最好这样做而不是自己动手（除了非常具体的情况）。