1.linklist.md

引入：程序内部和内存内部

程序内部定义的变量比如int a, b; int *c;都是在程序内部

但是链表，真正存储数据的节点们是在内存内部，程序内部存储的一般是链表的头指针。

头指针相当于一个小抓手，来方便我们处理链表操作

Q：head指向链表，相当于我可以在程序中访问它，为啥不是程序内部呢？

A：当我们改变head的值，会发现无法访问到链表。所以这个相当于一个小爪手。并且head也不是一个完整的链表节点结构，他只是存了首节点的地址

链表的特征

1. 每个节点至少包含两个部分：数据域与指针域
2. 每个节点通过指针域的值形成一个线性结构
3. 查找节点$O(n)$，插入节点$O(1)$，删除节点$O(1)$
4. 不适合快速的定位数据，适合动态的插入和删除数据的应用场景。

链表和二叉树有什么关系？

没什么关系！虽然它们俩在实现方式上类似（链表是一个指针域，二叉树再加一个指针域，双向链表还是两个指针域呢！）

但是逻辑结构上来说完全不是一个东西！

链表的操作：插入、删除--都要找到待操作节点的前一个节点

先找到待插入节点的前一个节点，将新节点指向前一个节点的后一个节点。

为什么不能先将前一个指向新节点呢？这样就无法访问到后一个节点了，后边的节点都丢失无法访问了。

这就造成了内存泄漏。

这里就要深刻理解线程是程序执行的最小单位，进程是操作系统分配资源的最小单位

发生内存泄漏怎么办呢，操作系统杀死这个进程之后就能释放了。所以操作系统、守护进程一定不能内存泄漏。

单向循环链表

一般来说，我们将head指针指向尾节点，这样的话我们若要在第一个节点处插入新节点就可以直接操作。因为新节点的上一个节点正是尾节点

如果，head指向的是第一个节点，那么我们在第一个节点处插入新节点就要向后走n-1步插入，这和我们的常理不符合。

注意呢，若向尾节点后边插入新节点，就要改变head的值哦。尾节点发生了变化。

向0号位插入和向尾节点的后一位插入是不一样的！！！

课后自己看双向链表

链表的应用场景

1.操作系统内部的动态内存分配

如图：

比如我们申请了橙色区域1GB内存，剩下两块内存就不连续了。这两块蓝色的正是靠链表链接起来的

2.LRU缓存淘汰算法

Least Recently Used 最近最少使用淘汰算法

CPU取数据可以有两种方式，

CPU->MEM->DISK

CPU->DISK

在MEM中存储的比较常用的程序段，页面就是靠链表穿起来的，实际上是哈希链表

当需要新的页面或者数据的时候，先看缓存中（也就是上图的链表）有没有此数据，没有的话就在尾部进行添加（假设添加了数据5 就要删除数据1 因为页面大小就为4）。如果达到表长，就删除最前面的(也就是最近未使用)的。