链表

实现链表的方式

每次创建一个新的链表的时候，就会调用一次new函数来创建新的节点（动态创建链表），这个操作是非常慢的

单链表：算法题中单链表用的最多的是邻接表（n个链表）。应用：存储树和图

双链表：优化某些问题

模拟单链表

1.使用数组来模拟单链表

2.初始化单链表

初始化：默认-1是代表空节点 head 初始值为-1，idx 初始值为0;

3.插入操作（头插法）

创建这个节点的值（e[idx] = x）

head的赋值给当前节点next[i]指针（ne[idx] = head）

让head重新指向头节点（head = idx）

将idx后移（idx++）为下次插入操作做好准备

4.在下标为k的节点后插入x

创建这个节点的值(e[idx]=val)

head的值赋给当前新节点next[i]指针(ne[idx]=ne[k])

将下标为k的节点指向当前节点(ne[k]=idx)

将idx向后移动(idx++)

5.删除下标为k的节点的后一个节点

6.删除头节点

7.例题

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

向链表头插入一个数；

删除第 k 个插入的数后面的数；

在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

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

输入格式

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

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

H x，表示向链表头插入一个数 xx。

D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。

I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

输出格式

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

数据范围

1≤M≤100000
所有操作保证合法。

输入样例：

输出样例：

【参考代码】

总结

一开始在头插法那里卡了好久，其主要原因还是对head, e[N], ne[N], idx;的含义没有理解透，从而导致不理解具体操作的代码是怎么得来的，通过几次手动模拟画图之后就能更好的理解啦！

注：如果文章有任何错误或不足，请各位大佬尽情指出，评论留言留下您宝贵的建议！如果这篇文章对你有些许帮助，希望可爱亲切的您点个赞推荐一手，非常感谢啦