时间戳

首页 > 解决方案 > 如何制作一个连续的链表？

c++ - 如何制作一个连续的链表？

问题描述

我有一个循环链表的自定义数据结构。它的目的很小众，所以想知道有没有办法让每个节点都指向一块连续内存块中的一个地址，从而实现随机访问。在初始填充之后，该列表根本不会被修改（插入/删除），所以一个连续的块不会妨碍我不认为的任何事情。

我怎样才能做到这一点？

另外，我不使用向量的原因是因为我正在基于指针重新排列对列表执行旋转。但是，我正在按 O(n) 重新排列指针，而我相信如果我使用连续的内存空间，我可以通过指针算术按 O(1) 重新排列指针。

编辑更清楚：我的“列表”是这样的

// barebones circular list structure
class List
{
    private:
        struct Node
        {
            Node* next;
            int data;
        };

        // beginning of list
        Node* start;
        // end of list which POINTS to beginning as well
        Node* end;
        // number of list elements
        int size;

    public:
        List()
        {
            start = NULL;
            end = NULL;
            size = 0;
        }
        ~List();

        // populates the list using size parameter and uses stdin for the values
        void populate_list(const int &size);
        // moves the starting pointer of a list, effectively rotating it
        void move_start(int n, char d);
        // print contents of list
        void print();
};

正如我所说，列表的所有元素（节点）都是通过填充列表填充的。人口的约定是从 1 开始的顺序。因此，假设您的大小为 5，则列表会像 {1, 2, 3, 4, 5} 一样填充。然后，给定一个旋转列表的数量，我通过旋转move_start()

// moves starting node by n spaces in d direction
void List::move_start(int n, char d)
{
    // left rotation procedure
    if (d == 'L')
    {
        // move the start pointer the given rotation amount
        for (int i = 0; i < n; i++)
            start = start->next;
    }

    // right rotation procedure
    else if (d == 'R')
    {
        // move the start pointer by the size of the list minux the given rotation amount
        for (int i = 0; i < size-n; i++)
            start = start->next;
    }
    return;
}

也许我的理解是错误的，但我相信我在 O(n) 处“旋转”，因为我将start指针从 1 到size-1时间（。但如果我有一个连续的Nodes 块，那么我可以简单地分配start给一个新的位置，而不是走到那里（O（1））。希望可以解决问题。

标签： c++memory-managementlinked-list

解决方案

我怎样才能做到这一点？

您可以使用使用自定义分配器的标准列表容器。

但是，我正在按 O(n) 重新排列指针，而我相信如果我使用连续的内存空间，我可以通过指针算术按 O(1) 重新排列指针。

所有列表都可以使用该操作在恒定时间内进行旋转splice（只要您不需要搜索相关的迭代器）。连续的内存空间不会提高这种操作的渐近复杂度。

根据您的描述，似乎简单地使用std::vector带有自定义迭代器的“第一个”元素将是数据结构的不错选择。我看不到使用链表的好处。向量和迭代器结合起来基本上产生了一个循环缓冲区。

推荐阅读