双链表如何为？

22.Acwing基础课第827题-简单-双链表 题目描述 实现一个双链表，双链表初始为空，支持 5 种操作： 在最左侧插入一个数； 在最右侧插入一个数； 将第 k 个插入的数删除； 在第 k个插入的数左侧插入一个数； 在第 k 个插入的数右侧插入一个数 现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。 注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。 输入格式 第一行包含整数 MM，表示操作次数。 接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种： L x，表示在链表的最左端插入数 x。 R x，表示在链表的最右端插入数 x。 D k，表示将第 k 个插入的数删除。 IL k x，表示在第 k 个插入的数左侧插入一个数。 IR k x，表示在第 k 个插入的数右侧插入一个数。 输出格式 共一行，将整个链表从左到右输出。 数据范围 1≤M≤100000 所有操作保证合法。 输入样例： 10 R 7 D 1 L 3 IL 2 10 D 3 IL 2 7 L 8 R 9 IL 4 7 IR 2 2 输出样例： 8 7 7 3 2 9 代码： #include <iostream> using namespace std; // 数组模拟链表的最大长度 const int N = 1e6+10; // e[i] ：节点 i 存储的值 // l[i] ：节点 i 的 左指针（左边节点的下标） // r[i] ：节点 i 的 右指针（右边节点的下标） // idx ：当前可以使用的 新节点下标 int e[N], l[N], r[N], idx; // 初始化双向链表 // 0 表示左哨兵（最左头节点） // 1 表示右哨兵（最右尾节点） void init() { // 左节点的右边是右节点 r[0] = 1; // 右节点的左边是左节点 l[1] = 0; // 0和1已被占用，下一个新节点从 2 开始 idx = 2; } // 核心操作：在 节点a 的 右边 插入一个值为 x 的新节点 void insert(int a, int x) { // 给新节点赋值 e[idx] = x; // 新节点的左边 = a l[idx] = a; // 新节点的右边 = a 原来的右边节点 r[idx] = r[a]; // a 原来右边节点的左边 = 新节点 l[r[a]] = idx; // a 的右边 = 新节点 r[a] = idx++; } // 在 节点a 的 左边 插入 x // 等价于：在 a 的 左节点 的 右边 插入 void insert_left(int a, int x) { insert(l[a],x); } // 删除节点 a // 注意：不能删除 0 和 1 哨兵节点 void remove(int a) { // 让 a 右边节点的左边 直接指向 a 的左边 l[r[a]] = l[a]; // 让 a 左边节点的右边 直接指向 a 的右边 r[l[a]] = r[a]; // 节点 a 被从链表中剔除 } // 遍历链表：从左到右输出所有值 void trasever() { // 从左哨兵的右边开始遍历 // 直到走到右哨兵 1 为止 for(int i = r[0]; i != 1; i = r[i]) { cout << e[i] << " "; } cout << endl; } int main() { // m 个操作 int m; cin >> m; // 先初始化链表 init(); int k,x; while(m--) { string op; cin >> op; // L x：在链表 最左边 插入 x if(op =="L") { cin >> x; insert(0,x); } // R x：在链表 最右边 插入 x else if(op == "R") { cin >> x; insert(l[1],x); } // D k：删除第 k 个插入的数 // 因为节点从 2 开始，所以 k+1 else if(op == "D") { cin >> k; remove(k+1); } // IL k x：在第 k 个数的 左边 插入 x else if(op == "IL") { cin >> k >> x; insert_left(k+1,x); } // IR k x：在第 k 个数的 右边 插入 x else if(op == "IR") { cin >> k >> x; insert(k+1,x); } } // 输出最终链表 trasever(); return 0; } #include <iostream> using namespace std; // 定义数组最大长度，100010是常用的略大于1e5的数值，避免越界 const int N = 100010; int m; // 操作的总次数 // 数组模拟双向链表的核心结构： // e[idx]：存储下标为idx的节点的值 // l[idx]：存储下标为idx的节点的左邻居下标 // r[idx]：存储下标为idx的节点的右邻居下标 // idx：当前可以分配的节点下标（相当于节点的"身份证号"） int e[N], l[N], r[N], idx; // 功能：在节点a的右边插入一个值为x的新节点 // 参数：a - 目标节点下标，x - 要插入的数值 void insert(int a, int x) { e[idx] = x; // 第一步：给新节点赋值x l[idx] = a; // 新节点的左邻居是a r[idx] = r[a]; // 新节点的右邻居是原来a的右邻居 l[r[a]] = idx; // 原来a的右邻居的左邻居改为新节点 r[a] = idx ++ ; // a的右邻居改为新节点，然后idx自增（分配下一个节点） } // 功能：删除下标为a的节点 // 参数：a - 要删除的节点下标 void remove(int a) { l[r[a]] = l[a]; // 被删节点的右邻居的左邻居 → 被删节点的左邻居 r[l[a]] = r[a]; // 被删节点的左邻居的右邻居 → 被删节点的右邻居 } int main() { cin >> m; // 输入操作次数 // 初始化双向链表的头尾哨兵节点： // 0作为左端点（头哨兵），1作为右端点（尾哨兵） // 初始时头哨兵的右邻居是尾哨兵，尾哨兵的左邻居是头哨兵 r[0] = 1, l[1] = 0; idx = 2; // 前两个下标（0、1）被哨兵占用，新节点从2开始分配 while (m -- ) // 循环处理m次操作 { string op; // 存储操作类型（L/R/D/IL/IR） cin >> op; int k, x; // k是操作的节点编号，x是要插入的数值 if (op == "L") // 操作L：在链表最左端插入数x（头哨兵0的右边） { cin >> x; insert(0, x); } else if (op == "R") // 操作R：在链表最右端插入数x（尾哨兵1的左边） { cin >> x; insert(l[1], x); // l[1]是尾哨兵的左邻居，即最后一个有效节点 } else if (op == "D") // 操作D：删除第k个插入的数对应的节点 { cin >> k; remove(k + 1); // 因为idx从2开始，第k个插入的节点下标是k+1（第1个→2，第2个→3...） } else if (op == "IL") // 操作IL：在第k个插入的数的左边插入x { cin >> k >> x; insert(l[k + 1], x); // l[k+1]是第k个节点的左邻居，插入到左邻居右边=插入到k节点左边 } else // 操作IR：在第k个插入的数的右边插入x { cin >> k >> x; insert(k + 1, x); } } // 遍历链表并输出所有有效节点的值： // 从头哨兵0的右邻居开始，直到遍历到尾哨兵1停止 for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' '; cout << endl; return 0; }