简单遍历链表的指针到指针技术是什么[[副本]

单链表 或者 树形结构 . 其思想是,一旦找到结束点(空指针),就不需要特殊情况或“尾随指针”跟随遍历指针。因为您可以将指针解引用到一个指针(它 到最后一个节点的下一个指针!)插入。像这样:

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

我想你是说 doubly-linked lists 其中节点类似于:

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容器来处理你的列表脏活的评论。然而,这是堆栈溢出,我们都在这里学习一些东西。

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

你可能是指一个双链接列表,其中一个指针向前,另一个指针向后。这允许您访问给定节点的下一个和上一个节点,而不必记住遇到的最后一个或两个节点(如在单链表中)。

但我发现的一件事使代码更加 更多 总是 作用于列表中间的节点。

例如,创建空列表:

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:如果你在进行空间仍然很重要的嵌入式编程,这可能不是一个可行的解决方案(尽管现在有些嵌入式环境也相当单调)。