列表加入算法如何工作？

Question

我在 wayland protocol source code 中找到了以下函数。

void
wl_list_insert_list(struct wl_list *list, struct wl_list *other)
{
     if (wl_list_empty(other))
         return;
     other->next->prev = list;
     other->prev->next = list->next;
     list->next->prev = other->prev;
     list->next = other->next;
 }

它对具有 link 的列表进行操作，如下所示：

struct wl_list {
    struct wl_list *prev;
    struct wl_list *next;
};

它只是一个双重 linked 列表，就像其他列表一样。

但是我完全不懂这个功能。对我来说，link 'other' 似乎完全从两个列表中消失了，*list 和 *list->next link 现在只是交叉到另一个列表。

另外：这不是循环列表。 head 和 tail links 指向它们自己。[编辑] 我的错，实际上是一个循环列表。有道理。

谁能帮我理解这个算法是如何工作的。非常感谢。

Answer 1

我画了画，然后困惑地看着它们，直到我意识到其中的魔力。 list 和 other 不是节点，它们是列表 objects。是的，other 从 "it's list of nodes" 中删除，因为我们要将列表 other 的 nodes 添加到列表 list。函数结束后，other被完全移除，循环链接的节点全部链接到list的节点中。

列表加入算法如何工作？

How does list joining algorithm work?

c

linked-list

list