实现数组式双向链表访问

双端链表（双向链表）是一种非常有用的数据结构，但其标准实现通常需要大量的指针操作。这不仅使得代码书写复杂且容易出错，也使得某些算法难以实现。为了简化代码并降低使用双向链表作为基础实现更复杂数据结构的难度，我设计并封装了一个链表类，使其支持通过数组下标方式访问节点。

目标

本项目的目标是实现一个可以使用类似数组下标方式访问链表中第 $n$ 个元素的双向链表类，并保留链表的所有优良特性。

设计思路

基于普通双向链表，我引入了一个新的管理类，用于管理链表对象。该类包含了三个节点指针（head、tail、cur）和两个用于统计的变量（tot、p），分别用于存储链表总长和当前指针位置的下标。

实现步骤

第一个版本

在第一个版本中，实现了对基本数据类型的支持，主要功能包括：

• 重载 operator[] 以返回节点类型
• 为节点类型定义了 insert()、remove()、operator=() 和 operator Type() 等方法

第二个版本

在第二个版本中，添加了对类对象的支持：

• 引入 NodeProxy 类，用于管理返回对象的行为，并为目标类的子元素重载相关操作符。

注意事项

链表管理类和节点类互相依赖，因此需要使用模板 (template) 来避免未定义行为。

C++ 源代码实现

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class Chain {
    template <typename N>
    class Mgr {
    public:
        int tot, p; 
        N *head, *tail, *cur;
        Mgr() {
            head = new N(this);
            tail = new N(this);
            tail->prev = head;
            head->next = tail;
            tot = 0, p = -1, cur = head;
        }
        ~Mgr() {
            while (head->next) {
                head = head->next;
                delete head->prev;
            }
            delete head;
        }
        N* get_node(const int &pos) {
            while (pos >= tot) tail->prev->insert(T());
            const int disHead = pos + 1;
            const int disTail = tot - pos - 1;
            const int disCur = abs(pos - p);
            if (disCur > disHead || disCur > disTail) {
                if (disHead < disTail) p = -1, cur = head;
                else p = tot, cur = tail;
            }
            while (pos < p) p--, cur = cur->prev;
            while (pos > p) p++, cur = cur->next;
            return cur;
        }
        class NodeProxy {
        private: 
            N* node;
        public:
            NodeProxy(N* _node) : node(_node) {}
            T* operator->() { return &(node->data); }
            T& operator*() { return node->data; }
            operator T&() { return node->data; }
            void operator= (const T &_data) { node->data = _data; }
            void insert(const T &_M_data) { node->insert(_M_data); }
            void remove() { node->remove(); }
        };
        NodeProxy operator[](const int &pos) { return NodeProxy(get_node(pos)); }
    };
    class Node {
    public:
        Node *prev, *next; 
        T data; 
        Mgr<Node> *from;
        Node(Mgr<Node> *_from):prev(nullptr), next(nullptr), from(_from) {}
        void insert(const T &_data) {
            from->tot++;
            Node *p = new Node(from);
            p->data = _data;
            p->prev = this;
            p->next = next;
            next->prev = p;
            next = p;
        }
        void remove() {
            from->tot--;
            from->p--;
            from->cur = prev;
            prev->next = next;
            next->prev = prev;
            delete this;
        }
    };
    Mgr<Node> data;
public:
    Chain() {}
    int size() { return data.tot; }
    auto operator[](const int &pos) { return data[pos]; }
};

struct node {
    int x, y;
};

int main() {
    
    Chain<node> c;
    c[10]->y = 9;          // 修改第10个元素的y值
    cout << c[10]->x << " " << c[10]->y << endl; // 输出第10个元素的x和y值
    
    c[9].insert({2, 28}); // 在第9项后插入新的元素
    cout << c[10]->x << " " << c[10]->y << endl; // 输出插入后的第10个元素的x和y值

    c[10].remove();       // 删除第10项
    cout << c[10]->x << " " << c[10]->y << endl; // 输出删除后的第10个元素的x和y值

    Chain<int> ch;

    ch[10] = 100;
    cout << ch[10] << endl;

    ch[9].insert(10);
    cout << (ch[11]>ch[10]?"great\n":"small\n");

    cout << ch[10] << endl;

    ch[10].remove();
    cout << ch[10] << endl;

    return 0;
}

总结

通过这种方式实现的数组式双向链表，不仅保留了链表的灵活性，还使得操作变得更加直观和易于理解。这种设计尤其适用于需要频繁访问或修改特定位置元素的场景。

---