数组和链表

1. 数组

数组(array)是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引(index)。 Alt text

2. 数组常用操作

2.1 初始化数组

我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0：

java

/* 初始化数组 */
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };

2.2 访问元素

数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组内存地址(首元素内存地址)和某个元素的索引，我们可以使用图 4-2 所示的公式计算得到该元素的内存地址，从而直接访问该元素。 Alt text 从地址计算公式的角度看，索引本质上是内存地址的偏移量。首个元素的地址偏移量是0，因此它的索引为0是合理的。在数组中访问元素非常高效，我们可以在O(1)时间内随机访问数组中的任意一个元素。

2.3 插入元素

数组元素在内存中是"紧挨着的"，它们之间没有空间再存放任何数据。如图所示，如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。 Alt text 值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素"丢失"。

2.4 删除元素

同理，如图所示，若想删除索引i处的元素，则需要把索引i之后的元素都向前移动一位。 Alt text 请注意，删除元素完成后，原先末尾的元素变得"无意义"了，所以我们无须特意去修改它。

2.5 遍历数组

在大多数编程语言中，我们既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素

2.6 查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。因为数组是线性数据结构，所以上述查找操作被称为"线性查找"。

2.7 扩容数组

在大多数编程语言中，数组的长度是不可变的。因为在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个O(n)的操作，在数组很大的情况下非常耗时。

2.8 数组的优点与局限性

数组存储在连续的内存空间内，且元素类型相同。有以下这些优点：

空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
支持随机访问：数组允许在O(1)时间内访问任何元素。
缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
连续空间存储是一把双刃剑，其存在以下局限性：
插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

2.9 数组典型应用

随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII码值作为索引，对应的元素存放在数组中的对应位置。
机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

3. 链表

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。链表的灵活性优势体现在内存空间不要求是连续的。
链表(linked list)是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过"引用"相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
Alt text 链表的组成单位是节点(node)对象。每个节点都包含两项数据：节点的"值"和指向下一节点的"引用"。链表的首个节点被称为"头节点"，最后一个节点被称为"尾节点"。链表节点 ListNode除了包含值，还需额外保存一个引用(指针)。因此在相同数据量下，链表比数组占用更多的内存空间。

java

/* 链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

4. 链表常用操作

4.1 初始化链表

建立链表分为两步，第一步是初始化各个节点对象，第二步是构建节点之间的引用关系。初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。

java

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// 构建节点之间的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以上代码中的链表可记作链表n0。

4.2 插入节点

在链表中插入节点非常容易。如图所示，假设我们想在相邻的两个节点n0和n1之间插入一个新节点P ，则只需改变两个节点引用(指针)即可，时间复杂度为O(1)。 Alt text

4.3 删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用(指针)即可。请注意，尽管在删除操作完成后节点P仍然指向n1 ，但实际上遍历此链表已经无法访问到P，这意味着P已经不再属于该链表了。 Alt text

4.4 访问节点

在链表中访问节点的效率较低。链表需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第i个节点需要循环i-1轮，时间复杂度为O(n)。

4.5 查找节点

遍历链表，查找其中值为target的节点，输出该节点在链表中的索引:

java

/* 在链表中查找值为 target 的首个节点 */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

4.6 数组vs链表

由于它们采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点:

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	O(1)	O(n)
添加元素	O(n)	O(1)
删除元素	O(n)	O(1)

4.7 常见链表类型

单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空None。
环形链表：如果我们令单向链表的尾节点指向头节点(首尾相接)，则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点(下一个节点)和前驱节点(上一个节点)的引用(指针)。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

4.8 链表典型应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构:

栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景:

高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU算法：在缓存淘汰(LRU)算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度:

时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的CPU调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

5. 列表

列表(list)是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。
当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据，从而难以选择合适的列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则会造成内存空间浪费。为解决此问题，我们可以使用动态数组(dynamic array)来实现列表。许多编程语言中的标准库提供的列表是基于动态数组实现的，例如Python中的list 、Java中的ArrayList 、C++中的vector和C#中的List等。

6. 列表常用操作

6.1 初始化列表

我们通常使用"无初始值"和"有初始值"这两种初始化方法：

java

/* 初始化列表 */
// 无初始值
List<Integer> nums1 = new ArrayList<>();
// 有初始值(注意数组的元素类型需为 int[] 的包装类 Integer[])
Integer[] numbers = new Integer[] { 1, 3, 2, 5, 4 };
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers));

6.2 访问元素

列表本质上是数组，因此可以在O(1)时间内访问和更新元素，效率很高。

6.3 插入与删除元素

相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为O(1)，但插入和删除元素的效率仍与数组相同，时间复杂度为O(n)。

java

/* 清空列表 */
nums.clear();

/* 在尾部添加元素 */
nums.add(1);
nums.add(3);
nums.add(2);
nums.add(5);
nums.add(4);

/* 在中间插入元素 */
nums.add(3, 6);  // 在索引 3 处插入数字 6

/* 删除元素 */
nums.remove(3);  // 删除索引 3 处的元素

6.4 遍历列表

与数组一样，列表可以根据索引遍历，也可以直接遍历各元素。

6.5 拼接列表

给定一个新列表nums1 ，我们可以将其拼接到原列表的尾部。

6.6 排序列表

完成列表排序后，我们便可以使用在数组类算法题中经常考查的"二分查找"和"双指针"算法。

7. 内存与缓存

实际上，物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。

7.1 计算机存储设备

计算机中包括三种类型的存储设备：硬盘(hard disk)、内存(random-access memory, RAM)、缓存(cache memory)。我们可以将计算机存储系统想象为图所示的金字塔结构。越靠近金字塔顶端的存储设备的速度越快、容量越小、成本越高。 Alt text 总的来说，硬盘用于长期存储大量数据，内存用于临时存储程序运行中正在处理的数据，而缓存则用于存储经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。

7.2 数据结构的内存效率

在内存空间利用方面，数组和链表各自具有优势和局限性。
一方面，内存是有限的，且同一块内存不能被多个程序共享，因此我们希望数据结构能够尽可能高效地利用空间。数组的元素紧密排列，不需要额外的空间来存储链表节点间的引用(指针)，因此空间效率更高。然而，数组需要一次性分配足够的连续内存空间，这可能导致内存浪费，数组扩容也需要额外的时间和空间成本。相比之下，链表以"节点"为单位进行动态内存分配和回收，提供了更大的灵活性。
另一方面，在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。数组由于其连续的存储方式，相对不容易导致内存碎片化。相反，链表的元素是分散存储的，在频繁的插入与删除操作中，更容易导致内存碎片化。

7.3 数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当CPU尝试访问的数据不在缓存中时，就会发生缓存未命中(cache miss)，此时CPU不得不从速度较慢的内存中加载所需数据。显然，"缓存未命中"越少，CPU读写数据的效率就越高，程序性能也就越好。我们将CPU从缓存中成功获取数据的比例称为缓存命中率(cache hit rate)，这个指标通常用来衡量缓存效率。为了尽可能达到更高的效率，缓存会采取以下数据加载机制:

缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
预取机制：处理器会尝试预测数据访问模式(例如顺序访问、固定步长跳跃访问等)，并根据特定模式将数据加载至缓存之中，从而提升命中率。
空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。

总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。这使得在解决算法问题时，基于数组实现的数据结构往往更受欢迎。

数组和链表 ​

1. 数组 ​

2. 数组常用操作 ​

2.1 初始化数组 ​

2.2 访问元素 ​

2.3 插入元素 ​

2.4 删除元素 ​

2.5 遍历数组 ​

2.6 查找元素 ​

2.7 扩容数组 ​

2.8 数组的优点与局限性 ​

2.9 数组典型应用 ​

3. 链表 ​

4. 链表常用操作 ​

4.1 初始化链表 ​

4.2 插入节点 ​

4.3 删除节点 ​

4.4 访问节点 ​

4.5 查找节点 ​

4.6 数组vs链表 ​

4.7 常见链表类型 ​

4.8 链表典型应用 ​

5. 列表 ​

6. 列表常用操作 ​

6.1 初始化列表 ​

6.2 访问元素 ​

6.3 插入与删除元素 ​

6.4 遍历列表 ​

6.5 拼接列表 ​

6.6 排序列表 ​

7. 内存与缓存 ​

7.1 计算机存储设备 ​

7.2 数据结构的内存效率 ​

7.3 数据结构的缓存效率 ​

数组和链表

1. 数组

2. 数组常用操作

2.1 初始化数组

2.2 访问元素

2.3 插入元素

2.4 删除元素

2.5 遍历数组

2.6 查找元素

2.7 扩容数组

2.8 数组的优点与局限性

2.9 数组典型应用

3. 链表

4. 链表常用操作

4.1 初始化链表

4.2 插入节点

4.3 删除节点

4.4 访问节点

4.5 查找节点

4.6 数组vs链表

4.7 常见链表类型

4.8 链表典型应用

5. 列表

6. 列表常用操作

6.1 初始化列表

6.2 访问元素

6.3 插入与删除元素

6.4 遍历列表

6.5 拼接列表

6.6 排序列表

7. 内存与缓存

7.1 计算机存储设备

7.2 数据结构的内存效率

7.3 数据结构的缓存效率