链表——chain

一、为什么需要链表？

在C语言的有序表中，无论是插入或删除一个元素，效率非常低下，特别是栈和队列这种数据结构，如果想去掉其中的一个元素，其他元素还需要先出去，需要排队，这里面有先后的顺序存在，否则出不去，简直急死人。那么有没有一种简单的数据结构，能够在插入和删除元素时能够高效地实现？有，那就是本文的主题——链表

链表存储的结点既有数据又有指针，数据还是原来的数据，而指针是指向下一个结点的位置。有了指针，数据完全不需要再按顺序进行排列，即可以放在存储区域的任何位置，这就是链式表示方法，这种链式结构的线性表称为链表。

二、链表如何表示 

现举例说明链表：

现有常见的有序表如下：

那么怎么表示链表呢？咱们慢慢来，将上面有序表位置打乱。

上面的数字是索引，先再引入一个数组，存放下一个数据的位置

我们可以看到，在But对应的数字为1，索引为1的是Cut，Cut对应的数字是3，索引3的数据是Out，Out对应的是6,索引为6的数据是Put，Put对应的数字是0,0表示链表的结尾。

于是这种链式结构就形成了，是不是比较纠结？一团毛线？哈哈哈，来个简单的表示方法，这是常见的链表表示方法：

其中结点的存储位置不一定是有序的，也可能比较乱，但都通过指针进行了连接。链表最后一个结点的指针是0，这种单向链表是最简单的有序链表，简称为链。如果链中结点数为0，那么链表为空链。

三、链表的操作 

下面我们就进行链表的插入和删除操作，

首先看如何插入，如果要在Cut和Out之间添加一个Gut怎么办？

只需要找一个空结点即可，此结点数据项放Gut，指针（链域）指向Out，同时将Cut的链域指向Gut即可，那么这个新的链表就已经构建成功。

在这个插入的过程中只需有空结点存在，并且加入指针，而其他数据的位置无需改变。

【用闪电将两个情侣分开，他们之间就不会有瓜葛了。然而插入了第三者，关系又复杂了】

删除：如果删除Gut怎么办？

很简单，只需将Cut的链域指向Out，这个删除过程就完成了，是不是懵逼？问号脸？

当我们从第一个结点遍历时，再也见不到Gut了，尽管Gut还与Out有指针，但Gut已经出局了。

【有没有关系有什么用呢？即使还留着你的联系方式，但人家都结婚了】

四、其他

由于时间所限，推荐算法不是一般的有难度，所以一两天难以总结，因而补充了个数据结构。

这只是单向链表，即最简单的链，其实Python的列表已经够强大了，根本无需考虑这些问题。

比如insert只要指定插入的索引位置即可，而删除用pop指定索引即可。不再演示。

另外链表还可与栈和队列结合起来，即链式栈和链式队列。