---
title: "双链表"
created: 2025-11-28
tags:
  - 算法
---

# 双链表

## 题目 [双链表](https://www.acwing.com/problem/content/829/)

![[image-1448206b.png]]

## 思路分析

道理基本一样 再加上一个数组表示左指针就行了

e[i]、l[i]、r[i]

可以不定义head 直接将0号位置作为head 1号位置作为tail 反正是双向的

但是idx不能少 这个是核心

那么初始化其实就是

![[image-c5b7bba9.png]]

让0.r=1 1.l=0 开始就用了两个位置 所以res=2（可以位置为第三个）

`void init(){`

`r[0]=1;`

`l[1]=0;`

`idx=2;`

`}`

而插入就是

![[image-c87376e2.png]]

idx位置的右指向k的右

idx的左指向k

原本k的右的左要指向idx

k的右要指向idx

`void add(int k,int x){`

`e[idx]=x;`

`r[idx]=r[k];`

`l[idx]=k;`

`l[r[k]]=idx;`

`r[k]=idx;`

`idx++;`

`}`

其实还有一种在k位置左边插入的情况

但是可以在调用时 调用add(l[k],x)

在k左边元素的右边插入 就是在k左边插入

这样可以少写一个函数

删除也不难

![[image-e2b51e85.png]]

右的左变左

左变右的左

`void remove(int k){`

`r[l[k]]=r[k];|`

`l[r[k]]=l[k];`

`}`

遍历输出就是

从第一个节点开始 不断右寻

`void print(){`

`for(int i=r[0];i!=1;i=r[i])`

`cout<<e[i]<<" ";`

`}`

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int e[N],l[N],r[N];

int idx;

void init()

{

    //初始化 第一个点的右边是 1   第二个点的左边是 0

    l[1]=0;

    r[0]=1;

    idx=2;//idx 此时已经用掉两个点了

}

//在第 K 个点右边插入一个 X

void add(int k,int x)

{

    e[idx]=x;

    r[idx]=r[k];

    l[idx]=k;

    l[r[k]]=idx;

    r[k]=idx;

    idx++;

}

//在K的左边插入一个数 可以直接调用这个函数

//在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x)

//删除第 k个 点

void remove(int k)

{

    r[l[k]]=r[k];

    l[r[k]]=l[k];

}

void print()

{

    for(int i=r[0];i!=1;i=r[i])

        cout<<e[i]<<" ";

}

int main()

{

    int M;

    cin>>M;

    init();

    while(M--)

    {

        string op;

        cin>>op;

        if(op=="L")

        {//0和1代表头和尾 最左边插入只要在指向0的数的左边插入就可以了

         //也就是可以直接在0的右边插入

            int x;

            cin>>x;

            add(0, x);

        }

        else if(op=="R")

        {//最右边插入 只要在指向1的那个点的右边插入

            int x;

            cin>>x;

            add(l[1],x);

        }

        else if(op=="D")

        {

            int k;

            cin>>k;

            remove(k+1);//remove（k+1）这样头结点和尾结点就永远不会被删掉了

        }

        else if(op=="IL")

        {

            int k,x;

            cin>>k>>x;

            add(l[k+1],x);

        }

        else if(op=="IR")

        {

            int k,x;

            cin>>k>>x;

            add(k+1,x);

        }

    }

    print();

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[链表|链表]] 🏠 [[00-听课板子]] ➡️ [[单链表|单链表]]