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

问题描述

我学习 SYS / queue.h FreeBSD和我有一个问题：

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

在 SYS / queue.h ， LIST_ENTRY 定义如下：

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

为什么它维护的 previous的地址下一个元素（结构类型** le_ $ P $光伏），而不是简单地 previous elment 如结构类型* le_ $ p $光伏？

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

推荐答案

如果您已经阅读从一开始queue.h文件，可能会
已经得到以下评论：

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.

那么列表，它提供的O（1）的插入和缺失，
但只能向前遍历。要做到这一点，你只需要
参考previously下一个指针，这到底是什么
实施

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维持previous下一个元素的地址？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！