什么是游标链表？[C++]

Question

我的教授给了我一个名为CursorList.cpp的文件，实现了“游标链表”。问题是 - 我甚至不知道那是什么！

有人能简要解释一下吗？

谢谢！

- Yuval Karmi

---

Yuval，你应该先看一下文件暴露了哪些接口。也就是说，读取它，查看有哪些公共方法，如何使用它们等等。从名称上看，它似乎很确定地实现了一个链表数据结构，即可以进行插入、删除、遍历等操作的数据结构。试着测试一下吧。 - Rob Lachlan

Answer 1

一个CursorList是一个链表的数组版本。基本上，你有一个链表节点的数组，但是每个节点元素不再包含指向链表中下一个项目的指针，而是包含下一个节点元素的索引。因此，例如，如果我们想要在链表中存储5, 3, 2, 11, 9，我们将得到5 -> 3 -> 2 -> 11 -> 9 -> NULL。插入操作并不是问题，我们只需更改最后一个指针指向插入的节点，并使插入的节点指向NULL。删除也是一样的，我们只需要重新调整指针。然而，总是需要动态分配（使用malloc或new）内存来创建新节点可能会有问题。

如果我们要在CursorList中存储，我们首先声明数组的最大大小，然后填充它。所以我们说listNode cursorList[10]，其中我们声明一个listNode对象如下：

class listNode {
    public:
        listNode() {
            data = -1;
            next = NULL;
        }
        listNode(int inputData, &listNode inputNext) {
            data = inputData;
            next = inputNext;
        }
    private:
        int data;
        listNode* next;
};

在用listNode对象填充数组后，我们将得到以下类似的结果：

现在，如果我们想要移除5，我们只需要更新next索引。这样我们就会得到下面这个结果：

一个问题出现了，我们怎么知道要设置5的next索引为什么值呢？这就是Freelist（@Justin Ethier回答中提到的）发挥作用的地方。Freelist包含数组中仍然空闲的索引。在创建CursorList时，Freelist包含0-9。当listNode对象被分配给数组元素时，Freelist会删除这些索引。当一个数字被移除（例如上面的5），该索引将被添加回Freelist中。如果我们想要向CursorList中添加一个数字，我们只需要更新相应元素的next索引即可。

- sbru

Answer 2

根据这里的内容，以下是关于光标链表的一些背景信息：

• 某些语言不支持指针
• 使用对象数组代替
• 从空闲列表开始
• 在需要时从空闲列表中分配空间
• 要删除：更改指针，添加到空闲列表

因此，这实际上是一种不使用指针实现的链表。也许这种实现方式更容易理解？

- Justin Ethier

---

仍不太清楚它们是什么。那么我能否扩展我的问题，问一下在这种情况下列表是什么？谢谢！ - Yuval Karmi

Answer 3

我猜测它是一个链表，除此之外还保留了一个指向“当前”元素的指针，例如用于遍历列表。

如果你想确切地知道你的教授的意思，看一下.cpp文件，并找出那里实现了什么。

- sth

---

这符合我对 ADT^H^H^H 对象类型的回忆 -- 列表 + 当前位置 -- 在我的数据结构课上（80年代，哀叹），在该术语被“窃取”仅表示 SQL 结果集缓冲区之前。 - Roboprog

Answer 4

在游标实现中，我们自己构建存储池，在数组中存储未使用的节点的链表。

在C和C++中，存储池由语言提供的一组库函数管理。在执行开始时，从操作系统获取适当大小的存储池。当程序请求新节点时，语言库函数从池中获取存储空间。如果池中没有足够的存储空间，则库会从操作系统请求额外的池空间。当程序释放存储空间时，语言库函数将其返回到存储池中。游标实现通常会从系统中获取固定数量的存储空间作为数组，并为应用程序提供类似于new和delete的函数。

- Kokul Jose