为什么 sys/queue.h 中的双向链表会维护前一个元素的地址? [英] Why does the doubly linked list in sys/queue.h maintain the address of previous next element?

问题描述

I'm studying sys/queue.h from FreeBSD and I have one question:

In sys/queue.h, LIST_ENTRY is defined as follows:

#define LIST_ENTRY(type)                        
struct {                                
    struct type *le_next;   /* next element */          
    struct type **le_prev;  /* address of previous next element */  
}

Why does it maintain the address of previous next element (struct type **le_prev) rather than simply previous elment like struct type *le_prev?

解决方案

If you would have read the queue.h file from the beginning, you may have got following comment:

 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.

so list, which provides O(1) insertion and deletion, but only forward traversal. To achieve this, you only need the reference to the previously next pointer, which is exactly what is implemented.

这篇关于为什么 sys/queue.h 中的双向链表会维护前一个元素的地址?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！