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

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

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

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

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

今天我们继续上节的内容--链表。上节我们分享的都是一些有关链表的基本内容，今天我们主要从代码的角度来聊聊有关链表的内容。

第一、如何理解指针以及引用的含义？

我知道很多同学，一提到指针，就翻白眼，哈哈，其实也没有这么可怕，我今天用自己的方式给大家解释一下指针以及引用的相关操作。

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针。或者也可以这样理解：指针中存储了一个变量的内存地址，指向了这个变量。

我们通过一个图来给大家解释一下：

我们在内存中分给空间的时候每个存储单元都有一个地址标识的，就像我们举的例子10000001H、10000002H 这个就是唯一识别这个存储单元的“钥匙”，所以next指针会存储它要访问的下一个存储单元的这个“钥匙”，通过这个“钥匙”就会去找对应的存储单元了。

我们还是通过图来解释一个语句，好多人搞了好久还是没有明白里面到底是个什么情况，假设图中的A让其为p结点，B为q结点，则图中的这种链表链接可以用：p->next = q；表示出来，

这行代码是什么意思呢？p结点中的next指针存储了q结点的内存地址，也就是那把“钥匙”。等号右边q赋值于等号左边的next指针意思是：next指针指向q这个变量(存储单元)。（大家仔细体会一下我这里说的“赋值”，和“指向”这两个词的意义）。

第二、指针丢失和内存泄漏问题

我们举一个例子：目前呢有一个a->next = b; b->next = null;

现在我们想在a和b结点之间插入一个节点x,目前指针L指向a结点，若我们把上面的需求用代码实现成如下：

p->next = x;

x->next = p->next;

请问上述代码能否满足我们的需求呢？答案是No.p->next = x 完成后就不再指向b结点了，而是指向了x结点。所以第二行的x->next = p->next 其实就是自己指向自己，所以链表也就段成两节，从节点b开始到最后的所有节点都无法访问了。

对于c语言或者c++在插入和删除一个节点的时候，一定要注意操作的顺序，要将节点x的next指针指向结点b，然后再把结点a的next指针指向x,这样才会保证不丢失指针，导致内存的泄漏，so，对于刚才的问题我们只需要将上面的两行代码顺序颠倒就可以了。

对于删除一个节点的时候，大家要注意需要手动的释放内存空间。否则也会出现内存泄漏的问题。

第三、留意边界条件的处理（重点）

在软件开发过程中，代码的一些边界或者异常情况下，很容易产生bug，so，在写完代码后需要检查边界条件是否考虑全面，以及代码在边界条件下运行是否正常。面试的过程中，更多的出错地方就是边界条件考虑的有问题或者写的代码在边界上会数组越界等问题。

how find ?

3.1.如果链表为空的时候，代码是否正常工作。

3.2.如果链表只包含一个节点，代码是否正常工作

3.3.代码逻辑在处理头结点和尾节点的时候是否能正常工作

第四、如何使用python来模拟实现链表的操作？

不知道各位在面试的时候有没有遇到过写算法的还让你使用c语言写的，我当时是遇到过的，当然也有那种语言不限的，python大法好，今天就说一下，如何使用python 来模拟实现c来实现链表的操作。以后你去面试的时候也多一种选择，可以用python来搞定算法题目。

class LinkList(object): def __init__(self,data)

self.data = data

self.next = None

A = LinkList(2)

B = LinkList(3)

A.next = B

好了，通过以上语句就可以模拟出我们上文中图片的内容，和c语言实现的效果是一致的，鉴于这个代码比较简单我就不做过多的解释了，有需要了解python基础内容的可以在后台菜单栏中找到相应的知识点练习。

第五、如何基于链表来实现LUR缓存淘汰算法呢？

基本思路如下：

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有新的数据被访问时，我们从链表头开始顺序遍历链表。

5.1.如果此时数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后在插入到链表的头部。

5.2.此时的数据不在缓存链表中，又可以分为两种情况：

5.2.1.此时缓存没有存满，则将此结点直接插入到链表的头 部。

5.2.2.如果此时缓存已满，则链表尾节点删除，将新的数据 结点插入到链表的头部。

通过以上的策略我们就可以实现一个LRU缓存。

好了，本期关于链表下篇的分享到此结束，下次开始我们分享栈有关的内容，你有任何问题，请留言或者后台与我取得联系，在时间允许的情况下回及时回复你的问题，谢谢理解。

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

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

2.此系列练习我会给出c语言的代码，以及pyhton代码。