今天我们来讲一下数据结构的第一个知识点 -- 单链表

何为数据结构呢?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 ---- 百度百科

待会将要介绍的是单链表,何为链表呢。可以把它想象成一辆火车,每节车厢都数据域和指针域,数据域用于存放数据,指针域用于与下一节车厢建立连接关系,相当于车厢之间的连接部分。指针将这一个个结点串连起来就是链表了

由于cpp动态链表生成一个结点的 new() 函数较为耗时,而一般用到链表的题,数据范围都是 $1e5$ ~ $1e6$,光是初始化链表就几乎超时了。所以本次单链表的实现用数组模拟。虽然动态链表也能用结构体数组来实现, 如果是这样的话,还不如用数组模拟,这样代码还短

现在就来看看数组是如何模拟单链表的吧~

int head , idx; // head为头指针,这里暂时忽略首元结点这些概念,idx表示用到的第几个结点,仅作标识作用
int e[N] , ne[N]; // e数组为数据域,用于存放单链表对应节点的值,ne数组为指针域,用于存储指向下一个节点的next指针,因为是用数组模拟,所以指针域存的是下标idx。也因为是数组,理论上我们是可以在O(1)的时间复杂度取到值,前提是这个操作是合法的(虽然没有释放内存,但是改变了指针的指向)

// 初始化单链表
void init() {
    head = -1 , idx = 0; // 这里有个小坑,idx的初始值可为0也可以是1。因为单链表不像双链表,没有直接前驱,不能访问到前驱结点,插入的时候是在第k个插入的结点后面的位置插入。所以应该注意是从0开始计算个数还是1,当然了,这纯属个人习惯,都无所谓
}

// 将结点插入到头指针后
void insert_to_head(int x) {
    e[idx] = x ,  ne[idx] = head , head = idx ++;
}

// 将结点插入到第k个插入的结点后
void insert(int k , int x) {
    e[k] = x , ne[idx] = ne[k] , ne[k] = idx ++;
}

// 删除头指针指向的结点
void del_head() {
    head = ne[head];
}

// 删除第k个插入的结点后的结点
void del(int k) {
    ne[k] = ne[ne[k]];
}

如果看到这里还是不理解,就看看下面两张gif吧
单链表添加结点
单链表删除结点

理解完模板之后就来实操吧
AcWing 826.单链表

题目描述

实现一个单链表,链表初始为空,支持三种操作:

  1. 向链表头插入一个数;
  2. 删除第 $k$ 个插入的数后面的数;
  3. 在第 $k$ 个插入的数后插入一个数。
    现在要对该链表进行 $M$ 次操作,进行完所有操作后,从头到尾输出整个链表。

注意 :题目中第 $k$ 个插入的数并不是指当前链表的第 $k$ 个数。例如操作过程中一共插入了 $n$ 个数,则按照插入的时间顺序,这 $n$ 个数依次为:第 $1$ 个插入的数,第 $2$ 个插入的数,…第 $n$ 个插入的数。

输入格式

第一行包含整数 $M$,表示操作次数。

接下来 $M$ 行,每行包含一个操作命令,操作命令可能为以下几种:

  1. H x,表示向链表头插入一个数 $x$。
  2. D k,表示删除第 $k$ 个插入的数后面的数(当 $k$ 为 $0$ 时,表示删除头结点)。
  3. I k x,表示在第 $k$ 个插入的数后面插入一个数 $x$(此操作中 $k$ 均大于 $0$)。
输出格式

共一行,将整个链表从头到尾输出。

数据范围

$1 \le M \le 100000$
所有操作保证合法。

输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5

C++代码
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;

int m;
int head , idx , e[N] , ne[N];

void init() {
    head = -1 , idx = 0;
}

void insert_to_head(int x) {
    e[idx] = x , ne[idx] = head , head = idx ++;
}

void del(int k) {
    ne[k] = ne[ne[k]];
}

void insert(int k , int x) {
    e[idx] = x , ne[idx] = ne[k] , ne[k] = idx ++; 
}

int main() {
    
    scanf("%d" , &m);
    
    init();
    
    while(m --) {
        char op[2];
        int k , x;
        scanf("%s" , op);
        if(op[0] == 'H') {
            scanf("%d", &x);
            insert_to_head(x);        
        }
        else if(op[0] == 'D') {
            scanf("%d", &k);
            if(!k) head = ne[head];
            else del(k - 1);
        }
        else {
            scanf("%d %d" , &k , &x);
            insert(k - 1 , x);
        }
    }
    
    for(int i = head; i != -1; i = ne[i]) printf("%d " , e[i]);
    
    return 0;
}

引用

引用一些大佬的题解

zning AcWing 826. 单链表_Java

Hasity AcWing 826. 为什么不用课本上的结构体?第 k 个插入的数在哪里等答疑

Bug-Free AcWing 826. 单链表

大海呀大海 AcWing 826. 单链表

Q.E.D.


都懂一点,不是很懂的小捞仔