算法笔记02-数组和链表

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

数组、链表、队列、栈等都是线性表结构。

与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性 表中，数据之间并不是简单的前后关系。

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

1.线性表

线性表就是数据排成像一条线一样的结构。

常见的线性表结构：数组，链表、队列、栈等。

2. 连续的内存空间和相同类型的数据

优点：两限制使得具有随机访问的特性

缺点：删除，插入数据效率低（为何数组插入和删除低效？）

【插入】

若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。最好情况时间复杂度 O(1)，最坏情况复杂度为O(n)，平均复杂度为O(n)。如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到最后，然后将插入的数据直接放在第k个位置上。这样时间复杂度就将为 O（1）了。

【删除】

与插入类似，为了保持内存的连续性。

最好情况时间复杂度 O(1)，最坏情况复杂度为O(n)，平均复杂度为O(n)。

提高效率：将多次删除操作中集中在一起执行，可以先记录已经删除的数据，但是不进行数据迁移，而仅仅是记录，当发现没有更多空间存储时，再执行真正的删除操作。这也是 JVM标记清除垃圾回收算法的核心思想。

 

用数组还是容器？

数组先指定了空间大小，容器如ArrayList可以动态扩容。

1.希望存储基本类型数据，可以用数组

2.事先知道数据大小，并且操作简单，可以用数组

3.直观表示多维，可以用数组

4.业务开发，使用容器足够，开发框架，追求性能，首先数组。

 

为什么数组要从 0 开始编号？

由于数组是通过寻址公式，计算出该元素存储的内存地址：a[i]_address = base_address + i * data_type_size

如果数组是从 1 开始计数，那么就会变成：a[i]_address = base_address + （i-1）* data_type_size

对于CPU来说，多了一次减法的指令。当然，还有一定的历史原因。

 

缓存

缓存 是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。

常见的缓存策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

 

缓存实际上就是利用了空间换时间的设计思想。

对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；

而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

 

如何用链表来实现 LRU 缓存淘汰策略呢？

三种最常见的链表结构，它们分别是：单链表、双向链表、循环链表、双向循环链表。

1.单链表

（1）每个节点只包含一个指针，即后继指针。

（2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。

（3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

2.循环链表

（1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。

（2）适用于存储有循环特点的数据，比如约瑟夫问题。

3.双向链表

（1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。

（2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。

与数组一样，链表也支持数据的查找、插入和删除操作。

数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。

 

选择数组还是链表？

1.插入、删除和随机访问的时间复杂度

数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。

链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点

（1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。

（2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

3.链表缺点

（1）内存空间消耗更大，因为需要额外的空间存储指针信息。

（2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

4.如何选择？

数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。如果代码对内存的使用非常苛刻，那数组就更适合。

 

1.对于指针（或者引用）的理解：

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

2.我们插入结点时，一定要注意操作的顺序；删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。

3. 利用哨兵简化难度

链表的插入、删除操作，需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断，链表的哨兵对象是只存指针不存数据的头结点。

4. 重点留意边界条件处理

操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想，能在其它的编码中也养成考虑边界的习惯。

 

经常用来检查链表代码是否正确的边界条件有这样几个：

如果链表为空时，代码是否能正常工作？

如果链表只包含一个结点时，代码是否能正常工作？

如果链表只包含两个结点时，代码是否能正常工作？

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

 

经典链表操作案例：

• 单链表反转

• 链表中环的检测

• 两个有序的链表合并

• 删除链表倒数第 n 个结点

• 求链表的中间结点