3

如果我有一个链表：

first node -----> second node ------> third node ---> ?

我可以在不使用经典列表线性搜索算法的情况下显示第三个节点值（例如）吗？

我尝试获取第 n 个节点：

struct node* indexof( struct node* head, int i )
{
    int offset = (int)((char*)head->next - (char*)head);
    return ((struct node*)((char*)head + offset * i));
}
4

3 回答 3

1

听起来您选择了错误的数据结构。如果你想直接进入第 n 个，那么你应该使用一个数组。

做不到这一点，以线性方式经历有什么不好？必须在很长的链表上调用很多才能导致性能问题。

于 2012-11-05T19:24:36.980 回答
1

这取决于您的确切链表实现，但一般来说，没有。您必须遍历列表才能访问第 n 个元素。

这是链表的一个特征，从某种意义上说，您可以用来计算数组或其他类似序列结构的偏移量的普通技巧将不起作用，因为您的各个列表元素不能保证在内存中布局任何明智的方式，因此您必须遵循next指针才能检索第三个元素。

您可以考虑提供对链接列表的恒定时间索引访问的其他数据结构。

于 2012-11-05T18:59:51.893 回答
0

链表的目的之一是能够以很少的成本轻松添加和删除节点。

您可以放弃该功能并使用有效负载指针数组，但它不再是链表（当可以通过算术增量轻松获得同一节点时，拥有指向下一个节点的指针的目的是什么？）。

例如，而不是

struct
{
    struct node *next;
    void *payload;
    ...
} node;

node *root = NULL;

并为没有节点分配空间，你可以有

typedef struct
{
    void *payload;
    ...
} node;
node *vector = NULL;
size_t vectorsize = 0;

并为最初需要的节点分配空间，然后realloc在需要时使用扩展列表，并memmove通过将节点移回已删除节点之外来删除节点。这在添加或删除节点时会导致明显的性能损失。另一方面，第 n 个节点正好是vector[n]。

我再说一遍，这不再是一个链表：可能无论你需要它做什么，用指针数组代替链表可以更好地完成它。

这提醒了我，你最好解释一下为什么你需要直接寻址能力（“陈述问题，不要问如何实现解决方案”）：也可能你需要的既不是数组也不是链表，但是，谁知道呢？可能是环形缓冲区、堆栈、山丘或二叉树。

在某些实现中，您甚至可以部署两个键合结构，例如，您可以在第一阶段使用（双重？）链表，其中包含大量插入和删除，尤其是最近插入的数据；然后为第二阶段构建并切换到指针数组，在该阶段您需要由节点号驱动的直接寻址（将数组用作列表节点地址的“缓存”）：

for (listsize = 0, scan = root; scan; scan = scan->next)
    listsize++;
if (NULL == (vector = (node *)malloc(listsize * sizeof(node))))
{
    // out of memory
    return EXIT_FAILURE;
}
for (listsize = 0, scan = root; scan; scan = scan->next)
    vector[listsize++] = scan;
// Now vector[i]->payload is the payload of the i-th node
于 2012-11-05T19:20:30.813 回答