826. 单链表 / 双链表
1、结构体法
struct Node
{
int val;
Node *next;
}
new Node(); //非常慢
2、用数组模拟链表
数组模拟单链表 速度快
邻接表： 存储 树 和 图
//e[N] ne[N] 用下标关联 e[]存储val ne[]存储next指针
//数组e相当于信息域，存储值 ： 数组ne相当于指针域，指向下一个节点
#include<iostream>
const int N = 1e5 + 10;
//head表示节点的下标
//idx存储当前已经用到的点
//e[i] 表示val的值 ne[i]表示节点i的next节点
int head, e[N], ne[N], idx;
void init()
{
head = -1;
idx = 0;
}
//链表头插入操作
void add_to_head(int x)
{
//e[idx] = x, ne[idx] = head, haed = idx++;
e[idx] = x; //把值存起来
ne[idx] = head; //这个节点的指针指向头结点
head = idx; //头结点指向这个节点
idx++; //然后更新用到的节点位置
}
//删除操作
void remove(int k)
{
ne[k] = ne[ne[k]];//指针跳过需要删除的点
}
//从指定位置插入
void add(int k,int x)
{
//e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
e[idx] = x;
ne[idx] = ne[k]; //插入位置的指针指向插入点后面的节点
ne[k] = idx; //插入点后面的节点的指针指向插入元素的节点
idx++; //更新用到的节点
}
int main()
{
int n;
cin >> n;
init();
while(n--) {
char c;
cin >> c;
int x, k;
if(c == 'H') {
cin >> x;
add_to_head(x);
}
else if(c == 'I') {
cin >> k >> x;
add(k - 1, x); //单链表是从0开始 所以要k - 1 输入第k个位置
}
else if(c == 'D') {
cin >> k;
if(!k) head = ne[head]; //注意删除头结点这块
else remove(k - 1); //这里也是k - 1
}
}
for(int i = head; i != -1; i = ne[i])
cout << e[i] << ' ';
cout << endl;
return 0;
}
数组模拟双链表
- 之所以在 “D”, “IL”, “IR” 要用 k+1 的原因是 双链表的起始点是2. 所以，每个插入位置k的真实位置应该为 k-1+2 = k+1 (在单链表中为 k-1)。
- 0, 1 节点的作用是边界。0为左边界，1为右边界。他俩在这里有点类似保留字的作用。正因如此，我们的idx也是从2开始
- 最后遍历输出结果的 for (int i = rn[0]; i != 1; i = rn[i])。从 rn[0] 开始是因为 0 为左边界，而终止条件 i==1是因为1为右边界（如果碰到，说明已经遍历完毕）
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N], l[N], r[N];
int idx;
// 初始化
void init()
{
l[1] = 0, r[0] = 1;//* 初始化 第一个点的右边是 1 第二个点的左边是 0
idx = 2;//! idx 此时已经用掉两个点了
}
// 在第 K 个点右边插入一个 X
void add(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k]; //todo 这边的 k 不加 1 ， 输入的时候 k+1 就好
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];
}
int main(void)
{
ios::sync_with_stdio(false);
cin >> m;
init();
while(m--)
{
string op;
cin >> op;
int k, x;
if(op=="R") {
cin >> x;
//! 0和 1 只是代表 头和尾 所以最右边插入只要在指向 1的 那个点的右边插入就可以了
add(l[1], x);
}
else if(op=="L") {
cin >> x;
//! 同理 最左边插入就是 在指向 0的数的左边插入就可以了 也就是可以直接在 0的 有右边插入
add(0, x);
}
else if(op=="D") {
cin >> k;
remove(k + 1);
}
else if(op=="IL") {
cin >> k >> x;
add(l[k + 1], x);
}
else {
cin >> k >> x;
add(k + 1, x);
}
}
//这里是i = r[0] 一直往右走就行
for(int i = r[0]; i != 1; i = r[i])
cout << e[i] << ' ';
cout << endl;
return 0;
}