数据结构-单链表-双链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构-单链表-双链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

“收藏从未停止，练习从未开始”，或许有那么一些好题好方法，在被你选中收藏后却遗忘在收藏夹里积起了灰？今天请务必打开你沉甸甸的收藏重新回顾，分享一下那些曾让你拍案叫绝的好东西吧！

模板一：单链表

H x，表示向链表头插入一个数 x。

D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。

I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

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

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int head,idx,e[N],ne[N];
// head:头结点的下标
// idx:存储当前已经用到了哪个点
// e[i]:表示节点i的值
// ne[i]:表示节点i的next指针是多少 i->next

//初始化
void init()
{
    head = 0;
    idx = 1;
}

//将x插入到头节点
// idx->next = head head = idx
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

//将x插到下标是k的点后面
// idx->next = k->next k->next = idx 
void add(int k,int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

//将下标是k的点后面的点删掉
// k->next = (k->next)->next
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin>>m;
    
    init();
    
    while(m--)
    {
        int k,x;
        char op;
        
        cin>>op;
        if(op == 'H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin>>k;
            if(!k) head = ne[head];//删除头节点 head = head->next
            else remove(k);
        }
        else
        {
            cin>>k>>x;
            add(k,x);
        }
    }
    
    for(int i=head;i!=0;i=ne[i]) cout<<e[i]<<" ";
    cout<<endl;
    
    return 0;
}

模板二：双链表

L x，表示在链表的最左端插入数 x。

R x，表示在链表的最右端插入数 x。

D k，表示将第 k 个插入的数删除。

IL k x，表示在第 k 个插入的数左侧插入一个数。

IR k x，表示在第 k 个插入的数右侧插入一个数。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int idx,e[N],l[N],r[N];
// l[idx]: idx->prior
// r[idx]: idx->next

//初始化
// 0是左端点 1是右端点
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

//在节点a的右边插入一个数
//idx->prior = a;
//idx->next = a->next
//a->next->prior = idx;
//a->next = idx
void insert(int a,int x)
{
    e[idx] = x;
    l[idx] = a;
    r[idx] = r[a];
    l[r[a]] = idx;
    r[a] = idx;
    idx++;
}

//删除节点a
//a->next->prior = a->prior
//a->prior->next = a->next
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

int main()
{
    init();
    
    int m;
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        int k,x;
        
        if(op == "L")
        {
            cin>>x;
            insert(0,x);
        }
        else if(op == "R")
        {
            cin>>x;
            insert(l[1],x);//l[1] 1->prior 0永远是左边界 1永远是右边界
        }
        else if(op == "D")
        {
            cin>>k;
            remove(k+1);
        }
        else if(op == "IL")
        {
            cin>>k>>x;
            insert(l[k+1],x);//这里l[k+1] k+1 -> prior 因为idx从2开始 所以是k+1
        }
        else
        {
            cin>>k>>x;
            insert(k+1,x);
        }
    }
    
    for(int i=r[0];i!=1;i=r[i]) // 0是左边界 0->next是第一个开始的节点 1是右边界 到了1结束
    {
        cout<<e[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}