链表中使用二重指针的优点有什么

yanwb0613

回复 1# aomw10


   刚看到这个问题，跟lz一样对这个问题有疑问

   个人理解，只是为了省一次"."操作：

   如果使用* prev, 那么插入时，  this->prev.next = this;
   如果使用** prev, 那么则为，   this->prev = this。

   说白了，插入，删除时，我们只需要修改前一节点的next指针，而不会修改它的prev和value
   那么prev直接指向前一节点的next元素即可，不需要指向结点本身，再"."到它的next元素

\\

int-main

如9楼说的，因为要修改的是一级指针本身，所以需要二级指针，而不是省不省的问题。

captivated

回复 1# aomw10

            这是为了方便链表遍历。

            一般的链表是这样子滴：
                               header
                                     |
                                  ________                  ________              ________
                                 | next  |     ---->      | next |     ---->   | next |  ----> NULL
              NULL <---- | prev  |     <----      | prev |     <----   | prev |
                                 -----------                   ------------             ------------
             如果我要遍历链表，只能从header开始遍历。


             LZ的结构，链表是酱紫的：
                                  ________                     ________                ________
                                 | next  |     -------->     | next |     ------>  | next |  ----> NULL
              NULL <---- | prev  |                       | prev |                 | prev |
                                 -----------                       ------------              ------------
                                           \                          /         \                      /   
                                               ___________                 ___________
                                               | header1 |                 | header2 |
            这样，任意节点的prev都指向header，我只要能取到一个节点(的内容)，就可以通过这个节点的prev(而不需要知道此节点的地址)，从此节点开始来前/后遍历链表。

            不好意思啊，手边没有做图工具，将就看吧...

            PS，个人浅见，如果弄错了欢迎拍砖。

MMMIX

看有些链表中定义的item，并非使用 *next, *prev,

而是向前指针使用二重指针

类似如下这种：
struct ...
aomw10 发表于 2011-06-21 20:24

这是 Minix 3 内核代码 kernel/proc.c 中给出的解释：

1. 
   
2. * The code here is critical to make everything work and is important for the
   
3. * overall performance of the system. A large fraction of the code deals with
   
4. * list manipulation. To make this both easy to understand and fast to execute
   
5. * pointer pointers are used throughout the code. Pointer pointers prevent
   
6. * exceptions for the head or tail of a linked list.
   
7. *
   
8. *  node_t *queue, *new_node;        // assume these as global variables
   
9. *  node_t **xpp = &queue;         // get pointer pointer to head of queue
   
10. *  while (*xpp != NULL)         // find last pointer of the linked list
    
11. *      xpp = &(*xpp)->next;        // get pointer to next pointer
    
12. *  *xpp = new_node;                // now replace the end (the NULL pointer)
    
13. *  new_node->next = NULL;        // and mark the new end of the list
    
14. *
    
15. * For example, when adding a new node to the end of the list, one normally
    
16. * makes an exception for an empty list and looks up the end of the list for
    
17. * nonempty lists. As shown above, this is not required with pointer pointers.
    
18. */
    

复制代码

captivated

回复 2# cobras


    是这样用的么...

    我还以为是
    father -> next = this;
    this -> prev = &father;

    为什么
    father->next = this;
    this->prev = &father->next; // 这样不是prev指向this自己了么？

captivated

回复 14# MMMIX


    就是说，方便在链表的最后插入节点。
    通常，在链表尾插入节点需要遍历整个链表。但是这个不用。

captivated

回复 14# MMMIX


    擦... 不是... 他给出的示例代码还是遍历了整个链表。
    他的意思是说，不用处理链表是不是空链表的情况，同样的代码都能用。

captivated

回复 14# MMMIX


    他还说，不管你从前面插入，还是从后面插入，感觉是一样的{:3_183:}

    其实，童鞋们觉得... 从前面插入与从后面插入，感觉一样吗？{:3_189:}

captivated

回复 2# cobras


    哦 又看了下 是修改节点指针，你那样用也有...

    尼玛，纠结。

ai616818

谢谢9L，学习