增强型链表：基本指南

链表如何工作？

链表是一种数据结构，其中每个数据的字段通过指针而不是偏移量连接。它由一个主元素组成，该主元素存储第一个和最后一个元素，即所谓的节点元素，其中包含所有必要的用户字段（例如电话、所有者、公司等）以及指向下一个节点的指针。最后一个元素链接到指示列表结尾的 NULL 字段。

当新元素添加到链表时，主节点必须将“尾部”指针更新为新的终止节点，并且必须将先前的 NULL 指针更新为新的尾部。

此数据结构允许高效记录新数据，而无需调整整个数组的大小。这是一种存储只写数据的有效方法，并且不需要提前知道元素的数量。这是一种简单的数据结构，在内存中，它看起来像这样：

驱逐键的链接列表

在之前的一篇文章中，我们讨论了每次删除项目后，需要一个缓冲区来扫描树而不离开树。在具有 GC 的语言中，这不是问题。但是，当应用程序代码管理内存时，基于包含过期元素的链接列表的缓冲区可以成为一种解决方案。

链表允许快速添加元素。但是，在链表中查找任何内容都需要顺序扫描，因此不适合快速检索密钥。因此，它是一种有效的解决方案，可用于记录数据、创建临时缓冲区和组织数据以从头节点进行顺序读取。

查找要抢占的元素就是此类任务的一个例子。抢占通常用于不同的缓存实现中。缓存包含可以从其他内存源以较大的延迟恢复的数据。缓存通常存储在主内存中。主内存是有限的，为了有效使用，主内存中只能存储一小部分数据快照。

它要求我们更智能地使用内存，避免将内存用于很少请求的数据，并且如果请求频率过低则删除此类数据。

清除缓存中字段的一种有效方法是最近最少使用 (LRU) 方法。下面是 LRU 表示：

在这种情况下，应用程序至少包含一个链接列表来存储最近使用的对象，并具有其他数据结构（如哈希表）以便快速搜索。节点是互连的。

当用户从哈希表中检索数据时，链表会通过将数据移至尾部来刷新这些数据。因此，经过几次操作后，尾部会包含最近使用的数据，而头部会保留很少请求的数据。

如果发生内存溢出，应用程序可以扫描前 N 个元素以释放足够的内存。这是一个简单的操作，因为链表适应顺序扫描。很少使用的数据的内存将被释放，而新的更频繁的节点可以存储在缓存中。

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

需要注意的是：当使用元素的数量在频率上差异很大时（例如，95% 的请求分布在 100 万个键中的前 100 个键上），Splay Tree 可能更适合存储缓存。这棵树根据每个节点的使用频率进行平衡。

Splay Tree 的主要思想与 LRU 相反 - 最常用的元素位于根附近，这使得该数据结构成为缓存的主要结构的理想选择。

可以通过两种方式解决驱逐问题：使用与主结构互连的链接列表，或将 Splay Tree 修改为线程二叉树。Splay Tree 中的节点已经按使用频率排序。虽然对树叶进行额外的线程处理可能需要更多 CPU 时间，但因此可以节省内存。

为了更好地理解内存中最近使用的数据的加速，您可以在此链接上探索实时 VM 迁移的示例。

提高链表的扫描速度

前面提到过，链表是写入数据最快的解决方案，虽然扫描速度很快，但比数组的扫描速度慢。

我在上一篇文章中将这个问题描述为数据局部性。然而，与二叉树类似，链表也有改进的潜力。展开链表允许你在列表的每个节点中存储更多数据。因此，它可以节省下一个指针节点的内存，有时还可以提高性能，前提是元素的大小适合 CPU 缓存行：

主要思想保持不变，但是列表在内存中的表示形式将会改变。

它将在许多方面发生变化。以下有 2 个选项：

这些改进提高了链表的性能，但也增加了代码的复杂性。对于使用链表的磁盘操作，展开的节点可以包含更多元素。理解其工作原理的一种简单方法是想象一个数组的链表。

在代码中，我们需要修改结构体描述，从现在开始读取或写入结构体数组中的每个元素：

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

跳过列表

跳跃列表是一种提高链表中元素搜索速度的方法。这种类型的链表存储一个键来对链表进行排序，并包含额外的指针，以便比简单的扫描操作更有效地定位节点。

额外的节点提高了跳跃列表中节点之间的遍历速度。它的工作原理类似于二进制搜索。相反，添加新元素需要更多时间。因此，跳跃列表必须有一个键。应用程序可以制作任意数量的级别来提高速度特性。在大多数情况下，更好的选择是让树中的级别略少或与高度大致相同。（观看上图）

在搜索时，应用程序从最高层开始，这是最快的路线。检测到附近的键后，它会下降到较低的级别，直到找到所需的节点。

此过程的时间复杂度为 O(log(n))。例如，对于具有 16 个节点的跳跃列表使用 4 级，对于 100 万个节点使用 20 级，对于 40 亿个节点使用 32 级，其时间复杂度与 RB 树相似。

跳过列表更好，原因如下：

• 实现简单。尽管与RB树具有相似的特性，但它的实现和维护要容易得多。

• 高效地将新节点附加到跳过列表的末尾。

• 创建跳跃表的线程安全实现比树更容易。

让我们探索一下这个概念的实现吧！

结构节点：

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

创建节点的函数：

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

在插入过程中，任务包括检测存储节点的正确位置并确定连接到此节点的级别数。使用随机函数确定级别有助于简化每个新节点的流程。平均而言，该函数在 50% 的情况下分配第二级，在 25% 的情况下分配第三级，依此类推。此方法最大限度地减少了访问内存以重新平衡元素的时间。

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

搜索节点的函数：

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

一个基准测试函数，用于测试链表、跳跃表和 RB 树的性能。用作键的值设置为 2 的幂。测试目的的值无关紧要。

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

在连续增长的键上测试此数据结构的结果：

这是插入的最佳时机（如果不考虑简单的链接列表）并且是一种相当快速的搜索元素的方法。

按顺序递减的键测试此数据结构的结果：

这很容易理解：这种跳跃列表的实现只有一个指向第一个元素的头指针。向末尾添加节点更加复杂。要改变这种方法，我们可以添加第二个指针（指向尾部）或反向跳跃列表（头部将指向大值）。这意味着跳跃列表是 Kafka 流等日志数据的有效数据结构。在这种情况下，它至少可以比 RB 树快两倍，并且更容易实现。

跳跃列表降低了链表的插入速度，但是，对于顺序数据，它仍然比其他对元素的访问时间为对数的数据结构更快，尤其是当键按顺序增长时。然而，键的任何顺序增长都会使树中的插入变得复杂，因为它会导致大量旋转以保持树的平衡。

只有当值在整个序列中增加（或减少）时，它才有效。例如，如果我们随机化键，结果将会有所不同：

从中可以看出，值的分布对 RB 树的速度特性没有显著影响，但会显著影响跳过表的性能。

结论

如今，我们的应用程序可能会以不同的方式组织内存或磁盘中的数据。映射和列表在以不同的顺序排列数据以实现不同的目的方面发挥着重要作用。这些结构可确保足够的性能、资源效率和能力。

有时，它不能满足我们的需求，应用程序必须在关键部分进行更改才能更优化。在某些情况下，使用更合适的数据结构可能会有所帮助，例如用于不精确匹配或节省内存的树。其他情况 - 改进算法，例如使用异步方法来提高单个线程的性能。

当所有其他选项都用尽时，剩下的方法就是调整数据结构和使用方法。有一些数据结构变化的例子，使它们更适合实际的特定任务。

虽然链表主要是一种只写和顺序扫描数据结构，但它可以比 RB 树进行更多优化，并且在只写情况下保持高效。然而，某些特性的提升可能会影响其他特性。因此，最好的方法是优先考虑重要的特性，丢弃不重要的特性。