何为链表
链表和数组都可用于存储数据,其中链表通过指针来连接元素,而数组则是把所有元素按次序依次存储。
不同的存储结构令他们有了不同的优势:
链表可以方便地删除、插入数据,操作次数是O(1)。
但也因为这样寻找读取数据的效率不如数组高,在随机访问数据中的操作次数是O(n)。
数组可以方便的寻找读取数据,在随机访问中操作次数是O(1)。但删除、插入的操作次数却是却是O(n)次。
构建链表
关于链表的构建使用到指针的部分比较抽象,光靠文字描述和代码可能难以理解,我们配合作图来理解。
单向链表
单向链表中包含数据域和指针域,其中数据域用于存放数据,指针域用来连接当前结点和下一节点。
struct Node {
int value;
Node *next;
}
上述方法是用结构体来实现链表,在算法题中不常用.因为太慢了
常用的是用数组模拟链表-静态链表.用数组模拟链表,需要有一些准备
- 创建一个head,存储链表头
- 创建一个e[]数组,存储节点的值
- 创建一个ne[]数组,存储节点的next指针
- 创建一个idx,表示当前用到了哪个节点
定义好这些之后,我们就可以开始模拟链表了.
首先初始化
// 初始化
void init()
{
head = -1;
idx = 0;
}
初始化之后,我们就可以来实现链表的插入,删除等操作了
头插法
首先,将待插入的节点的next指针指向头结点next指针指向的位置,再将头结点的next指针指向待插入的节点
有点绕,上图
代码:
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a;
ne[idx] = head;
head = idx ++ ;
}
在任意节点插入节点
假设要在K节点后插入一个节点,首先,将待插入的节点的next指针指向k节点next指针指向的位置.
再将k节点的next指针指向待插入的节点.
上图
//在第K个节点插入
void add_k(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
删除节点
假设要删除K后面的一个节点,只需要将k的next指针指向待删除节点next指针指向的位置
上图
代码:
//删除一个节点
void remove(int k)
{
ne[k]=ne[ne[k]];
}
以上就是静态链表的基本方法啦,一起练练?
ACwing 826.单链表
双向链表
双向链表中同样有数据域和指针域,不同之处在于指针域有左右(或上一个、下一个)之分,用来连接上一个节点、当前结点、下一个结点。用人话来说,就是有两个指针,一个指针指向前一个节点,一个指针指向后一个节点
和单链表一样双链表也是可以用数组来模拟,也需要准备
- 创建一个e[]数组,表示节点的值
- 创建一个l[]数组,表示节点的左指针
- 创建一个r[]数组,表示节点的右指针
- 创建一个idx,表示当前用到了哪个节点
定义好这些之后,我们就可以开始模拟链表了.
首先初始化
// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
初始化完成之后,就可以来实现链表的插入,删除等操作了
在任意位置插入节点
假设要在k节点的右边插入一个节点.
1. 将待插入的节点(a4)的左指针指向k节点
2. 将a4的右指针指向k节点右指针指向的位置
3. 然后将k节点的右指针指向的节点的左指针指向a4太绕了
4. 最后将k节点的右指针指向a4
上图
如果要在k节点的左边插入一个节点呢? 小问题,自己想去
// 在节点k的右边插入一个数x
void insert(int k, int x)
{
e[idx] = x;
l[idx] = k, r[idx] = r[k];
l[r[k]] = idx, r[k] = idx ++ ;
}
删除节点
假设要删除k节点
1. 将k节点的左节点指向k节点的右节点
2. 将k节点的右节点指向k节点的左节点
有手就行,上图
// 删除节点k
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
双链表的实现方法也完成了.一起练练?
ACwing 827.双链表
图画的漂亮呀
谢谢,hh