当前位置：首页 > article >正文

形象地理解UE4中的数据结构 TLinkedListBase

article 2025/1/4 7:22:39

大家都熟知链表，但不一定能快速看懂UE4中的数据结构。

TLinkedListBase表示“链接”中的一个结点，有三个成员：

一、ElementType Element; 表示具体的业务，例如int链条中的一个整数。

二、NextLink 表示 “下一个Node”，这是一个指向“下一个Node” 的指针，也非常好理解。

/** The next link in the linked list */
ContainerType* NextLink;

三、PrevLink 表示 “前一个Node” 的 “NextLink”，这是一个指针，它指向的是 “前一个Node” 的 “NextLink” 成员。逻辑上，我的 “前一个Node”的“NextLink”，通常就是 “我本身”（this）。

   /** Pointer to 'NextLink', within the previous link in the linked list
   * 指向 “前一个节点” 的 NextLink 成员
   */
   ContainerType** PrevLink;

这是一种什么感觉呢？就像是一个人（我 this），拿着别人手里的枪（别人的NextLink），指向我自己（this）。有了这样的一个形象的比喻，就可以理解下面的源代码了。

LinkBefore 在给定的元素之前插入“我”

FORCEINLINE void LinkBefore(ContainerType* Before)
// 首先，我们设想一下结局： this 将会在 Before（简称B） 的前面
// 
// 原本是 （前）T → B → N（后），以及 （前）P → This → Q（后），其中箭头指向的是后一个结点。
// 经过本方法后是：
// （前）T → This → B → N （后）

{
    checkSlow(Before != NULL);

    PrevLink = Before->PrevLink; // 我很强势，我之前手里拿着别人（P）的枪（P的NextLink指针），让这把枪指向了自己（现状如此、无须解释），如今，我换了一个人（T，即B的Previous），拿着他（T）手里的枪，指向了自己This（见下面第10行）。
    

    Before->PrevLink = &NextLink; // 这一句话的意思是： B拿着我的枪，&NextLink 这就是我的枪，指向了B。
    // 也就是形成 This → B


    NextLink = Before; // 我的Next指针指向B，也就是形成 This → B

    if (PrevLink != NULL)
    {
       *PrevLink = (ContainerType*)this; //【10行】 // 也就是形成 T → This
    }

// 到这里，B → N的关系没有变动。并形成了 T → This → B → N。
}

再重新复习一下： PrevLink 的意思是上一个节点的NextLink指针，只要把“X的 PrevLink ”指向某个Node Y，那么Y就是X的上一个节点了。

X->PrevLink = &Y; // 意味着Y成为X的上一个节点

LinkHead 将This插入到Head的前面

/**
 * Adds this element as the head of the linked list, linking the input Head pointer to this element,
 * so that when the element is linked/unlinked, the Head linked list pointer will be correctly updated.
 *
 * If Head already has an element, this functions like LinkBefore.
 *
 * @param Head     Pointer to the head of the linked list - this pointer should be the main reference point for the linked list
 */


// 原本是 P → This → Q，以及 T → Head → N
// 经过本方法后是：
//      P
//      ↓
// T → This → Head → N

FORCEINLINE void LinkHead(ContainerType*& Head)
{
    if (Head != NULL)
    {
       Head->PrevLink = &NextLink; // 形成 This → Head
    }

    NextLink = Head; // 形成 This → Head ，意味着断开了对Q的连接
    PrevLink = &Head; 

// 还记得Head的类型是 ContainerType* 的 & 吗？由于Head本身就是一个指针，且是该指针的本体，而非该指针的副本，所以这个指针对象本身，其实是T的成员“NextLink”。
// 所以这一句可以理解为 
// This.PrevLink = &(Head) = &(T->NextLink)
// 所以含义是形成了 T → This 

// 可以说C++语言博大精深，Head 是指Head节点，而 &Head 是Head 节点的前一个节点T 的NextLink成员

    Head = (ContainerType*)this; 
    // 对外界来说，我This，成为了新的Head
    // 也就是 Head 等价于 T->NextLink 赋值为 This ，即形成了 T → Head

}