文章目录
前言
一、单链表
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的点后面的一个点
图示：
即让k指向k后面的后面的元素，ne[k]指的是k后面的元素坐标，ne[ne[k]]指的是ne[k]后面元素的坐标
代码表示如下：
void remove(int k) { ne[k] = ne[ne[k]]; }
将x插入到下标为k的点的后面
图示：
代码：
void insert(int x, int k) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx; idx ++; }
3.AcWing 826. 单链表
本题链接：AcWing 826. 单链表
本博客给出题目截图：
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. 双链表
本博客给出题目截图：
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; }
三、时间复杂度
关于链表各操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
