链表

今天开始学链表了，我觉得学链表前很有必要先看看数组

数组

不得不承认数组的确是日常使用中最常用的手段之一，但是啊，数组的使用是有局限的(1)在编译期就要做到大小，不然是不行哒。2数组中的数据在内存中是以相同的距离隔开的，这就意味着我们要想在数组中插入数据变的非常困难。如果我们偏要插入数据的话则需要去移动改数组的其他数据。这样感觉非常不妙而且让人感觉非常烦躁。

数组定义

一组线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

关键词解释

• 线性表：每个线性表上的数据最多只有前和后两个方向。
  除了数组，链表、队列、栈都是线性表结构，然而线性表有分为顺序表和链表，顺序表可以简单的理解为数组这个概念。

联想到非线性表：数据之间并不是简单的前后关系。
如，二叉树、堆、图等

• 连续的内存空间和相同类型的数据
  正因为有了这两个限制，才使得数组有了随机访问的特性；
  也正是因为这两个限制，使得数组的删除、插入操作效率很低。

如何实现根据下标随机访问数组元素？

计算机会给每个内存单元分配一个地址，再通过地址来访问内存中的数据。
而计算机通过寻址公式来计算元素存储的内存地址：

//a[i]的地址就是从首地址偏移i*data_type_size的位置
a[i] = base_address + i * data_type_size

base_address: 内存块的首地址
data_type_size：数中每个元素的大小；根据存储的数据类型而定，如int型，该值为4

为什么数组要从0开始编号，而不是从1开始呢？

若数组从1开始计数，那么上面的公式就变成

a[i] = base_address + (i-1) * data_type_size

修改后，每次随机访问数组元素都多了一次减法运算，对于CPU就多了一次减法指令。

两个操作

数组的插入操作

• 效率低的原因：将某个数据插入到数组中的第i个位置。为了给新来的元素腾出这个位置，需要移动后面的i~n个元素，复杂度为O(n);
• 改进方法：当数组是无序的，简单的方法就是将原来第i个位置上的元素放到数组最后，然后将新来的元素放到第i个位置。复杂度为O(1);

数组的删除操作

与插入操作类似，若删除第i个位置的元素，需要搬移后面的i~n个元素，才能保证内存的连续性。

• 复杂度：若删除开头元素，最坏复杂度为O(n)；若删除数组末尾元素，最好复杂度为O(1)；平均复杂度为O(n)。
• 改进方法：不要求数组中数据的连续性，就可将多次删除操作集中在一起执行。
  每次删除元素时，并不真正搬移元素，而是记录下数据已被删除。当数组没有更多空间存储数据时，再执行一次真正的删除操作（做数据元素的搬移工作）

数组的访问越界问题

分析以下一段代码：

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

问题

不是只打印三行“hello world”；而是无限打印

原因

数组大小为3，a[0]，a[1]，a[2]，而我们的代码 for 循环的结束条件错写为了i<=3 而非 i<3，所以当 i=3 时，数组 a[3] 访问越界。
根据我们前面讲的数组寻址公式，a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 a[3]=0 就相当于 i=0，所以就会导致代码无限循环。

注：例子中死循环的问题跟编译器分配内存和字节对齐有关。数组3个元素，加上一个变量i。4个整数刚好能满足8字节对齐，所以i的地址恰好跟在a[2]后面，导致死循环。如果数组本身有4个元素，则这里不会出现死循环。因为编译器64位操作系统下，默认会进行8字节对齐，变量i的地址就不会紧跟在数组后面了。

Key

1 . 常会问的一个面试题：数组和链表的区别？
正确表述：链表适合插入、删除操作，时间复杂度为O(1)；数组适合随机访问数组元素(而不应该说查找)，根据下标随机访问的时间复杂度为O(1)。
明确的点：数组是适合查找，但查找的时间复杂度不为O(1)。即便是排好序的数组，用二分查找，时间复杂度也是O(nlogn)。

2 . 数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
在这种情况下，一般都会出现莫名其妙的逻辑错误，就像上面举的那个例子，debug的难度非常的大。而且，很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。

3 . 二维、多维数组如何寻址？
行优先

int a[d1][d2][d3];
int *p0 = &a[0][0][0];
int *p = &a[i][j][k];
int idx = i * (d2*d3) + j * d3 + k
ASSERT( p0 + idx == p);

但是我们亲爱的链表就不存在这样的问题

链表是节点的集合，节点中储存着数据并可以链接到其他节点，是不是很方便，也就是是通过这种方式我们可以链接到内存中的任何一个位置，不好意思链表真的可以为所欲为；每个节点都存储着链表其他地方的节点，因此我们非常容易的从一个节点到另一个节点，但是最灵活的还是指针，抱歉指针真的真的可以为所欲为

如何用链表实现LRU缓存淘汰算法？

缓存

• 缓存定义：一种高效数据读取性能的技术，比如常见的CPU缓存、数据库缓存、浏览器缓存等。缓存在计算机软件、硬件开发中应用都很广。
• 缓存特点：大小有限，被用满时，需要清理一部分数据，而哪些数据应该被清理哪些应该被保留，由缓存淘汰策略决定。

缓存淘汰策略

常见的缓存淘汰策略有：FIFO（First in,First out）先进先出策略、LFU（Least Frequently Used）最少使用策略、LRU（Least Recently Used）最近最少使用策略。

三种链表

链表通过指针将一组零散的内存块串联在一起。其中内存块叫做链表的结点，记录结点地址的叫做指针。链表的第一个结点叫头结点，最后一个结点叫尾结点。

单项链表

如果链表中只含有指向后继节点的链接这样的就被叫做单链表大概

单链表的“尾结点”，它的指针并不指向下一个结点，而是指向一个空地址NULL

懒得废话直接扔动图，动态图来自visualgo

搜索（ps谷歌拓展截下来的gif图凑合看吧）

插入

删除

（ps）单链表插入和删除操作，复杂度为O(1)

循环链表

一种特殊的单链表，与单链表的区别就在于尾结点，其尾结点指向链表的头结点

相比于单链表，循环链表的优势在于从链尾到链头很方便。著名的约瑟夫问题，就适合这种数据结构。

双向链表

单链表只有一个方向，结点只有一个后继指针next指向后面的节点。双向链表有两个方向，一个后继指针next和一个前驱指针pre。

双向链表在某些情况下的插入、删除操作比单链表更高效。
例如删除操作，从链表中删除一个数据，有两种情况：

• 删除链表中值等于某个给定值的结点
• 删除给定指针指向的结点

对于第一种情况，无论单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再将其删除。
尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况，已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点。这种情况下单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要 O(1) 的时间复杂度。

以上的情况涉及到一个空间换时间的设计思想：双向链表更费内存，但仍比单链表应用更广泛。

缓存实际上就是利用了空间换时间的设计思想。
如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。
但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。

若内存空间充足，如果更加追求代码的执行速度，就选择空间复杂度相对较高，时间复杂度相对较低的算法和数据结构，例如，缓存技术。
若内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间。

数组与链表对比

时间复杂度

删除、插入：链表O(1)、数组O(n)

随机访问操作：链表O(n)、数组(1)

缓存支持

数组在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。

链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

原因

CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取要访问的地址，而是读取一个数据块，并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。
这样就实现了比内存访问速度更快的机制，也是CPU缓存存在的意义：为了弥补内存访问速度过慢与CPU执行速度快之间的差异。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。

灵活性

数组大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致内存不足（out of memory）。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。

链表本身没有大小的限制，天然地支持动态扩容。

链表实现LRU缓存淘汰策略的思路

维护一个有序单链表，越靠近链表尾部的结点是越早被访问过的。当有新的数据被访问时，从链表头开始顺序遍历链表。----缓存访问的时间复杂度为O(n)

过程：

1 . 当访问的数据存储在缓存的链表中时，遍历得到数据对应的结点，将其从原位置删除，再将其插入到链表表头；
2 . 当访问的数据未出现在缓存的链表中时
1）若缓存有空闲，将该数据直接插入到链表表头。
2）若缓存被占满，则将链表尾部的数据删除，再将新数据插入到链表表头。

优化：使用散列表，记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。

思考

如何用数组实现LRU缓存淘汰策略？

方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时
1）缓存有空闲，将数据插入数组第一个元素位置，数组所有元素需要向后移动1个位置，新数据插入数组第一个元素位置，时间复杂度为O(n)；
2）缓存无空闲，清理数组末尾位置的元素，数组所有元素需要向后移动1个位置，新数据插入数组第一个元素位置，时间复杂度为O(n)；
当访问的数据存在于缓存的数组中时，查找到数据，将其从原位置删除，并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。

方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时
1）缓存有空闲，直接将数据添加进数组作为当前最后一个元素，时间复杂度为O(1)；
2）缓存无空闲，清理数组首位置的元素，数组所有元素向前移动1个位置， 将新元素插入数组，时间复杂度为O(n)；
当访问的数据存在于缓存的数组中时，查找到数据，将其从原位置删除，并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。

优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。

如何通过单链表实现“判断某个字符串是否为回文字符串”？

比如 “123454321”
1 . 前提：字符串以单个字符的形式存储在单链表中。
2 . 遍历链表，判断字符个数是否为奇数，若为偶数，则不是。
3 . 将链表中的字符倒序存储一份在另一个链表中。
4 . 同步遍历2个链表，比较对应的字符是否相等，若相等，则是回文字符串，否则，不是。

大概就那么多吧

讲…讲完了？？？？代码呢

不…不会写啊，是的讲了那么多然而并没有会，代码该不会还是不会

是的没错要用指针那就不会了呢，一点都不会了呢，没商量呢，不会就是不会呢

但是一点点还是可以的

就我会的稍微说一下，是的这就是我全部是知识储备了

理解指针或引用的含义

有些语言有指针概念，比如C语言；有些语言没有指针，取而代之的是引用，比如Java、Python。不管“指针”还是“引用”，都是一个意思，指存储所指对象的内存地址。

指针含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）

示例：

p—>next = q; 

表示p节点的后继next指针存储了q节点的内存地址

p—>next = p—>next—>next;

表示p节点的后继next指针存储了p节点的下下个节点的内存地址。

警惕指针丢失和内存泄漏

示例：

单链表的插入，希望在节点a和相邻节点b之间插入节点x，假设当前指针p指向节点a，则造成指针丢失和内存泄漏的代码：

p->next = x;
x->next = p->next

导致将x自身赋值给了x->next，自己指向自己。

对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。

所以，插入结点时，一定要注意操作的顺序。上面代码的正确写法是：两句代码顺序调换。
同理，删除链表时，也一定要手动释放内存空间，否则，也会出现内存泄漏问题。

Python语言不需手动释放，它的解释器的存储管理系统会自动回收不用的存储。

利用哨兵（头结点）简化实现难度

哨兵含义：

链表中的哨兵节点是解决边界问题的，不参与业务逻辑。如果我们引入哨兵节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有哨兵节点的链表就称为不带头链表。

示例：

不带头结点时：

• 对于单链表的插入操作

1 . 如果在p节点后插入一个新节点，只需2行代码即可搞定：

new_node—>next = p—>next;
p—>next = new_node;

2 . 如果向空链表中插入一个新结点，则代码就不同：

if(head == null){
  head = new_node;
}

• 对于单链表的删除操作

1 . 如果要删除节点p的后继节点，只需1行代码即可搞定：

p—>next = p—>next—>next;

2 . 如果删除的是链表的最后一个节点（链表中只剩下这个节点），则代码如下：

if(head—>next == null){
  head = null;
}

以上示例可以看出，不带头结点时，单链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点作特殊处理。

带头结点时：

哨兵节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。
这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的实现逻辑。

留意边界条件处理

常用的检查链表代码是否正确的边界条件：
1 . 如果链表为空时，代码是否能正常工作？
2 . 如果链表只包含一个节点时，代码是否能正常工作？
3 . 如果链表只包含两个节点时，代码是否能正常工作？
4 . 代码逻辑在处理头尾节点时是否能正常工作？

没了