AcWing 826. 单链表

题目传送门

一、链表有什么用，用数组不就可以了吗？

数组是一种支持随机访问，但不支持在任意位置插入或删除元素的数据结构。与之相对应，链表支持在任意位置插入或删除，但只能按顺序依次访问其中的元素。

二、理解与感悟

本节主要用数组模拟链表，速度更快，并且为静态存储。
\(e[N]\)存储节点的值，\(ne[N]\)存储该节点下一节点的下标。
注意：下标从零开始，第\(k\)个数对应数组\(e[k-1]\)；在删除节点时，要判断该节点是否为头节点，若为头节点，直接\(head\)指向该节点所指向的位置，即\(head = ne[head]\);

1、将链表初始化，\(head\)指向\(-1\)。

2、将\(x\)插到头结点。

3、在第\(k\)个数后面插入\(x\)

4、删除第\(k\)个节点后面的数

三、C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

//单链表
int e[N];   //存值
int ne[N];  //存下一个结点的索引
int idx;    //当前可以用的索引号
int head = -1;   //头指针,描述第一个结点的索引,-1表示单链表结尾，初始化时链表为空，所有head指向tail=-1

/**
 * 功能：向链表头插入一个数
 * @param x
 */
void add_to_head(int x) {
    /*四步法
     1、存值
     2、将头指针指向的结点标识为下一个结点
     3、将头指针指向当前结点
     4、idx++准备下一个可用的索引号
    */
    e[idx] = x, ne[idx] = head, head = idx++;
}

/**
 * 功能：将x插到下标是k的点后面
 * @param k
 * @param x
 */
void add(int k, int x) {
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

/**
 * 功能：将下标是k的点后面的点删掉
 * 比如想删除第k个结点，那么需要传入k-1,因为k-1的下一个结点才是k
 * @param k
 */
void remove(int k) {
    ne[k] = ne[ne[k]];
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);

    //m次操作
    int m;
    cin >> m;

    while (m--) {
        int k, x;
        char op;
        cin >> op;
        //头插法:x
        if (op == 'H') {
            cin >> x;
            add_to_head(x);
        } else if (op == 'D') {
            //表示删除第k个插入的数后面的数（当k为0时，示删除头结点）。
            cin >> k;
            //删除头结点需要特判，否则会丢失关系
            if (k == 0) head = ne[head];
                //第k个插入的数，那么在数组中下标是k-1,所以调用时需要使用remove(k-1,x)
            else remove(k - 1);
        } else {
            //在第k个插入的数后插入一个数
            cin >> k >> x;
            //第k个插入的数，那么在数组中下标是k-1,所以调用时需要使用add(k-1,x)
            add(k - 1, x);
        }
    }
    //遍历单链表
    for (int i = head; i != -1; i = ne[i])cout << e[i] << " ";
    return 0;
}