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

Question

我有一个循环链表的自定义数据结构。它的用途非常小众，所以想知道有没有办法让每个节点都指向连续内存块中的一个地址，实现随机访问。该列表在初始填充后根本不会被修改 (inserted/deleted)，因此一个连续的块不会阻碍任何我不认为的东西。

我怎样才能做到这一点？

此外，我不使用向量的原因是因为我正在基于指针重排对列表执行旋转。但是，我正在通过 O(n) 重新排列指针，而我相信如果我使用连续内存 space.

，我可以通过指针算法通过 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();
};

正如我所说，列表的所有元素（节点）都是通过填充列表填充的。 population 的约定是从 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 次（。但是如果我如果要有一个连续的 Node 块，那么我可以简单地将 start 分配到一个新位置，而不是将其移动到那里 (O(1))。希望一切都解决了。

Answer 1

如您问题的评论中所述，有许多更好的方法可以满足您的要求。

但是，如果您的要求非常严格，您必须使用列表，您可以使用 placement new 来控制连续内存。但在使用之前了解使用 placement new 的所有复杂性。

下面是一个如何实现该目标的示例。

    // buffer with required size
    unsigned char buf[sizeof(int) * 4];

    // placement new in buffer
    int* pInt1 = new (buf) int(2);
    int* pInt2 = new (buf + sizeof(int) * 1) int(4);
    int* pInt3 = new (buf + sizeof(int) * 2) int(6);
    int* pInt4 = new (buf + sizeof(int) * 3) int(8);

    //Test
    std::cout << pInt1 << "  " << pInt2 << "  " << pInt3 << "  " << pInt4 << std::endl;
    std::cout << *pInt1 << "  " << *pInt2 << "  " << *pInt3 << "  " << *pInt4 << std::endl;

    //Push into the list
    std::list<int*> tList;
    tList.push_back(pInt1);
    tList.push_back(pInt2);
    tList.push_back(pInt3);
    tList.push_back(pInt4);
      
    //Test
    for (auto it = tList.begin(); it != tList.end(); ++it)
    {
        std::cout << *it << std::endl;
        std::cout << **it << std::endl;
    }

Answer 2

How can I achieve this?

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

However, I'm rearranging the pointers by O(n), whereas I believe I can rearrange the pointers by O(1) via pointer arithmetic if I use a contiguous memory space.

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

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

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

How to make a contiguous linked list?

c++

memory-management

linked-list