LLVM中SDUse的addToList方法：链表插入的指针实现原理

我在阅读LLVM llc工具中SDUse的代码时，搞不懂SDUse::addToList(SDUse **List)的实现逻辑，尤其是**Prev和*Next指针是如何配合完成链表节点插入操作的？

SDUse类定义 #

/// 表示对SDNode的引用。此类包含一个SDValue，
/// 用于记录被引用的SDNode及其结果编号，一个指向使用该值的SDNode的指针，
/// 以及用于将一个SDNode的所有引用链接在一起的Next和Prev指针。
///
class SDUse {
  /// Val - 被引用的值。
  SDValue Val;
  /// User - 该值的使用者。
  SDNode *User = nullptr;
  /// Prev, Next - 指向该操作数所引用的SDNode的引用列表的指针。
  SDUse **Prev = nullptr;
  SDUse *Next = nullptr;

核心成员函数 #

void addToList(SDUse **List) {
    Next = *List;
    if (Next) Next->Prev = &Next;
    Prev = List;
    *List = this;
  }

  void removeFromList() {
    *Prev = Next;
    if (Next) Next->Prev = Prev;
  }
};

核心设计理解 #

SDUse实现的是一个特殊的双向链表：Next是普通的一级指针，指向后继节点；但Prev是二级指针，它存储的不是前一个节点的指针，而是链表中"指向当前节点的那个指针"的地址——这个指针可能是链表的头指针，也可能是前一个节点的Next指针。

这个设计的核心优势是：插入、删除操作不需要遍历链表找前驱，直接通过指针修改就能完成，且逻辑完全统一（不用区分头节点和中间节点）。

addToList 逐行解析 #

以在链表头部插入当前SDUse节点为例，拆解每一步逻辑：

1. Next = *List;
   把当前链表的头节点（*List是头指针指向的第一个SDUse实例）设为当前节点的后继节点，也就是当前节点插在原头节点的前面。
2. if (Next) Next->Prev = &Next;
   如果原链表不为空（存在头节点），就把原头节点的Prev指向当前节点的Next指针的地址。这一步是让原头节点明确："现在是当前节点的Next指针指向我"，后续删除时可以直接修改这个指针完成链接修正。
3. Prev = List;
   当前节点的Prev指向传入的链表头指针的地址（也就是List本身的地址）。因为当前节点即将成为新的链表头，后续如果删除它，直接修改*Prev就能更新链表的头指针。
4. *List = this;
   把链表头指针指向当前节点，完成头部插入操作。

为什么用二级指针Prev？ #

如果用普通的一级指针作为Prev（指向前一个节点），删除头节点时需要单独判断并修改链表头指针，逻辑会更繁琐。而用二级指针存储"指向自己的指针的地址"，不管是头节点还是中间节点，removeFromList的逻辑完全通用：

• *Prev = Next; 直接修改指向当前节点的那个指针，让它跳过当前节点指向后继节点
• 若后继节点存在，更新后继节点的Prev为当前节点的Prev，完成双向链接的修正

内容的提问来源于stack exchange，提问作者heshuju