Tại sao Linux sử dụng "con trỏ trỏ tới con trỏ" này cho danh sách?

Question

#define TAILQ_ENTRY(type)      \ 
struct {        \ 
    struct type *tqe_next; /* next element */   \ 
    struct type **tqe_prev; /* address of previous next element */ \ 
} 

Tôi tìm thấy mã ở trên sử dụng con trỏ tới con trỏ và đây không phải là con trỏ duy nhất. Tôi muốn biết tại sao làm như vậy? Con trỏ chính nó không thể xử lý nó?

Answer 1

Tôi đoán điểm ở đây là xóa các phần tử. Hãy xem xét rằng bạn có singly linked list, có nghĩa là bạn có thể chuyển tiếp điều hướng trong các nút của nó.

Bây giờ, hãy xem xét một nút danh sách chung (nói N_j) mà bạn muốn xóa. Sau khi xóa, bạn muốn dễ dàng liên kết nút trước (nói N_{j-1}) đến tiếp theo (giả sử N_{j+1}). Do đó, bạn cần phải sửa đổi trường tqe_next của nút trước đó N_{j-1} yêu cầu con trỏ đến nó, tức là con trỏ đến con trỏtqe_prev trong N_j.

Nói cách khác, trong pseudo-code về, sau đây đúng

*(N_j.tqe_prev) == (N_{j-1}).tqe_next 

hoặc

N_j.tqe_prev == &(N_{j-1}).tqe_next 

.