数据结构: 数组与链表

目录

1   数组

1.1   数组常用操作

1.   初始化数组

2.   访问元素

3.   插入元素

4.   删除元素

5.   遍历数组

6.   查找元素

7.   扩容数组

1.2   数组优点与局限性

1.3   数组典型应用

2   链表

2.1   链表常用操作

1.   初始化链表

2.   插入节点

3.   删除节点

4.   访问节点

5.   查找节点

2.2   数组 VS 链表

2.3   常见链表类型

2.4   链表典型应用

3   列表

3.1   列表常用操作

1.   初始化列表

2.   访问元素

3.   插入与删除元素

4.   遍历列表

5.   拼接列表

6.   排序列表

3.2   列表实现

4   小结

1.   重点回顾

2.   Q & A


1   数组

「数组 array」是一种线性数据结构,其将相同类型元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的「索引 index」。图 4-1 展示了数组的主要术语和概念。

数组定义与存储方式

图 4-1   数组定义与存储方式

1.1   数组常用操作

1.   初始化数组

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

int arr[5] = { 0 }; // { 0, 0, 0, 0, 0 }
int nums[5] = { 1, 3, 2, 5, 4 };

2.   访问元素

数组元素被存储在连续的内存空间中,这意味着计算数组元素的内存地址非常容易。给定数组内存地址(即首元素内存地址)和某个元素的索引,我们可以使用图 4-2 所示的公式计算得到该元素的内存地址,从而直接访问此元素。

数组元素的内存地址计算

图 4-2   数组元素的内存地址计算

观察图 4-2 ,我们发现数组首个元素的索引为 0 ,这似乎有些反直觉,因为从 1 开始计数会更自然。但从地址计算公式的角度看,索引的含义本质上是内存地址的偏移量。首个元素的地址偏移量是 0 ,因此它的索引为 0 也是合理的。

在数组中访问元素是非常高效的,我们可以在 O(1)内随机访问数组中的任意一个元素。

/* 随机访问元素 */
int randomAccess(int *nums, int size) {// 在区间 [0, size) 中随机抽取一个数字int randomIndex = rand() % size;// 获取并返回随机元素int randomNum = nums[randomIndex];return randomNum;
}

3.   插入元素

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

数组插入元素示例

图 4-3   数组插入元素示例

值得注意的是,由于数组的长度是固定的,因此插入一个元素必定会导致数组尾部元素的“丢失”。我们将这个问题的解决方案留在列表章节中讨论。

/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {// 把索引 index 以及之后的所有元素向后移动一位for (int i = size - 1; i > index; i--) {nums[i] = nums[i - 1];}// 将 num 赋给 index 处元素nums[index] = num;
}

4.   删除元素

同理,如图 4-4 所示,若想要删除索引 i 处的元素,则需要把索引 i 之后的元素都向前移动一位。

数组删除元素示例

图 4-4   数组删除元素示例

请注意,删除元素完成后,原先末尾的元素变得“无意义”了,所以我们无须特意去修改它。

/* 删除索引 index 处元素 */
// 注意:stdio.h 占用了 remove 关键词
void removeItem(int *nums, int size, int index) {// 把索引 index 之后的所有元素向前移动一位for (int i = index; i < size - 1; i++) {nums[i] = nums[i + 1];}
}

总的来看,数组的插入与删除操作有以下缺点。

  • 时间复杂度高:数组的插入和删除的平均时间复杂度均为 O(n) ,其中 n 为数组长度。
  • 丢失元素:由于数组的长度不可变,因此在插入元素后,超出数组长度范围的元素会丢失。
  • 内存浪费:我们可以初始化一个比较长的数组,只用前面一部分,这样在插入数据时,丢失的末尾元素都是“无意义”的,但这样做也会造成部分内存空间的浪费。

5.   遍历数组

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

/* 遍历数组 */
void traverse(int *nums, int size) {int count = 0;// 通过索引遍历数组for (int i = 0; i < size; i++) {count++;}
}

6.   查找元素

在数组中查找指定元素需要遍历数组,每轮判断元素值是否匹配,若匹配则输出对应索引。

因为数组是线性数据结构,所以上述查找操作被称为“线性查找”。

/* 在数组中查找指定元素 */
int find(int *nums, int size, int target) {for (int i = 0; i < size; i++) {if (nums[i] == target)return i;}return -1;
}

7.   扩容数组

在复杂的系统环境中,程序难以保证数组之后的内存空间是可用的,从而无法安全地扩展数组容量。因此在大多数编程语言中,数组的长度是不可变的

如果我们希望扩容数组,则需重新建立一个更大的数组,然后把原数组元素依次拷贝到新数组。这是一个 O(n) 的操作,在数组很大的情况下是非常耗时的。

/* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {// 初始化一个扩展长度后的数组int *res = (int *)malloc(sizeof(int) * (size + enlarge));// 将原数组中的所有元素复制到新数组for (int i = 0; i < size; i++) {res[i] = nums[i];}// 初始化扩展后的空间for (int i = size; i < size + enlarge; i++) {res[i] = 0;}// 返回扩展后的新数组return res;
}

1.2   数组优点与局限性

数组存储在连续的内存空间内,且元素类型相同。这种做法包含丰富的先验信息,系统可以利用这些信息来优化数据结构的操作效率。

  • 空间效率高: 数组为数据分配了连续的内存块,无须额外的结构开销。
  • 支持随机访问: 数组允许在 O(1) 时间内访问任何元素。
  • 缓存局部性: 当访问数组元素时,计算机不仅会加载它,还会缓存其周围的其他数据,从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑,其存在以下缺点。

  • 插入与删除效率低:当数组中元素较多时,插入与删除操作需要移动大量的元素。
  • 长度不可变: 数组在初始化后长度就固定了,扩容数组需要将所有数据复制到新数组,开销很大。
  • 空间浪费: 如果数组分配的大小超过了实际所需,那么多余的空间就被浪费了。

1.3   数组典型应用

数组是一种基础且常见的数据结构,既频繁应用在各类算法之中,也可用于实现各种复杂数据结构。

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

2   链表

内存空间是所有程序的公共资源,在一个复杂的系统运行环境下,空闲的内存空间可能散落在内存各处。我们知道,存储数组的内存空间必须是连续的,而当数组非常大时,内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

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

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

链表定义与存储方式

图 4-5   链表定义与存储方式

观察图 4-5 ,链表的组成单位是「节点 node」对象。每个节点都包含两项数据:节点的“值”和指向下一节点的“引用”。

  • 链表的首个节点被称为“头节点”,最后一个节点被称为“尾节点”。
  • 尾节点指向的是“空”,它在 Java、C++ 和 Python 中分别被记为 null、nullptr 和 None 。
  • 在 C、C++、Go 和 Rust 等支持指针的语言中,上述的“引用”应被替换为“指针”。

如以下代码所示,链表节点 ListNode 除了包含值,还需额外保存一个引用(指针)。因此在相同数据量下,链表比数组占用更多的内存空间

/* 链表节点结构体 */
struct ListNode {int val;               // 节点值struct ListNode *next; // 指向下一节点的指针
};typedef struct ListNode ListNode;/* 构造函数 */
ListNode *newListNode(int val) {ListNode *node, *next;node = (ListNode *) malloc(sizeof(ListNode));node->val = val;node->next = NULL;return node;
}

2.1   链表常用操作

1.   初始化链表

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

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

数组整体是一个变量,比如数组 nums 包含元素 nums[0] 和 nums[1] 等,而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称,比如以上代码中的链表可被记做链表 n0 。

2.   插入节点

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

相比之下,在数组中插入元素的时间复杂度为 O(n) ,在大数据量下的效率较低。

链表插入节点示例

图 4-6   链表插入节点示例

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

3.   删除节点

如图 4-7 所示,在链表中删除节点也非常方便,只需改变一个节点的引用(指针)即可

请注意,尽管在删除操作完成后节点 P 仍然指向 n1 ,但实际上遍历此链表已经无法访问到 P ,这意味着 P 已经不再属于该链表了。

链表删除节点

图 4-7   链表删除节点

/* 删除链表的节点 n0 之后的首个节点 */
// 注意:stdio.h 占用了 remove 关键词
void removeNode(ListNode *n0) {if (!n0->next)return;// n0 -> P -> n1ListNode *P = n0->next;ListNode *n1 = P->next;n0->next = n1;// 释放内存free(P);
}

4.   访问节点

在链表访问节点的效率较低。如上节所述,我们可以在 O(1) 时间下访问数组中的任意元素。链表则不然,程序需要从头节点出发,逐个向后遍历,直至找到目标节点。也就是说,访问链表的第 i 个节点需要循环 i−1 轮,时间复杂度为 O(n) 。

/* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {while (head && head->next && index) {head = head->next;index--;}return head;
}

5.   查找节点

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

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

2.2   数组 VS 链表

表 4-1 总结对比了数组和链表的各项特点与操作效率。由于它们采用两种相反的存储策略,因此各种性质和操作效率也呈现对立的特点。

表 4-1   数组与链表的效率对比

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

2.3   常见链表类型

如图 4-8 所示,常见的链表类型包括三种。

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

/* 双向链表节点结构体 */
struct ListNode {int val;               // 节点值struct ListNode *next; // 指向后继节点的指针struct ListNode *prev; // 指向前驱节点的指针
};typedef struct ListNode ListNode;/* 构造函数 */
ListNode *newListNode(int val) {ListNode *node, *next;node = (ListNode *) malloc(sizeof(ListNode));node->val = val;node->next = NULL;node->prev = NULL;return node;
}

常见链表种类

图 4-8   常见链表种类

2.4   链表典型应用

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

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

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

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

循环链表常被用于需要周期性操作的场景,比如操作系统的资源调度。

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

3   列表

数组长度不可变导致实用性降低。在实际中,我们可能事先无法确定需要存储多少数据,这使数组长度的选择变得困难。若长度过小,需要在持续添加数据时频繁扩容数组;若长度过大,则会造成内存空间的浪费。

为解决此问题,出现了一种被称为「动态数组 dynamic array」的数据结构,即长度可变的数组,也常被称为「列表 list」。列表基于数组实现,继承了数组的优点,并且可以在程序运行过程中动态扩容。我们可以在列表中自由地添加元素,而无须担心超过容量限制。

3.1   列表常用操作

1.   初始化列表

我们通常使用“无初始值”和“有初始值”这两种初始化方法。

// C 未提供内置动态数组

2.   访问元素

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

// C 未提供内置动态数组

3.   插入与删除元素

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

// C 未提供内置动态数组

4.   遍历列表

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

// C 未提供内置动态数组

5.   拼接列表

给定一个新列表 list1 ,我们可以将该列表拼接到原列表的尾部。

// C 未提供内置动态数组

6.   排序列表

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

// C 未提供内置动态数组

3.2   列表实现

许多编程语言都提供内置的列表,例如 Java、C++、Python 等。它们的实现比较复杂,各个参数的设定也非常有考究,例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。

为了加深对列表工作原理的理解,我们尝试实现一个简易版列表,包括以下三个重点设计。

  • 初始容量:选取一个合理的数组初始容量。在本示例中,我们选择 10 作为初始容量。
  • 数量记录:声明一个变量 size ,用于记录列表当前元素数量,并随着元素插入和删除实时更新。根据此变量,我们可以定位列表尾部,以及判断是否需要扩容。
  • 扩容机制:若插入元素时列表容量已满,则需要进行扩容。首先根据扩容倍数创建一个更大的数组,再将当前数组的所有元素依次移动至新数组。在本示例中,我们规定每次将数组扩容至之前的 2 倍。

/* 列表类简易实现 */
struct myList {int *nums;       // 数组(存储列表元素)int capacity;    // 列表容量int size;        // 列表大小int extendRatio; // 列表每次扩容的倍数
};typedef struct myList myList;/* 构造函数 */
myList *newMyList() {myList *list = malloc(sizeof(myList));list->capacity = 10;list->nums = malloc(sizeof(int) * list->capacity);list->size = 0;list->extendRatio = 2;return list;
}/* 析构函数 */
void delMyList(myList *list) {free(list->nums);free(list);
}/* 获取列表长度 */
int size(myList *list) {return list->size;
}/* 获取列表容量 */
int capacity(myList *list) {return list->capacity;
}/* 访问元素 */
int get(myList *list, int index) {assert(index >= 0 && index < list->size);return list->nums[index];
}/* 更新元素 */
void set(myList *list, int index, int num) {assert(index >= 0 && index < list->size);list->nums[index] = num;
}/* 尾部添加元素 */
void add(myList *list, int num) {if (size(list) == capacity(list)) {extendCapacity(list); // 扩容}list->nums[size(list)] = num;list->size++;
}/* 中间插入元素 */
void insert(myList *list, int index, int num) {assert(index >= 0 && index < size(list));// 元素数量超出容量时,触发扩容机制if (size(list) == capacity(list)) {extendCapacity(list); // 扩容}for (int i = size(list); i > index; --i) {list->nums[i] = list->nums[i - 1];}list->nums[index] = num;list->size++;
}/* 删除元素 */
// 注意:stdio.h 占用了 remove 关键词
int removeNum(myList *list, int index) {assert(index >= 0 && index < size(list));int num = list->nums[index];for (int i = index; i < size(list) - 1; i++) {list->nums[i] = list->nums[i + 1];}list->size--;return num;
}/* 列表扩容 */
void extendCapacity(myList *list) {// 先分配空间int newCapacity = capacity(list) * list->extendRatio;int *extend = (int *)malloc(sizeof(int) * newCapacity);int *temp = list->nums;// 拷贝旧数据到新数据for (int i = 0; i < size(list); i++)extend[i] = list->nums[i];// 释放旧数据free(temp);// 更新新数据list->nums = extend;list->capacity = newCapacity;
}/* 将列表转换为 Array 用于打印 */
int *toArray(myList *list) {return list->nums;
}

4   小结

1.   重点回顾

  • 数组和链表是两种基本的数据结构,分别代表数据在计算机内存中的两种存储方式:连续空间存储和分散空间存储。两者的特点呈现出互补的特性。
  • 数组支持随机访问、占用内存较少;但插入和删除元素效率低,且初始化后长度不可变。
  • 链表通过更改引用(指针)实现高效的节点插入与删除,且可以灵活调整长度;但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、循环链表、双向链表。
  • 动态数组,又称列表,是基于数组实现的一种数据结构。它保留了数组的优势,同时可以灵活调整长度。列表的出现极大地提高了数组的易用性,但可能导致部分内存空间浪费。

2.   Q & A

数组存储在栈上和存储在堆上,对时间效率和空间效率是否有影响?

存储在栈上和堆上的数组都被存储在连续内存空间内,数据操作效率是基本一致的。然而,栈和堆具有各自的特点,从而导致以下不同点。

  1. 分配和释放效率:栈是一块较小的内存,分配由编译器自动完成;而堆内存相对更大,可以在代码中动态分配,更容易碎片化。因此,堆上的分配和释放操作通常比栈上的慢。
  2. 大小限制:栈内存相对较小,堆的大小一般受限于可用内存。因此堆更加适合存储大型数组。
  3. 灵活性:栈上的数组的大小需要在编译时确定,而堆上的数组的大小可以在运行时动态确定。

为什么数组要求相同类型的元素,而在链表中却没有强调同类型呢?

链表由结点组成,结点之间通过引用(指针)连接,各个结点可以存储不同类型的数据,例如 int、double、string、object 等。

相对地,数组元素则必须是相同类型的,这样才能通过计算偏移量来获取对应元素位置。例如,如果数组同时包含 int 和 long 两种类型,单个元素分别占用 4 bytes 和 8 bytes ,那么此时就不能用以下公式计算偏移量了,因为数组中包含了两种长度的元素。

# 元素内存地址 = 数组内存地址 + 元素长度 * 元素索引

删除节点后,是否需要把 P.next 设为 None 呢?

不修改 P.next 也可以。从该链表的角度看,从头结点遍历到尾结点已经遇不到 P 了。这意味着结点 P 已经从链表中删除了,此时结点 P 指向哪里都不会对这条链表产生影响了。

从垃圾回收的角度看,对于 Java、Python、Go 等拥有自动垃圾回收的语言来说,节点 P 是否被回收取决于是否有仍存在指向它的引用,而不是 P.next 的值。在 C 和 C++ 等语言中,我们需要手动释放节点内存。

在链表中插入和删除操作的时间复杂度是 O(1) 。但是增删之前都需要 O(n) 查找元素,那为什么时间复杂度不是 O(n) 呢?

如果是先查找元素、再删除元素,确实是 O(n) 。然而,链表的 O(1) 增删的优势可以在其他应用上得到体现。例如,双向队列适合使用链表实现,我们维护一个指针变量始终指向头结点、尾结点,每次插入与删除操作都是 O(1) 。

图片“链表定义与存储方式”中,浅蓝色的存储结点指针是占用一块内存地址吗?还是和结点值各占一半呢?

文中的示意图只是定性表示,定量表示需要根据具体情况进行分析。

  • 不同类型的结点值占用的空间是不同的,比如 int、long、double 和实例对象等。
  • 指针变量占用的内存空间大小根据所使用的操作系统及编译环境而定,大多为 8 字节或 4 字节。

在列表末尾添加元素是否时时刻刻都为 O(1) ?

如果添加元素时超出列表长度,则需要先扩容列表再添加。系统会申请一块新的内存,并将原列表的所有元素搬运过去,这时候时间复杂度就会是 O(n) 。

“列表的出现大大提升了数组的实用性,但副作用是会造成部分内存空间浪费”,这里的空间浪费是指额外增加的变量如容量、长度、扩容倍数所占的内存吗?

这里的空间浪费主要有两方面含义:一方面,列表都会设定一个初始长度,我们不一定需要用这么多。另一方面,为了防止频繁扩容,扩容一般都会乘以一个系数,比如 ×1.5 。这样一来,也会出现很多空位,我们通常不能完全填满它们。

在 Python 中初始化 n = [1, 2, 3] 后,这 3 个元素的地址是相连的,但是初始化 m = [2, 1, 3] 会发现它们每个元素的 id 并不是连续的,而是分别跟 n 中的相同。这些元素地址不连续,那么 m 还是数组吗?

假如把列表元素换成链表节点 n = [n1, n2, n3, n4, n5] ,通常情况下这五个节点对象也是被分散存储在内存各处的。然而,给定一个列表索引,我们仍然可以在 O(1) 时间内获取到节点内存地址,从而访问到对应的节点。这是因为数组中存储的是节点的引用,而非节点本身。

与许多语言不同的是,在 Python 中数字也被包装为对象,列表中存储的不是数字本身,而是对数字的引用。因此,我们会发现两个数组中的相同数字拥有同一个 id ,并且这些数字的内存地址是无须连续的。

C++ STL 里面的 std::list 已经实现了双向链表,但好像一些算法的书上都不怎么直接用这个,是不是有什么局限性呢?

一方面,我们往往更青睐使用数组实现算法,而只有在必要时才使用链表,主要有两个原因。

  • 空间开销:由于每个元素需要两个额外的指针(一个用于前一个元素,一个用于后一个元素),所以 std::list 通常比 std::vector 更占用空间。
  • 缓存不友好:由于数据不是连续存放的,std::list 对缓存的利用率较低。一般情况下,std::vector 的性能会更好。

另一方面,必要使用链表的情况主要是二叉树和图。栈和队列往往会使用编程语言提供的 stack 和 queue ,而非链表。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/147570.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

10.03

代码 #include <iostream>using namespace std; class cz { private:int num1; //实部int num2; //虚部 public:cz(){}cz(int a,int b):num1(a),num2(b){}cz(const cz &other):num1(other.num1),num2(other.num2){}~cz(){}const cz operator(const cz &othe…

websocket逆向【python实现http/https拦截】

python实现http拦截 前言:为什么要使用http拦截一、技术调研二、技术选择三、使用方法前言:为什么要使用http拦截 大多数爬虫玩家会直接选择API请求数据,但是有的网站需要解决扫码登录、Cookie校验、数字签名等,这种方法实现时间长,难度高。需求里面不需要高并发,有没有…

5月22日比特币披萨日,今天你吃披萨了吗?

比特币披萨日 1. Laszlo Hanyecz2. 最贵披萨诞生记3. 梭哈买披萨4. 未完待续 2010年5月22日&#xff0c;美国佛罗里达州的程序员Laszlo Hanyecz&#xff08;拉兹洛哈涅克斯&#xff09;用10000个比特币购买了棒约翰&#xff08;Papa Johns&#xff09;比萨店一个价值25美元的奶…

C语言:选择+编程(每日一练Day9)

目录 选择题&#xff1a; 题一&#xff1a; 题二&#xff1a; 题三&#xff1a; 题四&#xff1a; 题五&#xff1a; 编程题&#xff1a; 题一&#xff1a;自除数 思路一&#xff1a; 题二&#xff1a;除自身以外数组的乘积 思路二&#xff1a; 本人实力有限可能对…

C++核心编程--继承篇

4.6、继承 继承是面向对象三大特征之一 有些类与类之间存在特殊的关系&#xff0c;例如下图中&#xff1a; ​ 我们发现&#xff0c;定义这些类的定义时&#xff0c;都拥有上一级的一些共性&#xff0c;还有一些自己的特性。那么我们遇到重复的东西时&#xff0c;就可以考虑使…

OpenCV读取图像时按照BGR的顺序HWC排列,PyTorch按照RGB的顺序CHW排列

OpenCV读取RGB图像 在OpenCV中&#xff0c;读取的图片默认是HWC格式&#xff0c;即按照高度、宽度和通道数的顺序排列图像尺寸的格式。我们看最后一个维度是C&#xff0c;因此最小颗粒度是C。 例如&#xff0c;一张形状为2562563的RGB图像&#xff0c;在OpenCV中读取后的格式…

R | R及Rstudio安装、运行环境变量及RStudio配置

R | R及Rstudio安装、运行环境变量及RStudio配置 一、介绍1.1 R介绍1.2 RStudio介绍 二、R安装2.1 演示电脑系统2.2 R下载2.3 R安装2.4 R语言运行环境设置&#xff08;环境变量&#xff09;2.4.1 目的2.4.2 R-CMD测试2.4.3 设置环境变量 2.5 R安装测试 三、RStudio安装3.1 RStu…

【pwn入门】用gdb实现第1个pwn

声明 本文是B站你想有多PWN学习的笔记&#xff0c;包含一些视频外的扩展知识。 有问题的源码 #include <stdio.h> #include <stdlib.h> #include <unistd.h> char sh[]"/bin/sh"; int func(char *cmd){system(cmd);return 0; }int main(){char …

【操作系统】进程同步与进程互斥

&#x1f40c;个人主页&#xff1a; &#x1f40c; 叶落闲庭 &#x1f4a8;我的专栏&#xff1a;&#x1f4a8; c语言 数据结构 javaEE 操作系统 Redis 石可破也&#xff0c;而不可夺坚&#xff1b;丹可磨也&#xff0c;而不可夺赤。 进程同步与进程互斥 一、什么是进程同步二、…

redis中list类型的操作

一、特点 Redis列表是简单的字符串列表&#xff0c;按照插入顺序排序。你可以添加一个元素到列表的头部&#xff08;左边&#xff09;或者尾部&#xff08;右边&#xff09;。一个列表最多可以包含 2^32 - 1 个元素 (超过40亿个元素)。 list其底层使用quicklist存储数据 qu…

力扣-383.赎金信

Idea 使用一个hashmap 或者一个int数组存储第二次字符串中每一个字符及其出现的次数 遍历第一个字符串&#xff0c;讲出现的重复字符减1&#xff0c;若该字符次数已经为0&#xff0c;则返回false AC Code class Solution { public:bool canConstruct(string ransomNote, strin…

色彩一致性自动处理方法在遥感图像中的应用

前言 在获取卫星遥感影像时&#xff0c;由于受不均匀的光照、不同的大气条件和不同的传感器设备等因素的影响&#xff0c;遥感影像中会存在局部亮度和色彩分布不均匀的现象&#xff0c;下面是在BigMap地图下载器中收集的几幅谷歌卫星影像&#xff0c;像下面这种都是拼接好的影像…

S32K144 GPIO编程

前面的文章介绍了如何在MDK-Keil下面进行S32K144的开发&#xff0c;下面就使用该工程模板进行GPIO LED的编程试验。 1. 开发环境 S32K144EVB-Q100开发板MDK-Keil Jlink 2. 硬件连接 S32K144EVB-Q100开发板关于LED的原理图如下&#xff1a; 也就是具体连接关系如下&#xf…

键盘上F1至F12键的作用

多年来&#xff0c;我们习惯了最上排的12个按键&#xff0c;从F1到F12&#xff0c;它们被称为“快速功能键”&#xff0c;可以让你更轻松地操作电脑&#xff1b;但是&#xff0c;很多人可能从未使用过它们&#xff0c;也从来不知道它们的用途。那么今天&#xff0c;就向大家科普…

以太网基础学习(二)——ARP协议

一、什么是MAC地址 MAC地址&#xff08;英语&#xff1a;Media Access Control Address&#xff09;&#xff0c;直译为媒体访问控制位址&#xff0c;也称为局域网地址&#xff08;LAN Address&#xff09;&#xff0c;MAC位址&#xff0c;以太网地址&#xff08;Ethernet Addr…

蓝桥杯每日一题2023.10.3

杨辉三角形 - 蓝桥云课 (lanqiao.cn) 题目描述 题目分析 40分写法&#xff1a; 可以自己手动构造一个杨辉三角&#xff0c;然后进行循环&#xff0c;用cnt记录下循环数的个数&#xff0c;看哪个数与要找的数一样&#xff0c;输出cnt #include<bits/stdc.h> using na…

Flutter笔记:滚动之-无限滚动与动态加载的实现(GetX简单状态管理版)

Flutter笔记 无限滚动与动态加载的实现&#xff08;GeX简单状态管理版&#xff09; 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq…

JavaScript系列从入门到精通系列第十二篇:JavaScript中对象的简介和对象的基本操作以及JavaScript中的属性值和属性名

文章目录 前言 一&#xff1a;对象分类 1&#xff1a;内建对象 2&#xff1a;宿主对象 3&#xff1a;自建对象 二&#xff1a;对象的基本操作 1&#xff1a;创建对象 2&#xff1a;向对象中添加属性 3&#xff1a;读取对象中的属性 4&#xff1a;修改对象中的属性 三…

问题: 视频颜色问题,偏绿

参考 什么是杜比视界&#xff1f; - https://www.youtube.com/watch?vldXDQ6VlC7g 【哈士亓说】07&#xff1a;HDR、杜比视界究竟是个啥&#xff1f;为什么这个视频还不是HDR视频&#xff1f; - https://www.youtube.com/watch?vrgb9Xg3cJns 正文 视频应该是 杜比视界 电…

231003-四步MacOS-iPadOS设置无线竖屏随航SideCar

Step 0&#xff1a;MacOS到iPad无线竖屏随航显示&#xff0c;最终效果 Step 1&#xff1a; 下载 Better Display Step 2&#xff1a;在设置中新建虚拟屏幕&#xff0c;创建虚拟屏幕 Step 3&#xff1a;进行如下设置 Step 4&#xff1a;注意事项 ⚠️ 设置后的虚拟屏幕与Sideca…