AI_第一部分 数据结构与算法（5.链表上篇）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

本期我们来聊聊链表（Linked list）,今天我们只是会了解一下链表的简单使用以及表示方法，具体的应用我们后文再展开说。

第一、为什么要有链表（历史问题）

从底层的数据结构来看：

现在要存储200MB大小的数据，对于数组而言，它需要一块连续的内存空间来存储，对内存的要求比较高，当内存中没有连续的、足够大的存储空间时，即使是内存中总的剩余空间大于200MB,仍然会申请失败。

对于链表来讲，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块链接起来，所以若申请的是200MB大小的链表，与上面相同情况下，是不会有问题的。这也就有了链表这种数据结构有了存在的“价值”!

第二、单链表结构

链表是通过指针将一组零散的内存链接起来的，我们称内存块为链表的“结点”，除了结点之外为了把每个节点串联起来还必须要记录链表上的下一个节点的地址。我们可以称这个记录下一个节点的指针叫做后继指针，可以用“next”来表示。

从我们给出的图示可以看出：

2.1.第一个和最后一个节点比较特殊，第一个节点一般称为：头结点，最后一个节点称为：尾节点。其中头结点为了记录链表的基地址，有了这个结点就可以依次访问后续的结点，尾节点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址（NULL），这样就表示其为链表的最后一个节点。

2.2.在数组中进行插入和删除操作，为了保持内存的连续性，需要做大量的搬迁工作，所以时间复杂度是O(n),但是对于链表而言，我们只需要考虑相邻节点的指针改变，所以时间复杂度为O(1),

2.3.这样就带来一个问题，链表想随机的访问第i个元素，就没有数组的效率高了，因为链表是非连续存储的，所以只能根据指针一个结点一个结点地依次遍历，直到找到对应的结点。所以链表的随机访问性能没有数组好，需要O(n)的时间复杂度。

2.4.我们给出单链表的数据结构的定义格式，大家可以感受一下，后续编写代码过程中会用到，不要到时候不认识啦：

typedef struct LNode{

ElemType data; //数据域

struct LNode *next; //指针域

} LNode, *LikList;

第三、循环链表

从上面我们得知，单链表的尾节点的指针域是null，那也就意味着它不再指向任何后续节点，而循环链表的尾节点就是要指向链表的表头节点，通过图示大家应该能感受到它其实就像一个环一样的首尾相连，所以才叫做循环链表。

从图中我们可以得出以下结论：

3.1.链表中没有指针域为null的结点，因此在循环单链表中判断链表为空的条件不再是头结点的指针域是否为空，而是它是否等于头指针。

3.2.循环单链表可以从从表中任意结点开始遍历整个链表，有时候对单链表常做的操作是在表头和表尾，此时可以对循环链表不设头指针而设置尾指针，从而提高操作效率，why? 若设置的是尾指针则对表头和表尾的操作时间复杂度都是O(1).

第四、双向链表

在实际的开发过程中用的比较多的是双向链表以及更加复杂的双向循环链表。单向链表只有一个方向，结点只有一个后继结点next指向后继的结点，但是双向链表，它支持的方向是两个，每个节点不止有一个后继结点指针next指向后继的结点，还有一个前驱的指针prev指向前面的结点。

从图中我们可以看出：

4.1.双向链表每个节点需要两个空间来存储后继和前驱节点的地址，若在相同情况下，存储相同多的数据，单链表比双链表需要更小的内存空间，但是双链表支持双向的遍历，这样操作链表的灵活性就提高了。

4.2.从结构上可以看出，双向链表是支持O(1)找到前驱和后继结点，所以在某些情况下效率比单链表高很多

4.3.对于一个有序链表，双链表安值查找的效率也是比单链表高很多，因为我们可以记录上次查找的位置index,每次查询时，根据要查找的值与index的大小关系决定是向前还是向后查找，所以平均只需要查找一半的数据。

4.4.其实你是不是能感觉到我们双链表就是在用空间来换取时间呢？是的，这个用空间换取时间的思想是很重要的，比如你在日常的开发中经常会听到或者不自觉的使用，“做一个映射关系呀”，对的没做，这种做映射关系就是类似于枚举的方式列出来，虽占用了一些空间，但是在获取想要的值的时候确实效率比你循环匹配要高很多。

好了，本期关于链表上篇的分享到此结束，本篇只是介绍了链表的一些基础内容，后续我们会展开来分享，你有任何问题，请留言或者后台与我取得联系，在时间允许的情况下回及时回复你的问题，谢谢理解。

如果你觉得公众号的内容不错，可以推荐于身边的朋友，你的每次肯定和受益都会成为我前进的动力，一起加油！

注意：1.欢迎大家把自己的答案在最下面进行留言，或者后台留言。

2.此系列练习我会给出c语言的代码，当然现在的比较简单，目前还没有代码啦。