数组与链表
数组与链表
数据结构的世界如同一堵厚实的砖墙。数组的砖块整齐排列，逐个紧贴。链表的砖块分散各处，连接的藤曼自由地穿梭于砖缝之间。
数组
数组是一种线性数据结构，其将相同类型的元素存储于连续的内存空间中，它的位置被称为索引。
数组的常用操作
1.初始化数组
数组的两种初始化方法：无初始值、给定初始值
/* 初始化数组 */
let arr = new Array(5).fill(0); // [0, 0, 0, 0, 0]
let nums = [1, 3, 2, 5, 4];
let strs = [];
2.访问数组
数组元素被存储在连续的内存空间中，意味着计算数组元素的内存地址非常容易。给定数组内存地址(首元素内存地址)和某个元素的指引，依据公式：元素内存地址 = 数组内存地址 + 元素长度 x 元素索引来获取元素的内存地址，从而直接访问该元素。
索引本质上是内存地址的偏移量。
3.插入元素
数组中元素是紧挨着的，相邻元素之间没有空间插入其他元素。要想插入元素，则需要将要插入位置之后的所有元素向后移动一位，再将该值赋值给该索引。
// 数组插入
function arrInsert(arr = [], index, value) {
console.log(arr, index, value);
console.log(arr.length - 1);
// 从末尾开始
for (let i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = value;
console.log(arr); // 12345
}
arrInsert([1, 3, 4, 5, 6], 1, 2);
问题：数组长度是固定的，插入一个元素必定会导致数组尾部元素丢失！后续章节进行解答
4.删除元素
删除元素，也需要将该索引之后的元素向前移动一位。
// 删除元素
function arrDelete(arr = [], index) {
for (let i = index; i < arr.length - 1; i++) {
arr[i] = arr[i + 1];
}
console.log(arr);
}
arrDelete([1, 2, 3, 4, 5, 6], 2); // [ 1, 2, 4, 5, 6, 6 ]，末尾值变无意义，一般不需要进行处理
总的来说，数组的插入与删除操作有以下缺点：
- 时间复杂度高：数组的插入与删除均需要移动与索引位置有关的元素，平均时间复杂度为O(n),n为数组长度。
- 丢失元素：由于数组长度不可变，插入元素后，超出部分会丢失。
- 内存浪费：我们可以初始化一个很大的数组，只使用其中一部分，插入数据时就不会存在丢失情况。但是这样会很浪费内存空间。
5.遍历数组
可以使用索引遍历数组，也可通过索引直接获取每个元素。
6.查找元素
在数组中查找元素需要遍历数组，每轮进行判断元素值是否匹配，若匹配则输入对应索引。由于数组是线性数据结构，因此被称为“线性查找”。
7. 扩容数组
在复杂的系统环境中，很难保证元素之后的空间是可用的，因此无法安全的扩展数组容量，因此在大多数编程语言中，数组长度不可变，但是JS可变。
数组的优点与局限性
数组存储在连续的内存空间中，具有以下有点：
- 空间效率高：数组为数据分配了连续的内存块，无需额外的结构开销。
- 支持随机访问：数组允许在O(1)时间内访问元素。
- 缓存局部性：当访问数组元素时，不光会加载该元素，还会加载周围的其他元素，从而借助高速缓存提升后续的执行速度。
局限性如下：
- 插入和删除效率低下，数组中元素过多时，插入和删除需要移动大量的元素。
- 长度不可变：数组在初始化后长度就固定了，扩容需要将旧数组复制到新数组中，开销很大。
- 空间浪费：如果数组分配的空间大小超出实际所需，则多余的空间被浪费了。
数组的典型应用
数组是一种基础且常见的数据结构，既频繁应用在各类算法中，也可实现各种复杂的数据结构。
- 随机访问：若想随机抽取一些样本，那么可以使用数组进行存储，并生成一个随机数列，然后根据索引访问数组中的元素。
- 排序和搜索：数组是排序和搜索算法常用的数据机构。快速排序、归并排序、二分查找等都在数组中进行。
- 查找表：需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。
- 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，都是基于数组实现的。
- 数据结构实现：数组可以实现用于实现栈、队列、哈希表、堆、图等数据结构。例如图的相邻矩阵就是一个二维数组。
链表
内存空间是所有程序的公共资源，在一个复杂的系统运行环境中，空闲的内存空间可能散布于内存各处。但是数组的存储必须是连续的内存空间，当数组很大时，内存可能无法提供如此大的连续空间。
链表是一种数据结构，其中每个元素都是一个节点对象，各个节点通过引用相连接，引用记录了下一个节点的内存地址，通过它可以从当前节点访问下一节点。链表的存储可以是分散的内存空间，无需连续。
链表的每个节点都包含两项数据：节点的值、指向下一节点的引用(记录的下一节点内存地址)。链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”，尾节点的引用为None。相对于数组而言，链表还需存储一个引用指针，因此需要更多的内存空间。
链表的常用操作
1.初始化链表
建立链表分为两步，第一步初始化各个节点对象，第二部构建各个节点之间的引用关系。初始化完成后，可以从链表的头节点触发，通过引用指向，依次访问各个子节点。
2.插入节点
链表的插入相对于数组简单，假设在n0和n1之间插入新节点p，只需要改写n0和n1的指针引用即可，时间复杂度为O(1)。
3.删除节点
链表的删除节点只需要改变一个节点的引用即可
/* 基于环形数组实现的双向队列 */
class ArrayDeque {
#nums;
// 用于存储双向队列元素的数组
#front; // 队首指针，指向队首元素
#queSize; // 双向队列长度
/* 构造方法 */
constructor(capacity) {
this.#nums = new Array(capacity);
this.#front = 0;
this.#queSize = 0;
}
/* 获取双向队列的容量 */ capacity() {
return this.#nums.length;
}
/* 获取双向队列的长度 */ size() {
return this.#queSize;
}
/* 判断双向队列是否为空 */ isEmpty() {
return this.#queSize === 0;
}
/* 计算环形数组索引 */
index(i) {
// 通过取余操作实现数组首尾相连
// 当 i 越过数组尾部后，回到头部
// 当 i 越过数组头部后，回到尾部
return (i + this.capacity()) % this.capacity();
}
/* 队首入队 */
pushFirst(num) {
if (this.#queSize === this.capacity()) {
console.log("双向队列已满");
return;
}
// 队首指针向左移动一位
// 通过取余操作实现 front 越过数组头部后回到尾部
this.#front = this.index(this.#front - 1);
// 将 num 添加至队首
this.#nums[this.#front] = num;
this.#queSize++;
}
/* 队尾入队 */
pushLast(num) {
if (this.#queSize === this.capacity()) {
console.log("双向队列已满");
return;
}
// 计算队尾指针，指向队尾索引 + 1
const rear = this.index(this.#front + this.#queSize);
// 将 num 添加至队尾
this.#nums[rear] = num;
this.#queSize++;
}
/* 队首出队 */
popFirst() {
const num = this.peekFirst();
// 队首指针向后移动一位
this.#front = this.index(this.#front + 1);
this.#queSize--;
return num;
}
/* 队尾出队 */
popLast() {
const num = this.peekLast();
this.#queSize--;
return num;
}
/* 访问队首元素 */
peekFirst() {
if (this.isEmpty()) throw new Error("The Deque Is Empty.");
return this.#nums[this.#front];
}
/* 访问队尾元素 */
peekLast() {
if (this.isEmpty()) throw new Error("The Deque Is Empty.");
// 计算尾元素索引
const last = this.index(this.#front + this.#queSize - 1);
return this.#nums[last];
}
/* 返回数组用于打印 */
toArray() {
// 仅转换有效长度范围内的列表元素
const res = [];
for (let i = 0, j = this.#front; i < this.#queSize; i++, j++) {
res[i] = this.#nums[this.index(j)];
}
return res;
}
}
4.访问节点
链表节点的访问效率是很低的，因为链表是分散存储的，想访问某个指定节点，需要从头节点触发，直到找到目标节点为止，时间复杂度为O(n)。
5.查找节点
遍历链表，查找其中值为target的节点，输出该节点的索引。也属于线性查找，时间复杂度为O(n)。
常见链表类型
常见的链表包含三种：
- 单向链表：每个节点包含值和执行下一节点的引用数据。将首个节点称为头节点，最后一个节点称为尾节点，尾节点指向空None。
- 环形链表：将单向链表的尾节点引用指向头节点，会得到一个环形链表，在环形链表中任意一个节点都可被视作头节点。
- 双向链表：双向链表的节点相对于单向链表而言，多记录了一个头引用，存储了前驱节点的引用。较单向链表而言更为灵活，可以朝两个方向遍历链表，但是也占用更多内存空间。
链表的典型应用
单向链表常用于实现栈、队列、哈希表和图等数据结构。
- 栈与队列：当插入和删除都在链表一端进行时，表现出先进后出特性，对应栈。当插入在链表一端进行时，删除在链表另外一端时，表现出先进先出特性，对应队列。
- 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
- 图：领接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每一个元素都代表与该顶点相连的其他顶点。
双向链表常用于快速查找前一个和后一个元素的场景。
- 高级数据结构：例如红黑树、b树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表中的头引用。
- 浏览器历史：在网页浏览器中，用户点击前进或后退时，浏览器需要直到用户访问过的前一个和后一个网页，也类似于双向链表。
- LRU算法：缓存淘汰算法LRU，我们需要快速找到最佳使用最少的数据，以及支持快速添加和删除节点。
环形链表常用于需要周期性操作的场景中，例如系统的资源调度。
- 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的CPU调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU将切换到下一个进程。
- 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表中，用于实现无缝播放。
列表
列表是一种抽象的数据结构，表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无需考虑数组容量限制的问题。链表可以基于链表和数组实现。
- 链表天然可以看作一个列表，其支持元素增删改查操作，并且可以灵活动态扩容。
- 数组也支持元素增删改查，由于长度不可变，因此只能看作具有长度限制的列表。
当使用数组实现列表时，长度不可变的性质将会导致列表的实用性降低。
常用操作
1.初始化列表
通常使用“无初始值”和“有初始值”
// 无初始值
const nums1 = [];
// 有初始值
const nums = [1, 3, 2, 5, 4];
2.访问元素
列表本质上是数组，因此可以在O(1)时间内访问和更新元素，效率很高。
/* 访问元素 */
const num = nums[1]; // 访问索引 1 处的元素
/* 更新元素 */
nums[1] = 0; // 将索引 1 处的元素更新为 0
3.插入与删除元素
相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为O(1)，但插入和删除元素的效率仍与数组相同，时间复杂度为O(n)。
/* 清空列表 */
nums.length = 0;
/* 在尾部添加元素 */
nums.push(1);
nums.push(3);
nums.push(2);
nums.push(5);
nums.push(4);
/* 在中间插入元素 */
nums.splice(3, 0, 6); // 在索引 3 处插入数字 6
/* 删除元素 */
nums.splice(3, 1); // 删除索引 3 处的元素
4.遍历列表
与数组一样，列表可以根据索引遍历，也可以直接遍历各元素。
5.拼接列表
/* 拼接两个列表 */
const nums1 = [6, 8, 7, 10, 9];
nums.push(...nums1); // 将列表 nums1 拼接到 nums 之后
6.排序列表
/* 排序列表 */
nums.sort((a, b) => a - b); // 排序后，列表元素从小到大排列
列表的实现
实现一个列表，重点为以下三个方面：
- 初始容量：选取一个合理的数组初始容量。
- 数量记录：声明一个变量size，用于记录列表当前元素数量，并随着元素插入和删除实时更新，依据此变量，可以定位列表尾部，以及判断是否需要扩容。
- 扩容机制：若当前列表已满，需要先依据扩容倍数创建一个更大的数组，再将当前数组所有元素移动至新数组中。
// 实现列表
class MyList {
arr = new Array();
capacity = 10; // 数组容量
size = 0; // 数组长度
extendRatio = 2; // 扩容倍数
constructor() {
this.arr = new Array(this.capacity);
}
// 获取列表size
getSize() {
return this.size;
}
// 获取容量
getCapacity() {
return this.capacity;
}
// 访问元素
get(index) {
if (index < 0 || index >= this.size) {
throw new Error("索引越界");
}
return this.arr[index];
}
/* 更新元素 */
set(index, num) {
if (index < 0 || index >= this.size) throw new Error("索引越界");
this.arr[index] = num;
}
/* 在尾部添加元素 */
add(num) {
// 如果长度等于容量，则需要扩容
if (this.size === this.capacity) {
this.extendCapacity();
}
// 将新元素添加到列表尾部
this.arr[this.size] = num;
this.size++;
}
/* 在中间插入元素 */
insert(index, num) {
if (index < 0 || index >= this.size) throw new Error("索引越界");
// 元素数量超出容量时，触发扩容机制
if (this.size === this.capacity) {
this.extendCapacity();
}
// 将索引 index 以及之后的元素都向后移动一位
for (let j = this.size - 1; j >= index; j--) {
this.arr[j + 1] = this.arr[j];
}
// 更新元素数量
this.arr[index] = num;
this.size++;
}
/* 删除元素 */
remove(index) {
if (index < 0 || index >= this.size) throw new Error("索引越界");
let num = this.arr[index];
// 将将索引 index 之后的元素都向前移动一位
for (let j = index; j < this.size - 1; j++) {
this.arr[j] = this.arr[j + 1];
}
// 更新元素数量
this.size--;
// 返回被删除的元素
return num;
}
/* 列表扩容 */
extendCapacity() {
// 新建一个长度为原数组 extendRatio 倍的新数组，并将原数组复制到新数组
this.arr = this.arr.concat(
new Array(this.capacity() * (this.extendRatio - 1))
);
// 更新列表容量
this.capacity = this.arr.length;
}
/* 将列表转换为数组 */
toArray() {
let size = this.size();
// 仅转换有效长度范围内的列表元素
const arr = new Array(size);
for (let i = 0; i < size; i++) {
arr[i] = this.get(i);
}
return arr;
}
}
内存与缓存
数组与链表，在物理结构上的差异在于数组是连续存储的，而链表是不连续的。物理结构的差异很大程度上决定了程序对内存和缓存的使用效率，进而影响算法的整体性能。
计算机存储设备
计算机中包含了三种存储设备：硬盘(hard disk)、内存(radon-access memory)、缓存(cache memory)
硬盘：适合长期存储，包括操作系统、程序、文件等，断电后不会丢失，且存储容量较大，TB级别，但是读取速度较慢。 内存：临时存储当前运行的程序和正在处理的数据，断电后数据会丢失，容量较小，GB级别。读取速度较快。 缓存：存储经常访问的数据和指令，减少CPU访问内存的次数，断电后数据丢失，容量非常小，MB级别，读取速度非常快。
总的来说，硬盘用于长期存储大量数据，内存用于临时存储程序运行中正在处理的数据，而缓存则用于存储经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。
数据结构的内存效率
一方面，内存是有限的，且同一块内存不能被多个程序共享，因此我们希望数据结构能够尽可能高效地利用空间。数组的元素紧密排列，不需要额外的空间来存储链表节点间的引用（指针），因此空间效率更高。然而，数组需要一次性分配足够的连续内存空间，这可能导致内存浪费，数组扩容也需要额外的时间和空间成本。相比之下，链表以“节点”为单位进行动态内存分配和回收，提供了更大的灵活性。
另一方面，在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。数组由于其连续的存储方式，相对不容易导致内存碎片化。相反，链表的元素是分散存储的，在频繁的插入与删除操作中，更容易导致内存碎片化。