网站建设的布局对网络推广的影响,温州网站优化搜索,在iis里面创建网站,辽宁建设工程信息网作用内存空间是所有程序的公共资源#xff0c;在一个复杂的系统运行环境下#xff0c;空闲的内存空间可能散落在内存各处。我们知道#xff0c;存储数组的内存空间必须是连续的#xff0c;而当数组非常大时#xff0c;内存可能无法提供如此大的连续空间。此时链表的灵活性优势…内存空间是所有程序的公共资源在一个复杂的系统运行环境下空闲的内存空间可能散落在内存各处。我们知道存储数组的内存空间必须是连续的而当数组非常大时内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。
链表(linked list)是一种线性数据结构其中的每个元素都是一个节点对象各个节点通过“引用”相连接。引用记录了下一个节点的内存地址通过它可以从当前节点访问到下一个节点。
链表的设计使得各个节点可以被分散存储在内存各处它们的内存地址是无须连续的。 观察上图 链表的组成单位是节点 (node)对象。每个节点都包含两项数据节点的“值”和指向下一节点的“引用”。
链表的首个节点被称为“头节点”最后一个节点被称为“尾节点”。尾节点指向的是“空”它在 Java、C 和 Python 中分别被记为 \(\text{null}\)、\(\text{nullptr}\) 和 \(\text{None}\) 。在 C、C等支持指针的语言中上述的“引用”应被替换为“指针”。 如以下代码所示链表节点 ListNode 除了包含值还需额外保存一个引用指针。因此在相同数据量下链表比数组占用更多的内存空间。
/* 链表节点结构体 */
struct ListNode {int val; // 节点值ListNode *next; // 指向下一节点的指针ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};5.1 链表常用操作
5.1.1 初始化链表 建立链表分为两步第一步是初始化各个节点对象第二步是构建引用指向关系。初始化完成后我们就可以从链表的头节点出发通过引用指向 next 依次访问所有节点。
/* 初始化链表 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;数组整体是一个变量比如数组 nums 包含元素 nums[0] 和 nums[1] 等而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称比如以上代码中的链表可被记做链表 n0 。
5.1.2 插入节点
在链表中插入节点非常容易。如下图所示假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P 则只需要改变两个节点引用指针即可时间复杂度为O(1)。
相比之下在数组中插入元素的时间复杂度为O(n)在大数据量下的效率较低。 /* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {ListNode *n1 n0-next;P-next n1;n0-next P;
}5.1.3 删除节点
如下图所示在链表中删除节点也非常方便只需改变一个节点的引用指针即可。请注意尽管在删除操作完成后节点 P 仍然指向 n1 但实际上遍历此链表已经无法访问到 P 这意味着 P 已经不再属于该链表了。 /* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode *n0) {if (n0-next nullptr)return;// n0 - P - n1ListNode *P n0-next;ListNode *n1 P-next;n0-next n1;// 释放内存delete P;
}5.1.4 访问节点
在链表访问节点的效率较低。如上节所述我们可以在 \(O(1)\) 时间下访问数组中的任意元素。链表则不然程序需要从头节点出发逐个向后遍历直至找到目标节点。也就是说访问链表的第 i个节点需要循环i - 1轮时间复杂度为 O(n) 。
/* 访问链表中索引为 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.1.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;
}5.2 数组 VS 链表
下表总结对比了数组和链表的各项特点与操作效率。由于它们采用两种相反的存储策略因此各种性质和操作效率也呈现对立的特点。 5.3 常见链表类型
如下图所示常见的链表类型包括三种。
单向链表即上述介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点将最后一个节点称为尾节点尾节点指向空 \(\text{None}\) 。环形链表如果我们令单向链表的尾节点指向头节点即首尾相接则得到一个环形链表。在环形链表中任意节点都可以视作头节点。双向链表与单向链表相比双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点下一个节点和前驱节点上一个节点的引用指针。相较于单向链表双向链表更具灵活性可以朝两个方向遍历链表但相应地也需要占用更多的内存空间。
/* 双向链表节点结构体 */
struct ListNode {int val; // 节点值ListNode *next; // 指向后继节点的指针ListNode *prev; // 指向前驱节点的指针ListNode(int x) : val(x), next(nullptr), prev(nullptr) {} // 构造函数
};5.4 链表典型应用
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
栈与队列当插入和删除操作都在链表的一端进行时它表现出先进后出的的特性对应栈当插入操作在链表的一端进行删除操作在链表的另一端进行它表现出先进先出的特性对应队列。哈希表链地址法是解决哈希冲突的主流方案之一在该方案中所有冲突的元素都会被放到一个链表中。图邻接表是表示图的一种常用方式在其中图的每个顶点都与一个链表相关联链表中的每个元素都代表与该顶点相连的其他顶点。
双向链表常被用于需要快速查找前一个和下一个元素的场景。
高级数据结构比如在红黑树、B 树中我们需要访问节点的父节点这可以通过在节点中保存一个指向父节点的引用来实现类似于双向链表。浏览器历史在网页浏览器中当用户点击前进或后退按钮时浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。LRU 算法在缓存淘汰算法LRU中我们需要快速找到最近最少使用的数据以及支持快速地添加和删除节点。这时候使用双向链表就非常合适。
循环链表常被用于需要周期性操作的场景比如操作系统的资源调度。
时间片轮转调度算法在操作系统中时间片轮转调度算法是一种常见的 CPU 调度算法它需要对一组进程进行循环。每个进程被赋予一个时间片当时间片用完时CPU 将切换到下一个进程。这种循环的操作就可以通过循环链表来实现。数据缓冲区在某些数据缓冲区的实现中也可能会使用到循环链表。比如在音频、视频播放器中数据流可能会被分成多个缓冲块并放入一个循环链表以便实现无缝播放。
