单链表笔记其模板

一：定义

是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

二：数组模拟链表

定义：

idx：存储当前已经用到了哪个点

head：头节点下标

e[i]：结点i 的值

ne[i]：表示结点i的下一个下标是。

比如：

1：初始化：

idx=0,head=-1(尾)

2：将x插入头节点

插入数，有一个统一的步骤

新插入点的ne[idx]接上原head指向的结点3，断掉黑色链，head接上新插入点的位置，即idx

代码：

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

3: x插入到下标是k的点后面

与2类似，只是头节点变成了下标是k的结点。

同样的，连新链，断旧链，再把k接倒新点上

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

4：下标是k的点的后面点删掉

这个就比较简单了，把1，2断掉，直接把3接过去即可，所以是，把k指向下一个的下一个

void remove(int k)
{
    //指向下一个的下一个 
    ne[k]=ne[ne[k]];
}

三：模板题

地址：https://www.acwing.com/problem/content/828/