算法基础04 数据结构:单链表+双链表
1.单链表
「常见实现方式」:
- STL vector :直接使用库函数,方便。
- 结构体: 最常规的数据结构,按部就班的来。
- 静态数组:数组模拟在算法题中提高运行速度。
「采用静态数组」:
「变量介绍」:
e[N]
: 存储每一个插入的元素的值。
ne[N]
: 存储每一个元素的下一个元素对应的的数组下标。
head
: 存储 头节点的下标。
idx
: 是计量数,可以理解为每插入一个元素都会追加在e[N]数组里,而idx表示当前到第几个该插入了,插入后idx++。
1 | int e[N], ne[N], head, idx; |
「实现思路:」
初始化 head 为 -1,首先head指向空。初始化 idx 为0,从下标0开始记录。
指令为 ‘H’,表示在链表最头部插入,也就是头节点,对应代码
1
2
3
4
5
6
7
8
9// 在链表头插入
void into_head(int x)
{
e[idx] = x; // 先存下当前要插入元素
ne[idx] = head; // 让 当前点的指向的下一个元素的下标 为 head的下一个,
//因为头结点之前可能指向 a,你要在头结点插入一个新元素 b,那就形成了head ----> b(新) ----> a(旧)的关系。
head = idx; // 之后让 head 指向新插入的元素
idx++; // 操作完成,idx++
}指令为 ‘I’,则表示在第k个数后面插入一个新元素,因为数组下标从0开始,则k-1就对应第k个数
1
2
3
4
5
6
7
8// 在第 k个插入的数后插入一个数
void add_to_k(int k, int x)
{
e[idx] = x; // 思路大致相同
ne[idx] = ne[k]; // 让 新插入的元素的下一个指向为 k 的下一个。
ne[k] = idx; // 之后让 k指向新插入的元素
idx++;
}指令为 ‘D’,则表示删除 第k个元素后面的数。
1
2
3
4
5// 移除第k个后面的数
void remove(int k)
{
ne[k] = ne[ne[k]]; // 例如 a --> b -- >c ,直接 a --> c,就表示删除了中间元素
}
「完整代码:」
题目链接:826. 单链表 - AcWing题库
1 |
|
2.双链表
「常见实现方式:」
- 结构体:最基础,常用。
- 静态数组:数组模拟,速度较快。
「静态数组方式:」
「变量介绍:」
e[N]
: 存储每一个插入的元素的值。
l[N]
: 存储每一个元素的左链接元素下标。
r[N]
: 存储每一个元素的右链接元素下标。
idx
: 是计量数,可以理解为每插入一个元素都会追加在e[N]数组里,而idx表示当前到第几个该插入了,插入后idx++。
「注意:」
这里 默认初始占据数组两个空间,l[1]
and r[0]
互相指向
r[0]
:r[0] = 1,表示虚拟头节点,初始指向 1,1也代表着链表结束,后续添加元素指向新的头结点元素下标。
l[1]
:l[1] = 0,表示虚拟尾节点,初始指向 0,0表示虚拟头结点的位置,后续添加新元素指向新的尾节点元素下标。
「实现思路:」
1.以下插入操作都可以通过一个函数解决:
L x
,表示在链表的最左端插入数 x。(最左端可以理解为在0的右边插入,即让 r[0] = idx(大概意思)
)
R x
,表示在链表的最右端插入数 x。 (在最右端可以理解为在尾端点的 左元素 的右边插入,即在 r[l[1]] = idx(大概意思)
)
IL k x
,表示在第 k个插入的数左侧插入一个数。 (第k个数的左边,即 第 k - 1插入的数的右边,这里注意,不是直接寻找第k-1个数,而是寻找第k个数的左边,然后再在这个元素的右边插入,即 r[l[k+1]] = idx(大概意思,因为idx从2开始,k+1对应第k个数)
)
IR k x
,表示在第 k 个插入的数右侧插入一个数。
1 | // 往第k个右边插入数据 |
2.删除操作就一个函数:
让第k个数的右边的左边等于第k个数的左边,让k的左边的右边等于k的右边。
1 | void removeK(int k) |
「完整代码:」
1 | #include <bits/stdc++.h> |