开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

链表

简介: 复习acwing算法基础课的内容,本篇为讲解基础算法:链表,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上
+关注继续查看

文章目录

前言

一、单链表

1.单链表必备属性

2.单链表的几种操作

初始化

在表头插入一个元素

删除下标是k的点后面的一个点

将x插入到下标为k的点的后面

3.AcWing 826. 单链表

AC代码

二、双链表

1.双链表必备属性

2.双链表的几种操作

初始化

在第k个插入点的右边插入一个数x

在第k个插入点的左边插入一个数x

删除第k个点

3.AcWing 827. 双链表

AC代码

三、时间复杂度


前言

复习acwing算法基础课的内容,本篇为讲解基础算法:链表,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上


一、单链表

1.单链表必备属性

int idx;         //idx指的是是数组的下标
//我们在对链表进行操作的时候,这个下标可能会特别的混乱,比如往a[2]和a[3]中间插一个a[7]
//但是这不影响什么,因为我们在遍历链表的时候,不是靠数组下标去遍历的,而是靠ne数组
int e[N];       //存的是值,比如e[i]代表的就是下标是1的值
int ne[N];      //存的是我们下一个指向的是哪个坐标
int head;       //头结点,初始化为-1,表示链表里没有元素,

2.单链表的几种操作

初始化

void init()
{
    idx = 0;              //一开始链表的下标从0开始
    head = -1;            //头结点指向-1,证明链表里没有元素
}

在表头插入一个元素

void insert_head(int x)
{
    e[idx] = x;          //把值x放进以idx为下标的链表元素中
    ne[idx] = head;      //以idx为下标的链表元素指向原头结点指向的
    head = idx;          //现在头结点不再是指向-1,而是指向第一个元素
    idx ++;              //往后移动一位,准备接下来的一系列操作
}

删除下标是k的点后面的一个点

图示:

image.png

即让k指向k后面的后面的元素,ne[k]指的是k后面的元素坐标,ne[ne[k]]指的是ne[k]后面元素的坐标

代码表示如下:

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

将x插入到下标为k的点的后面

图示:

image.png

代码:

void insert(int x, int k)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

3.AcWing 826. 单链表

本题链接:AcWing 826. 单链表

本博客给出题目截图:

image.png

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 100010;

int idx, e[N], ne[N], head = -1;     //定义成全局变量idx自动赋值为0

void insert_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx ++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

void insert(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        char op[2];
        int x, k;
        scanf("%s", op);
        
        if (op[0] == 'H')
        {
            scanf("%d", &x);
            insert_head(x);
        }
        
        else if (op[0] == 'D')
        {
            scanf("%d", &k);
            if (!k) head = ne[head];
            else remove(k - 1);  //删除第k个插入的数后面的一个数,因为我们的坐标是从0开始的,所以是remove(k - 1);
        }
        
        else 
        {
            scanf("%d%d", &k, &x);
            insert(k - 1, x);    //在第k个插入的数后面加一个数,因为我们的坐标是从0开始的,所以是insert(k - 1, x);
        }
    }
    
    for (int i = head; i != -1; i = ne[i]) printf("%d ", e[i]);
    
    return 0;
}

这里说一个小技巧:即使是读入一个字符,也写成读入一个字符串的形式,这样会省去很多不必要的输入麻烦————y总

所以,本代码中把op定义成了op[2],输入的时候写的是scanf("%s", op);


二、双链表

1.双链表必备属性

int idx;             //同单链表中的idx的,指的是下标
int l[N];            //指的是本点的左边的点,如l[i]指的是坐标为i的点的左边的点的坐标
int r[N];            //指的是本点的右边的点,如r[i]指的是坐标为i的点的右边的点的坐标
int e[N];            //同单链表中的e[i],指的是坐标为i的点的值

2.双链表的几种操作

初始化

void init()
{
    //0表示左端点,1表示右端点
    l[1] = 0, r[0] = 1;      //1的左边是0,0的右边是1
    idx = 2;                 //因为已经用过两个点(0和1)了,所以idx从2开始
}

在第k个插入点的右边插入一个数x

void insert(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}

在第k个插入点的左边插入一个数x

insert (l[k + 1], x); //直接调用insert函数即可
//注意这里是l[k + 1],因为一开始已经用过两个点了,即初始化时候的0和1,故我们真正插入的第一个点的下标是2,所以第k个插入的点的下标为k + 1

删除第k个点

void remove(int k)
{
    l[r[k]] = l[k];      //k这个点的右边的点的左边直接指向k的左边
    r[l[k]] = r[k];      //k这个点的左边的点的右边直接指向k的右边
}

3.AcWing 827. 双链表

本题链接:AcWing 827. 双链表

本博客给出题目截图:

image.png

image.png

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010;

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

void init()
{
    l[1] = 0, r[0] = 1;
    idx = 2;
}

void insert (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)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main()
{
    init ();
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        string op;
        int k, x;
        cin >> op;
        
        if (op == "L")
        {
            scanf("%d", &x);
            insert (0, x);     //0代表头,我们要在头插入一个数,即在0的右边插入一个数
        }
        else if (op == "R")
        {
            scanf("%d", &x);
            insert (l[1], x);   //0和1只是代表头和尾,所以我们如果要在最右边插入,只要在指向1的那个点的右边插入就可以了
        }
        else if (op == "D")
        {
            scanf("%d", &k);
            remove (k + 1);
        }
        else if (op == "IL")
        {
            scanf("%d%d", &k, &x);
            insert (l[k + 1], x);
        }
        else
        {
            scanf("%d%d", &k, &x);
            insert(k +1, x);
        }
    }
    
    for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);    //从r[0](链表头)开始遍历,直到走到1(结尾)
    
    return 0;
}

三、时间复杂度

关于链表各操作的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《手撕链表题系列-8》相交链表
本系列主要讲解链表的经典题 注:划重点!!必考~
20 0
C++数据类型——链表
C++数据类型——链表
67 0
复杂链表的复制
题目描述:有一个复杂链表,其结点除了有一个Next指针指向下一个结点外,还有一个random指向链表中的任意结点或者NULL。其链表的定义如下: public class RandomListNode { int label; Rand...
753 0
处理空列表
java代码: import com.example.test.Test1.R; import android.app.Activity; import android.
435 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载