Tại sao danh sách được liên kết kép trong sys/queue.h duy trì địa chỉ của phần tử tiếp theo trước đó?

Question

Tôi đang học sys/queue.h từ FreeBSD và tôi có một câu hỏi:

Trong sys/queue.h, LIST_ENTRY được định nghĩa như sau:

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

Tại sao nó duy trì địa chỉ của phần tử tiếp theo trước (struct type **le_prev) thay vì chỉ đơn giản là elment trước như struct type *le_prev?

Answer 1

Nếu bạn đã có thể đọc các tập tin queue.h từ đầu, bạn có thể đã có lời nhận xét sau đây:

* 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. 

nên danh sách, trong đó cung cấp O (1) chèn và xóa, nhưng chỉ về phía trước traversal. Để đạt được điều này, bạn chỉ cần tham chiếu đến con trỏ tiếp theo trước đó, chính xác là những gì được thực hiện .

Answer 2

Hãy để tôi cố giải thích. Trên thực tế, **le_prev* dành ablity vào danh sách được xác định bởi sys/queue.h để insert_before mà chuyển tiếp danh sách có thể không. So với insert_before, insert_after có thể được triển khai tốt trong danh sách hoặc danh sách chuyển tiếp. Vì vậy, danh sách là chức năng hơn.

insert_before(entry* list_elem, entry* elem, type val) 
{ 
    elem->next = list_elem; 
    *(list->prev) = elem; 
    elem->prev = *(list->prev); 
    list_elem->prev = elem->next; 
} 
insert_after(entry* list_elem, entry* elem, type val) 
{ 
    if(((elem)->next= (list_elem)->next) != NULL) { 
     (elem_list)->next->prev = &(elem)->next; 
    } 
    (list_elem)->next = elem; 
    elem->prev = &(list_elem)->next; 
}