206. 双链表
时间限制：1000 MS 内存限制：64 MB
题目描述
# 双链表 ## 题目描述 实现一个双向链表。链表初始为空，支持以下 $5$ 种操作： 1. 在链表的最左端插入一个数。 2. 在链表的最右端插入一个数。 3. 删除第 $k$ 个插入的数。 4. 在第 $k$ 个插入的数左侧插入一个数。 5. 在第 $k$ 个插入的数右侧插入一个数。 现在对该链表进行 $M$ 次操作，请在所有操作结束后，从左到右输出链表中的所有元素。 **注意：**“第 $k$ 个插入的数”指按照插入时间顺序编号为 $k$ 的数，而不是当前链表中从左到右的第 $k$ 个数。所有插入操作统一按时间顺序从 $1$ 开始编号；删除操作不会改变其他数的插入编号，已删除的编号也不会被重新使用。 ## 输入格式 从文件 `dlist.in` 中读入数据。 第一行包含一个整数 $M$，表示操作次数。 接下来 $M$ 行，每行包含一个操作命令，格式为以下五种之一： - `L x`：在链表的最左端插入整数 $x$。 - `R x`：在链表的最右端插入整数 $x$。 - `D k`：删除第 $k$ 个插入的数。 - `IL k x`：在第 $k$ 个插入的数左侧插入整数 $x$。 - `IR k x`：在第 $k$ 个插入的数右侧插入整数 $x$。 ## 输出格式 将结果输出到文件 `dlist.out` 中。 输出一行，按从左到右的顺序输出操作结束后链表中的所有元素，相邻元素之间用一个空格分隔。 如果链表为空，则输出一个空行。 ## 数据范围 - $1 \le M \le 300$。 - $x$ 为 `int` 类型整数。 - 所有操作保证合法，即 `D k`、`IL k x` 和 `IR k x` 所引用的插入编号均已存在，且对应的数尚未被删除。 ## 样例输入 ``` 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 ``` ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。