数据结构单链表的模拟实现

一、链表的定义

线性表的链式存储就是链表。
它是将元素存储在物理上任意的存储单元中，由于⽆法像顺序表⼀样通过下标保证数据元素之间的逻辑关系，链式存储除了要保存数据元素外，还需额外维护数据元素之间的逻辑关系，这两部分信息合称结点（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;
}