一、链表的定义
线性表的链式存储就是链表。
它是将元素存储在物理上任意的存储单元中，由于⽆法像顺序表⼀样通过下标保证数据元素之间的逻辑关系，链式存储除了要保存数据元素外，还需额外维护数据元素之间的逻辑关系，这两部分信息合称结点（node）。即结点有两个域：保存数据元素的数据域和存储逻辑关系的指针域。
二、定义-创建-初始化
1. 两个⾜够⼤的数组，⼀个⽤来存数据，⼀个⽤来存下⼀个结点的位置
2. 变量h ，充当头指针，表⽰头结点的位置
3. 变量id ，为新来的结点分位置
const int N = 1e5 + 10;
int h; // 头指针
int id; // 下⼀个元素分配的位置
int e[N], ne[N]; // 数据域和指针域
// 下标 0 位置作为哨兵位
// 其中 ne 数组全部初始化为 0，其中 ne[i] = 0 就表⽰空指针，后续没有结点三、头插
// 头插
void push_front(int x)
{
// 先把 x 放在⼀个格⼦⾥⾯
id++;
e[id] = x;
// 修改指针，顺序不能颠倒！
// 1. x 的右指针指向哨兵位的后继
// 2. 哨兵位的右指针指向 x
ne[id] = ne[h];
ne[h] = id;
}四、遍历链表
// 打印链表
void print()
{
// 定义⼀个指针从头结点开始
// 通过 ne 数组逐渐向后移动
// 直到遇到空指针
for(int i = ne[h]; i; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl << endl;
}通过i是否等于0来判断。
五、按值查找
解法⼀：遍历整个链表即可。
解法⼆：如果存储的值数据范围不⼤，可以⽤哈希表优化。（不知道哈希表是什么没有关系，只要知道mp数组的作⽤，把它当成⼀个标记数组即可。）
int mp[N]; // mp[i] 表⽰ i 在这个元素存放的位置
/*
push_front 和 insert 的时候，打上标记
mp[x] = id; // x 这个元素存放的位置是 id
erase 的时候，消除标记
mp[x] = 0;
*/
// 查询值为 x 的元素存储的位置
int find(int x) // 注意，这⾥传⼊的是元素的值
{
// 策略⼀：先找到 x，然后返回 x 后⾯的元素
for(int i = ne[h]; i; i = ne[i]) // 遍历链表
{
if(e[i] == x) // 如果找到 x
{
return i;
}
}
// 找不到就返回 0
return 0;
// // 策略⼆：使⽤哈希表优化
return mp[x]; // mp[x] ⾥⾯就存着 x 这个元素存储的位置下标
}如果运用map操作，那么在头插中应该这样写
id++;
e[id] = x;
mp[x] = id;
ne[id] = ne[h];
ne[h] = id;
六、在任意位置之后插⼊元素
// 在存储位置为 p 的元素后⾯，插⼊⼀个元素 x
void insert(int p, int x) // ⼀定要注意，这⾥的 p 是位置，不是元素
{
id++; // x 这个元素分配的位置
e[id] = x; // 将 x 放在 id 位置处
ne[id] = ne[p]; // x 指向 p 的后⾯
ne[p] = id; // p 指向 x
}和头插操作差不多。
就是把ne[h]换成了ne[p]。
若使用mp数组，应该
id++;
e[id] = x;
mp[x] = id;
ne[id] = ne[p];
ne[p] = id;七、删除任意位置之后的元素
// 删除存储位置为 p 后⾯的元素
void erase(int p) // 注意 p 表⽰元素的位置
{
if(ne[p])
{
mp[e[ne[p]]] = 0; // 将 p 后⾯的元素从 mp 中删除
ne[p] = ne[ne[p]]; // 指向下⼀个元素的下⼀个元素
}
}所有测试代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// 创建
int e[N], ne[N], h, id;
int mp[N]; // mp[i] 表⽰ i 这个数存储的位置
// 遍历链表
void print()
{
for(int i = ne[h]; i; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl << endl;
}
// 头插
void push_front(int x)
{
id++;
e[id] = x;
mp[x] = id; // 标记 x 存储的位置
// 先让新结点指向头结点的下⼀个位置
// 然后让头结点指向新来的结点
ne[id] = ne[h];
ne[h] = id;
}
// 按值查找
int find(int x)
{
// // 解法⼀：遍历链表
// for(int i = ne[h]; i; i = ne[i])
// {
// if(e[i] == x) return i;
// }
// return 0;
// 解法⼆：⽤ mp 数组优化
return mp[x];
}
// 在任意位置 p 之后，插⼊⼀个新的元素 x
void insert(int p, int x)
{
id++;
e[id] = x;
mp[x] = id;
ne[id] = ne[p];
ne[p] = id;
}
// 删除任意位置 p 后⾯的元素
void erase(int p)
{
if(ne[p]) // 当 p 不是最后⼀个元素的时候
{
mp[e[ne[p]]] = 0; // 把标记清空
ne[p] = ne[ne[p]];
}
}
int main()
{
for(int i = 1; i <= 5; i++)
{
push_front(i);
print();
}
//cout << find(1) << endl;
//cout << find(5) << endl;
//cout << find(6) << endl;
// insert(1, 10);
// print();
// insert(2, 100);
// print();
erase(2);
print();
erase(4);
print();
return 0;
}
