算法竞赛基础:双向链表
本文将会介绍在算法竞赛中双向链表的几种使用方式,适合有一定基础的人阅读。
双向链表的结构
一般来说,普通的链表结构是这样的:
struct node {
int num;
node *next;
}
next指针指向下一个链表,这样的结构只能够支持单向查询。
双向链表,顾名思义,就是可以支持双向的访问和查询。
也就是这样的:
struct node {
int num;
node *l, *r;
}
这种链表为访问前后的元素提供的很大的便利性。
C++的STL模板中也有类似的结构:
List
list<int> lis;
List是连续的容器,而vector是非连续的容器,即list将元素存储在连续的存储器中,而vector存储在不连续的存储器中。
向量(vector)中间的插入和删除是非常昂贵的,因为它需要大量的时间来移动所有的元素。链表克服了这个问题,它是使用list容器实现的。
List支持双向,并为插入和删除操作提供了一种有效的方法。
在列表中遍历速度很慢,因为列表元素是按顺序访问的,而vector支持随机访问。
列表模板
示例
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l;
}
它创建一个空的整数类型值列表。
列表也可以使用参数初始化。
示例
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l{1,2,3,4};
}
列表可以通过两种方式初始化。
示例
list<int> new_list{1,2,3,4};
or
list<int> new_list = {1,2,3,4};
list支持的操作有以下这些:
方法 | 描述 |
---|---|
insert() | 它将新元素插入到迭代器指向的位置之前。 |
push_back() | 它在容器的末尾添加了一个新元素。 |
push_front() | 它在前面增加了一个新元素。 |
pop_back() | 删除最后一个元素。 |
pop_front() | 删除第一个元素。 |
empty() | 它检查列表是否为空。 |
size() | 它查找列表中存在的元素数。 |
max_size() | 它找到列表的最大大小。 |
front() | 它返回列表的第一个元素。 |
back() | 它返回列表的最后一个元素。 |
swap() | 当两个列表的类型相同时,它将交换两个列表。 |
reverse() | 它反转了列表的元素。 |
sort() | 它以递增的顺序对列表中的元素进行排序。 |
merge() | 它合并两个排序的列表。 |
splice() | 它将新列表插入到调用列表中。 |
unique() | 它从列表中删除所有重复的元素。 |
resize() | 它更改列表容器的大小。 |
assign() | 它将一个新元素分配给列表容器。 |
emplace() | 它将在指定位置插入一个新元素。 |
emplace_back() | 它将在容器的末尾插入一个新元素。 |
emplace_front() | 它将在列表的开头插入一个新元素。 |
erase() | 删除这个元素 |
但是这种结构往往在大量数据的情况下会超时。我们需要一种更加有效的方式,通常,我们选择空间换时间,因此静态链表通常是更好的选择,接下来介绍一种静态双向循环链表在竞赛中实现的方式。
竞赛方式实现
思路是这样的:
要实现一个静态双向循环链表,需要模拟一个左右指针,在这里,我们选择花费大量空间去用数组的下标代替指针和对应的值:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N 1e5 + 10;
struct node {
int l, r;
int key;
} arr[MAX_N] = {0};
其中,l
和r
分别表示上一个和下一个元素的数组下标。
插入操作
插入操作的思路很简单:
先将新元素的l
和r
指向左右两个元素。
再分别让左右两个元素的r
和l
分别指向新元素本身;
//ll:左元素,rr:右元素, new:新元素
void add(int ll, int rr, int new) {
arr[new].l = ll;
arr[new].r == rr;
arr[ll].r == new;
arr[rr].l == new;
}
这不是一种唯一的实现方式,其中的参数和需求都可以根据具体情况改变。
删除操作
删除操作提供两种思路:
- 第一种与插入操作类似,实现元素的删除
- 第二种更加快速,通过在节点种的key值,去判断是否输出(如果要求输出链表的话)
第一种方式:
void del(int target) {
int l, r;
l = arr[target].l;
r = arr[target].r;
arr[l].r = r;
arr[r].l = l;
第二种方式:
void del(int target) {
arr[target].key = 0; //在对链表元素进行操作时,检测其key值的真值,如果为0,直接不对其进行操作
}
第二种方式虽然没有改变l
和r
的值,但是也能够实现链表访问机制的修改而且还支持数据恢复,相当好用。
查找操作
这种方式是基于上面删除操作时的第二种方式实现的:
bool find(int target) {
return arr[target].key == 1;
}
因为这种特殊的链表结构支持随机访问(正常的链表结构是不支持的),所以查找操作变成检测对应元素的键值是否有效,如果有效,返回一个真值。
遍历操作
以输出全部数值为例:
这里值得一提的是,如果按照这种上文所述的方式去建立双向链表的话,你会发现没有头结点。
具体原因是由于开辟第一个结点时,也就是数组下标为1的时候,结构体中的
l
和r
指向的是1本身,那这个时候如果再多插入几个结点,最后一个结点的r
会指向1,1的l
会指向最后一个结点,这样一来,当你在1之前插入结点时,按理来说头节点会变成新插入的结点,但由于缺少一个指向头节点的指针而丢失链表的头,这显然是我们不想看到的。
解决方法也很简单,我们在数组下标为0的位置创建一个结点作为虚拟头结点,当在真正的头结点之前插入新的结点时,这时候新结点会在0和头节点之间,当我们需要访问头节点的时候,通过0去访问就可以了。文章来源:https://www.toymoban.com/news/detail-821338.html
下面是建立的虚拟头节点0之后的遍历输出操作:文章来源地址https://www.toymoban.com/news/detail-821338.html
void bs() {
// from left to right
for (int i = arr[0].r; i; i = arr[i].r) {
cout << arr[i] << " ";
}
到了这里,关于算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!