数据结构和算法：数组和链表

数组

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

数组元素被存储在连续的内存空间中，给定数组内存地址（首元素内存地址）和某个元素的索引，可以计算得到该元素的内存地址，从而直接访问该元素。

索引本质上是内存地址的偏移量。首个元素的地址偏移量是 0 ，因此它的索引为 0 是合理的。

插入元素： 数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。

由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。

删除元素： 若想删除索引处的元素，则需要把索引之后的元素都向前移动一位。

总的来看，数组的插入与删除操作有以下缺点：
1.时间复杂度高：数组的插入和删除的平均时间复杂度均为 () ，其中为数组长度。
2.丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
3.内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。

数组的优点与局限性

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。
1.空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
2.支持随机访问：数组允许在 (1) 时间内访问任何元素。
3.缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储存在以下局限性：
1.插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
2.长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
3.空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

数组典型应用

随机访问： 随机抽取一些样本，可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
排序和搜索： 数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
查找表： 当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。
数据结构实现： 数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

链表

链表 （linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

链表的组成单位是节点 node对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。
链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。

链表常用操作

1.初始化链表

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

/* 初始化链表 */// 初始化各个节点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 。

2.插入节点

在链表中插入节点非常容易。假设在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为 (1) 。
相比之下，在数组中插入元素的时间复杂度为 () ，在大数据量下的效率较低。

/* 在链表的节点 n0 之后插入节点 P */void insert(ListNode *n0, ListNode *P) {ListNode *n1 = n0->next;P->next = n1;n0->next = P;}

3.删除节点

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

void remove(ListNode *n0) {if (n0->next == nullptr)return;// n0 -> P -> n1ListNode *P = n0->next;ListNode *n1 = P->next;n0->next = n1;// 释放内存delete P;}

4.访问节点

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

/* 访问链表中索引为 index 的节点 */ListNode *access(ListNode *head, int index) {for (int i = 0; i < index; i++) {if (head == nullptr)return nullptr;head = head->next;}return head;}

5.查找节点

遍历链表，查找其中值为 target 的节点，输出该节点在链表中的索引。此过程也属于线性查找。

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

数组 vs. 链表

常见链表类型

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

链表典型应用

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

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

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

列表

列表（list）表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题，可以基于链表或数组实现。

链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。
数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。

动态数组 （dynamic array）来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。

列表常用操作

1.初始化列表

“无初始值”和“有初始值”两种初始化方法：

/* 初始化列表 */// 无初始值vector<int> nums1;// 有初始值vector<int> nums = { 1, 3, 2, 5, 4 };

2.访问元素

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

/* 访问元素 */int num = nums[1]; // 访问索引 1 处的元素/* 更新元素 */nums[1] = 0; // 将索引 1 处的元素更新为 0

3.插入与删除元素

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

/* 清空列表 */nums.clear();/* 在尾部添加元素 */nums.push_back(1);nums.push_back(3);nums.push_back(2);nums.push_back(5);nums.push_back(4);/* 在中间插入元素 */nums.insert(nums.begin() + 3, 6); // 在索引 3 处插入数字 6/* 删除元素 */nums.erase(nums.begin() + 3); // 删除索引 3 处的元素

4.遍历列表

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

/* 通过索引遍历列表 */int count = 0;for (int i = 0; i < nums.size(); i++){count += nums[i];}/* 直接遍历列表元素 */count = 0;for (int x : nums){count += x;}

5.拼接列表

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

// === File: list.cpp ===/* 拼接两个列表 */vector<int> nums1 = { 6, 8, 7, 10, 9 };// 将列表 nums1 拼接到 nums 之后nums.insert(nums.end(), nums1.begin(), nums1.end());

6.排序列表

/* 排序列表 */sort(nums.begin(), nums.end()); // 排序后，列表元素从小到大排列

列表实现

包括以下三个重点设计：
1.初始容量： 选取一个合理的数组初始容量。
2.数量记录： 声明一个变量 size ，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。
3.扩容机制： 若插入元素时列表容量已满，则需要进行扩容。先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。

lass MyList{private:int *arr; // 数组（存储列表元素）int arrCapacity = 10; // 列表容量int arrSize = 0;// 列表长度（当前元素数量）int extendRatio = 2;// 每次列表扩容的倍数public:/* 构造方法 */MyList(){arr = new int[arrCapacity];}/* 析构方法 */~MyList(){delete[] arr;}/* 获取列表长度（当前元素数量）*/int size(){return arrSize;}/* 获取列表容量 */int capacity(){return arrCapacity;}/* 访问元素 */int get(int index){// 索引如果越界，则抛出异常，下同if (index < 0 || index >= size())throw out_of_range("索引越界");return arr[index];}/* 更新元素 */void set(int index, int num){if (index < 0 || index >= size())throw out_of_range("索引越界");arr[index] = num;}/* 在尾部添加元素 */void add(int num){// 元素数量超出容量时，触发扩容机制if (size() == capacity())extendCapacity();arr[size()] = num;// 更新元素数量arrSize++;}/* 在中间插入元素 */void insert(int index, int num){if (index < 0 || index >= size())throw out_of_range("索引越界");// 元素数量超出容量时，触发扩容机制if (size() == capacity())extendCapacity();// 将索引 index 以及之后的元素都向后移动一位for (int j = size() - 1; j >= index; j--){arr[j + 1] = arr[j];}arr[index] = num;// 更新元素数量arrSize++;}/* 删除元素 */int remove(int index){if (index < 0 || index >= size())throw out_of_range("索引越界");int num = arr[index];// 将索引 index 之后的元素都向前移动一位for (int j = index; j < size() - 1; j++){arr[j] = arr[j + 1];}// 更新元素数量arrSize--;// 返回被删除的元素return num;}/* 列表扩容 */void extendCapacity(){// 新建一个长度为原数组 extendRatio 倍的新数组int newCapacity = capacity() * extendRatio;int *tmp = arr;arr = new int[newCapacity];// 将原数组中的所有元素复制到新数组for (int i = 0; i < size(); i++){arr[i] = tmp[i];}// 释放内存delete[] tmp;arrCapacity = newCapacity;}/* 将列表转换为 Vector 用于打印 */vector<int> toVector(){// 仅转换有效长度范围内的列表元素vector<int> vec(size());for (int i = 0; i < size(); i++){vec[i] = arr[i];}return vec;}};/* Driver Code */int main(){/* 初始化列表 */MyList *nums = new MyList();/* 在尾部添加元素 */nums->add(1);nums->add(3);nums->add(2);nums->add(5);nums->add(4);cout << "列表 nums = ";vector<int> vec = nums->toVector();printVector(vec);cout << "容量 = " << nums->capacity() << " ，长度 = " << nums->size() << endl;/* 在中间插入元素 */nums->insert(3, 6);cout << "在索引 3 处插入数字 6 ，得到 nums = ";vec = nums->toVector();printVector(vec);/* 删除元素 */nums->remove(3);cout << "删除索引 3 处的元素，得到 nums = ";vec = nums->toVector();printVector(vec);/* 访问元素 */int num = nums->get(1);cout << "访问索引 1 处的元素，得到 num = " << num << endl;/* 更新元素 */nums->set(1, 0);cout << "将索引 1 处的元素更新为 0 ，得到 nums = ";vec = nums->toVector();printVector(vec);/* 测试扩容机制 */for (int i = 0; i < 10; i++){// 在 i = 5 时，列表长度将超出列表容量，此时触发扩容机制nums->add(i);}cout << "扩容后的列表 nums = ";vec = nums->toVector();printVector(vec);cout << "容量 = " << nums->capacity() << " ，长度 = " << nums->size() << endl;// 释放内存delete nums;return 0;}

内存与缓存

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

计算机存储设备

硬盘用于长期存储大量数据；
内存用于临时存储程序运行中正在处理的数据；
缓存则用于存储经常访问的数据和指令。

在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少对较慢的内存的依赖。

数据结构的内存效率

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

数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多。
由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中 （cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。

“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好；将 CPU 从缓存中成功获取数据的比例称为缓存命中率 （cache hit rate），这个指标通常用来衡量缓存效率。

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

数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面：
占用空间： 链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
缓存行： 链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
预取机制： 数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
空间局部性： 数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。
总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。

学习地址：https://github.com/krahets/hello-algo
重新复习数据结构，所有的内容都来自这里。