算法刷题笔记 双链表（C++实现）

题目描述

• 实现一个双链表，双链表初始为空，支持5种操作：

  • 在最左侧插入一个数；
  • 在最右侧插入一个数；
  • 将第k个插入的数删除；
  • 在第k个插入的数左侧插入一个数；
  • 在第k个插入的数右侧插入一个数

• 现在要对该链表进行M次操作，进行完所有操作后，从左到右输出整个链表。

• 注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

输入格式

• 第一行包含整数M，表示操作次数。
• 接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
  • L x，表示在链表的最左端插入数x。
  • R x，表示在链表的最右端插入数x。
  • D k，表示将第k个插入的数删除。
  • IL k x，表示在第k个插入的数左侧插入一个数。
  • IR k x，表示在第k个插入的数右侧插入一个数。

输出格式

• 共一行，将整个链表从左到右输出。

数据范围

• 1 ≤ M ≤ 100000
• 所有操作保证合法。

基本思路

• 双链表实际上就是对单链表的衍生。单链表中，每一个结点只需要存储自己的下一个结点的位置（通过下标或指针的方式）即可，但是双链表中的结点需要存储自己的上一个结点的位置。另外，双链表中往往不只有头指针，还有尾指针。
• 和单链表的实现思路类似，出于效率考虑，我们并不会在每次新建一个链表结点时都使用C++中的new运算符创建一个新结点，而是开辟一个空间足够大的静态数组，来模拟单链表。链表中每一个结点存储的左右两个结点的位置也分别通过一个静态数组进行表示。本题的最大难点就是对于每一种操作，都需要考虑是否要分情况，是否要合并多种情况。

实现代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int list[N];
int l[N], r[N];
int head = -1, tail = -1, current = 0;

inline void insert_left(void)
{
    // 输入结点信息
    int x;
    cin >> x;
    // 创建一个新结点
    list[current] = x;
    l[current] = -1;
    r[current] = head;
    // 修改原先的首结点
    if(head != -1) l[head] = current;
    else tail = current;
    // 将新插入的结点设置为首结点，同时修改当前位置
    head = current;
    current ++;
}

inline void insert_right(void)
{
    // 输入结点信息
    int x;
    cin >> x;
    // 创建一个新结点
    list[current] = x;
    l[current] = tail;
    r[current] = -1;
    // 修改原先的尾结点
    if(tail != -1) r[tail] = current;
    else head = current;
    // 将新插入的结点设置为尾结点，同时修改当前位置
    tail = current;
    current ++;
}

inline void delete_k(void)
{
    //输入部分
    int k;
    cin >> k;
    // 第一种情况，即该结点不是首结点也不是尾结点
    if(head != k - 1 && tail != k - 1)
    {
        // 找出该结点的前一个结点和后一个结点的下标
        int before = l[k - 1], after = r[k - 1];
        // 修改前一个结点的后一个元素下标和后一个结点的前一个元素下标
        r[before] = r[k - 1];
        l[after] = l[k - 1];
    }
    // 第二种情况，即该结点是首结点但是不是尾结点
    else if(head == k - 1 && tail != k - 1) 
    {
        head = r[k - 1];
        l[head] = -1;
    }
    // 第三种情况，即该结点是尾结点但是不是首结点
    else if(tail == k - 1 && head != k - 1)
    {
        tail = l[k - 1];
        r[tail] = -1;
    }
    // 第四种情况，该结点是链表中唯一结点
    else
    {
        head = -1;
        tail = -1;
    }
}

inline void insert_before_k(void)
{
    int k;
    cin >> k;
    if(head == k - 1) insert_left();
    else
    {
        int x;
        cin >> x;
        // 找到第k个结点的前一个结点
        int before = l[k - 1];
        // 创建一个新的结点
        list[current] = x;
        l[current] = before;
        r[current] = k - 1;
        // 修改前一个结点的后指针
        r[before] = current;
        // 修改第k个结点的前指针
        l[k - 1] = current;
        // 修改当前指针
        current ++;
    }
}

inline void insert_after_k(void)
{
    int k;
    cin >> k;
    if(tail == k - 1) insert_right();
    else
    {
        int x;
        cin >> x;
        // 找到第k个结点的后一个结点
        int after = r[k - 1];
        // 创建一个新的结点
        list[current] = x;
        l[current] = k - 1;
        r[current] = after;
        // 修改第k个结点的后指针
        r[k - 1] = current;
        // 修改后一个结点的前指针
        l[after] = current;
        // 修改当前指针
        current ++;
    }
}

int main(void)
{
    // 输入操作次数
    int M;
    cin >> M;
    // 输入每一次的操作，并分情况讨论
    for(int i = 0; i < M; ++i)
    {
        string operation;
        cin >> operation;
        if(operation == "L") insert_left();
        else if(operation == "R") insert_right();
        else if(operation == "D") delete_k();
        else if(operation == "IL") insert_before_k();
        else if(operation == "IR") insert_after_k();
    }
    // 循环输出整个链表
    while(head != -1)
    {
        cout << list[head] << " ";
        head = r[head];
    }
    return 0;
}