如何实现节点存储在连续内存块的循环链表以达成O(1)旋转操作

1. 连续内存节点分配 #

核心逻辑是在初始化填充链表时直接申请一整块连续的Node数组内存，而非逐个分配零散的Node节点，具体修改如下：

• 首先给List类新增私有成员Node* node_base，用来存储连续内存块的首地址，方便后续指针运算和内存释放，同时修改构造函数对其初始化：

class List
{
    private:
        struct Node
        {
            Node* next;
            int data;
        };
        Node* node_base; // 新增连续内存首地址成员
        Node* start;
        Node* end;
        int size;
    public:
        List()
        {
            start = NULL;
            end = NULL;
            size = 0;
            node_base = nullptr; // 初始化首地址为空
        }
        ~List();
        void populate_list(const int &size);
        void move_start(int n, char d);
        void print();
};

• 修改populate_list方法，申请指定大小的Node数组，依次初始化每个节点的data和next指针，形成循环结构：

void List::populate_list(const int &s)
{
    size = s;
    node_base = new Node[size];
    for (int i = 0; i < size; i++) {
        node_base[i].data = i + 1;
        node_base[i].next = &node_base[(i+1) % size];
    }
    start = node_base;
    end = &node_base[size - 1];
}

• 析构函数直接释放整块数组内存即可：

List::~List()
{
    if (node_base != nullptr) {
        delete[] node_base;
    }
}

2. O(1)时间复杂度旋转实现 #

由于所有节点都存储在连续内存上，每个节点的位置可以通过首地址偏移直接计算，不需要遍历next指针，修改后的move_start方法如下：

void List::move_start(int n, char d)
{
    if (size == 0) return;
    // 对n取模，避免n大于size的无效计算
    n = n % size;
    if (n == 0) return;
    // 计算当前start相对于首地址的偏移量
    int offset = start - node_base;
    if (d == 'L') {
        offset = (offset + n) % size;
    } else if (d == 'R') {
        offset = (offset + size - n) % size;
    }
    // 直接赋值得到新的start地址
    start = node_base + offset;
}

说明 #

该方案完全符合你提到的「填充后无增删操作」的前提，原有链表的遍历逻辑不会受到任何影响，仅新增了一个首地址指针的存储开销，没有额外性能损耗。

内容的提问来源于stack exchange，提问作者James Newman