二、数据结构2：双链表模板题+算法模板（双链表）

╰+哭是因爲堅強的太久メ 2023-10-10 21:57 52阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  双链表题目模板
 *  模板题
 *   *  双链表
     *   *  原题链接
         *  题目
         *  思路
         *  题解

## 算法模板 ##

### 双链表题目模板 ###

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
    int e[N], l[N], r[N], idx;
    
    // 初始化
    void init()
    {
        //0是左端点，1是右端点
        r[0] = 1, l[1] = 0;
        idx = 2;
    }
    
    // 在节点a的右边插入一个数x
    void insert(int a, int x)
    {
        e[idx] = x;
        l[idx] = a, r[idx] = r[a];
        l[r[a]] = idx, r[a] = idx ++ ;
    }
    
    // 删除节点a
    void remove(int a)
    {
        l[r[a]] = l[a];
        r[l[a]] = r[a];
    }

## 模板题 ##

### 双链表 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/829/][https_www.acwing.com_problem_content_829]

#### 题目 ####

827 . 双链表  
实现一个双链表，双链表初始为空，支持 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

所有操作保证合法。

输入样例：

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

#### 思路 ####

![在这里插入图片描述][8fb4d35f20de4f69a926def4718a4dac.png]  
![在这里插入图片描述][3e6d5efae346418cb005fbec75754010.png].  
![在这里插入图片描述][53400138988043c98921ddd487ee0652.png]

#### 题解 ####

#include <iostream>
    using namespace std;
    const int M = 1e5 + 10;
    int e[M],l[M],r[M],idx;
    int m;
    void init(){
    	r[0] = 1;
    	l[1] = 0;
    	idx = 2; // idx从2开始，所以删除第k个插入的数是remove(k+1) 
    }
    
    void add(int k,int x){
    	e[idx] = x;
    	r[idx] = r[k];
    	l[idx] = k;
    	l[r[k]] = idx;
    	r[k] = idx;
    	idx ++;
    }
    
    void remove(int k){
    	r[l[k]] = r[k];
    	l[r[k]] = l[k];
    }
    int main(){
    	cin>>m;
    	init();
    	while(m--){
    		string op;
    		cin>>op;
    		if(op == "R"){
    			int x;
    			cin>>x;
    			add(l[1],x);
    		}
    		else if( op == "L"){
    			int x;
    			cin>>x;
    			add(0,x);
    		}
    		else if( op == "D"){
    			int k;
    			cin>>k;
    			remove(k+1); // idx从2开始，所以删除第k个插入的数是remove(k+1) 
    		}
    		else if (op == "IL"){
    			int k,x;
    			cin>>k>>x;
    			add(l[k+1],x);
    		}
    		else{
    			int k,x;
    			cin>>k>>x;
    			add(k+1,x);
    		}
    	}
    	for(int i=r[0];i!=1;i = r[i]) cout<<e[i]<<" ";
    	
    	
    }

[https_www.acwing.com_problem_content_829]: https://www.acwing.com/problem/content/829/
[8fb4d35f20de4f69a926def4718a4dac.png]: https://img-blog.csdnimg.cn/8fb4d35f20de4f69a926def4718a4dac.png
[3e6d5efae346418cb005fbec75754010.png]: https://img-blog.csdnimg.cn/3e6d5efae346418cb005fbec75754010.png
[53400138988043c98921ddd487ee0652.png]: https://img-blog.csdnimg.cn/53400138988043c98921ddd487ee0652.png