赞
踩
目录
「数组 array」是一种线性数据结构,其将相同类型元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的「索引 index」。图 4-1 展示了数组的主要术语和概念。
图 4-1 数组定义与存储方式
我们可以根据需求选用数组的两种初始化方式:无初始值、给定初始值。在未指定初始值的情况下,大多数编程语言会将数组元素初始化为 0 。
- int arr[5] = { 0 }; // { 0, 0, 0, 0, 0 }
- int nums[5] = { 1, 3, 2, 5, 4 };
数组元素被存储在连续的内存空间中,这意味着计算数组元素的内存地址非常容易。给定数组内存地址(即首元素内存地址)和某个元素的索引,我们可以使用图 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;
- }
数组元素在内存中是“紧挨着的”,它们之间没有空间再存放任何数据。如图 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 所示,若想要删除索引 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];
- }
- }
总的来看,数组的插入与删除操作有以下缺点。
在大多数编程语言中,我们既可以通过索引遍历数组,也可以直接遍历获取数组中的每个元素。
- /* 遍历数组 */
- void traverse(int *nums, int size) {
- int count = 0;
- // 通过索引遍历数组
- for (int i = 0; i < size; i++) {
- count++;
- }
- }
在数组中查找指定元素需要遍历数组,每轮判断元素值是否匹配,若匹配则输出对应索引。
因为数组是线性数据结构,所以上述查找操作被称为“线性查找”。
- /* 在数组中查找指定元素 */
- int find(int *nums, int size, int target) {
- for (int i = 0; i < size; i++) {
- if (nums[i] == target)
- return i;
- }
- return -1;
- }
在复杂的系统环境中,程序难以保证数组之后的内存空间是可用的,从而无法安全地扩展数组容量。因此在大多数编程语言中,数组的长度是不可变的。
如果我们希望扩容数组,则需重新建立一个更大的数组,然后把原数组元素依次拷贝到新数组。这是一个 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;
- }
数组存储在连续的内存空间内,且元素类型相同。这种做法包含丰富的先验信息,系统可以利用这些信息来优化数据结构的操作效率。
连续空间存储是一把双刃剑,其存在以下缺点。
数组是一种基础且常见的数据结构,既频繁应用在各类算法之中,也可用于实现各种复杂数据结构。
内存空间是所有程序的公共资源,在一个复杂的系统运行环境下,空闲的内存空间可能散落在内存各处。我们知道,存储数组的内存空间必须是连续的,而当数组非常大时,内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。
「链表 linked list」是一种线性数据结构,其中的每个元素都是一个节点对象,各个节点通过“引用”相连接。引用记录了下一个节点的内存地址,通过它可以从当前节点访问到下一个节点。
链表的设计使得各个节点可以被分散存储在内存各处,它们的内存地址是无须连续的。
图 4-5 链表定义与存储方式
观察图 4-5 ,链表的组成单位是「节点 node」对象。每个节点都包含两项数据:节点的“值”和指向下一节点的“引用”。
如以下代码所示,链表节点 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;
- }
建立链表分为两步,第一步是初始化各个节点对象,第二步是构建引用指向关系。初始化完成后,我们就可以从链表的头节点出发,通过引用指向 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
。
在链表中插入节点非常容易。如图 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;
- }
如图 4-7 所示,在链表中删除节点也非常方便,只需改变一个节点的引用(指针)即可。
请注意,尽管在删除操作完成后节点 P
仍然指向 n1
,但实际上遍历此链表已经无法访问到 P
,这意味着 P
已经不再属于该链表了。
图 4-7 链表删除节点
- /* 删除链表的节点 n0 之后的首个节点 */
- // 注意:stdio.h 占用了 remove 关键词
- void removeNode(ListNode *n0) {
- if (!n0->next)
- return;
- // n0 -> P -> n1
- ListNode *P = n0->next;
- ListNode *n1 = P->next;
- n0->next = n1;
- // 释放内存
- free(P);
- }
在链表访问节点的效率较低。如上节所述,我们可以在 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;
- }
遍历链表,查找链表内值为 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;
- }
表 4-1 总结对比了数组和链表的各项特点与操作效率。由于它们采用两种相反的存储策略,因此各种性质和操作效率也呈现对立的特点。
表 4-1 数组与链表的效率对比
数组 | 链表 | |
---|---|---|
存储方式 | 连续内存空间 | 分散内存空间 |
缓存局部性 | 友好 | 不友好 |
容量扩展 | 长度不可变 | 可灵活扩展 |
内存效率 | 占用内存少、浪费部分空间 | 占用内存多 |
访问元素 | O(1) | O(n) |
添加元素 | O(n) | O(1) |
删除元素 | O(n) | O(1) |
如图 4-8 所示,常见的链表类型包括三种。
- /* 双向链表节点结构体 */
- 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 常见链表种类
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
双向链表常被用于需要快速查找前一个和下一个元素的场景。
循环链表常被用于需要周期性操作的场景,比如操作系统的资源调度。
数组长度不可变导致实用性降低。在实际中,我们可能事先无法确定需要存储多少数据,这使数组长度的选择变得困难。若长度过小,需要在持续添加数据时频繁扩容数组;若长度过大,则会造成内存空间的浪费。
为解决此问题,出现了一种被称为「动态数组 dynamic array」的数据结构,即长度可变的数组,也常被称为「列表 list」。列表基于数组实现,继承了数组的优点,并且可以在程序运行过程中动态扩容。我们可以在列表中自由地添加元素,而无须担心超过容量限制。
我们通常使用“无初始值”和“有初始值”这两种初始化方法。
// C 未提供内置动态数组
列表本质上是数组,因此可以在 O(1) 时间内访问和更新元素,效率很高。
// C 未提供内置动态数组
相较于数组,列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 �(1) ,但插入和删除元素的效率仍与数组相同,时间复杂度为 O(n) 。
// C 未提供内置动态数组
与数组一样,列表可以根据索引遍历,也可以直接遍历各元素。
// C 未提供内置动态数组
给定一个新列表 list1
,我们可以将该列表拼接到原列表的尾部。
// C 未提供内置动态数组
完成列表排序后,我们便可以使用在数组类算法题中经常考察的“二分查找”和“双指针”算法。
// C 未提供内置动态数组
许多编程语言都提供内置的列表,例如 Java、C++、Python 等。它们的实现比较复杂,各个参数的设定也非常有考究,例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。
为了加深对列表工作原理的理解,我们尝试实现一个简易版列表,包括以下三个重点设计。
size
,用于记录列表当前元素数量,并随着元素插入和删除实时更新。根据此变量,我们可以定位列表尾部,以及判断是否需要扩容。- /* 列表类简易实现 */
- 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;
- }
数组存储在栈上和存储在堆上,对时间效率和空间效率是否有影响?
存储在栈上和堆上的数组都被存储在连续内存空间内,数据操作效率是基本一致的。然而,栈和堆具有各自的特点,从而导致以下不同点。
为什么数组要求相同类型的元素,而在链表中却没有强调同类型呢?
链表由结点组成,结点之间通过引用(指针)连接,各个结点可以存储不同类型的数据,例如 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) 。
图片“链表定义与存储方式”中,浅蓝色的存储结点指针是占用一块内存地址吗?还是和结点值各占一半呢?
文中的示意图只是定性表示,定量表示需要根据具体情况进行分析。
在列表末尾添加元素是否时时刻刻都为 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
,而非链表。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。