如何利用社交网站做招聘,怎样注册小程序店铺,网站网络营销平台,wordpress编辑无效文章目录 前言链表简介头节点与尾节点特性 分类单向链表双向链表循环链表 单链表基本操作定义并初始化单链表读取节点插入节点删除节点修改节点 参考资料写在最后 前言
本系列专注更新基本数据结构#xff0c;现有以下文章#xff1a;
【算法与数据结构】数组.
【算法与数… 文章目录 前言链表简介头节点与尾节点特性 分类单向链表双向链表循环链表 单链表基本操作定义并初始化单链表读取节点插入节点删除节点修改节点 参考资料写在最后 前言
本系列专注更新基本数据结构现有以下文章
【算法与数据结构】数组.
【算法与数据结构】链表.
【算法与数据结构】哈希表. 链表
简介
链表是一种线性结构但不同于数组在内存中占据一块连续的内存链表使用的是内存中一组任意的存储单元来存储具有相同的数据类型的元素。这组任意的存储单元可以是连续的也可以不是连续的。
以单链表为例链表的存储方式如下图所示。 链表将一组任意的存储单元串联在一起。每一个存储单元被称为链表的一个节点节点是一个结构体。结构体内存储两个变量一个是节点的值另一个是指向链表下一个节点的指针。一个节点值为整型的链表结构体可以这样定义
struct ListNode {int val;ListNode* next;
}头节点与尾节点
链表的头节点指的是链表的第一个节点有的资料中将第一个元素之前的节点称为头节点就是我们会面要讲到的呀节点通常给一个链表的头节点我们就可以通过遍历得到链表中的每一个节点。这里需要区分一下头节点与头指针。
头指针是指向链表第一个节点的指针。在单向链表中头指针指向链表的头节点就是后面会提到的呀节点的next指针即 dummy-next。在双向链表中头指针同样指向链表的头节点。
链表的尾节点是指链表中最后一个节点。在单向链表中尾节点的 next 指针通常指向空指针 nullptr表示链表的末尾。在双向链表中尾节点的 next 指针同样指向空指针 nullptr而 prev 指针则指向倒数第二个节点表示双向链表的末尾。
特性
链表不需要实现事先分配内存在需要存储空间时可以临时申请。因为链表不需要内存中一块连续的存储空间所以相比数组可以更好的利用内存中零散的空间。相比于数组使用链表执行数据的插入、删除以及移动效率会高一点。但是空间开销相比数组会大一点因为链表的每一个节点需要存储两个变量而数组的每个位置只需要存储一个变量。 分类
单向链表
定义
单向链表指的是链表的每一个节点里的指针都会指向下一个节点的链表。
单向链表节点类设计如下所示 C11 \texttt{C11} C11 的标准库中虽然也定义了 forward_list \texttt{forward\_list} forward_list 单向链表但因为单向链表的定义与操作相对简单所有我们通常自己定义节点。
struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* _next) : val(x), next(_next) {}};结构图 双向链表
定义
双向链表是对单向链表的升级除了具备单向链表的 next 节点之外还有一个 prev 指针该指针指向当前节点的上一个节点。头节点的上一个节点为 nullptr 节点尾节点的下一个节点为 nullptr。
双向链表的节点类设计如下所示。 C11 \texttt{C11} C11 的标准库中虽然也定义了 list \texttt{list} list 双向链表.
struct ListNode {int val;ListNode* next;ListNode* prev;ListNode() : val(0), next(nullptr), prev(nullptr) {}ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}ListNode(int x, ListNode* _next, ListNode* _prev) : val(x), next(_next), prev(_prev) {}};结构图 循环链表
定义
循环链表有两种一种是在单向链表中将尾节点的 next 指针指向由空指针改为指向头节点形成的单向循环链表另一种指的是双向循环链表。
双向循环循环链表是在双向链表的基础上将链表的头节点和尾节点连接在一起即将头节点的 prev 指针指向尾节点尾节点的 next 指针指向头节点。通过这样的操作可以实现从循环链表的任何一个节点出发都能找到其他的任意节点。
循环链表的节点类设计与双向链表的节点类设计一致。
结构图 单链表基本操作
链表是一种具有增、删、改、查这四种基本操作的基本数据结构。单链表作为一种形式最简单的链表自然也具备这四种操作。本节会介绍定义并初始化单链表以及提到的四种基本操作中间还会穿插介绍如何计算链表的长度。
在这单向链表、双向链表和循环链表中单向链表最为基础并且是算法类面试题中链表这一块的考察重点需要重点掌握。
定义并初始化单链表
// 定义节点
struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* _next) : val(x), next(_next) {}};// 定义链表头节点
ListNode* head new ListNode(0);在此例子中我们首先定义了链表的节点类然后定义了一个节点 head 作为链表的头节点头节点的 next 指针指向一个空节点。
读取节点
在数组这种顺序结构中我们计算任意一个元素的存储位置是很容易的C/C 中虽然是通过下标进行索引的但其底层是通过数组的首地址与下标之间的计算获得对应位置的地址再取地址中的元素。但是在单链表中我们无法像数组那样通过索引得知第 N 个节点是什么只能从头节点开始一个节点一个节点的查找。
获得链表的第 N 个节点N 1 的算法思路
在查找链表的第 N 个节点之前需要先统计链表中的节点总数如果总数 cnt N则直接返回 nullptr否则接着执行以下步骤。声明一个指向链表头节点的节点 cur使用 for 循环或者 while 循环迭代将节点向后移动 N-1 次将 cur 更新为 cur-next。循环结束后返回 cur 即为需要查找的节点。
// 计算以 head 为头节点的链表的节点数
int getN(ListNode* head) {int cnt 0;while (head ! nullptr) {cnt;head head-next;}return cnt;
}ListNode* getNthNode(ListNode* head, int N) {int cnt getN(head);if (N cnt) {return nullptr;}ListNode* cur head;while (N 1) {cur cur-next;}return cur;
}在此例子中我们使用函数 getN 计算链表的长度节点的数量。我们从链表的头节点开始遍历链表只要当前的链表不为空nullptr就更新 cnt cnt 1并更改 head 为下一个节点。
插入节点
在给定链表中的指定位置插入一个节点需要考虑以下几个问题
1给定的链表是否为空2指定位置是否越界3指定的位置位于链表的头部、中间还是尾部。
如果给定的链表为空则直接返回新插入的节点如果指定的位置越界直接返回给定链表的头节点即可。对于问题3中的三种情况我们逐条进行分析。
在链表中间插入元素
顾名思义插入节点的位置位于链表的中间位置在链表第 i 个位置头节点被称为第一个位置之前插入值为 val 的链节点通常
1遍历链表找到第 i-1 个节点 preNode2新建需要插入的节点 newNode3将节点 newNode 的 next 指针连接到指向preNode 节点的下一个节点4将节点 preNode 的 next 指针连接到 newNode 节点5最后返回头节点 head。
一图胜千言上述变换过程见下图所示 在链表头部插入节点
在链表头部插入节点更加简单
新建需要插入的节点 newNode将节点 newNode 的 next 指针连接到指向head 节点newNode 作为链表新的头节点。
在链表尾部插入元素
遍历找到链表的最后一个节点将该节点的 next 指针指向新建的节点 newNode 即可。
总结
下面就是一个往给定链表中指定位置插入一个元素的示例
ListNode* insertNode(ListNode* head, int pos, int newVal) {// 问题1if (head nullptr) { return new ListNode(newVal);}// 问题2int N getN(head); // 获取链表长度if (pos 0 || pos N1) { // 注意这里的 大于 N1 是考虑到要在尾部插入节点return head;}// 问题3ListNode* cur head;int i 1;while (i pos-1) { // 找到第 pos 个节点后退出循环cur cur-next;i;}ListNode* newNode new ListNode(newVal);// 在链表头部插入节点if (cur head) { cur-next head;return newNode;}// 在链表中间或尾部插入节点newNode-next cur-next; // 当在在链表尾部插入节点时此时 cur-next nullptrcur-next newNode;return head;
}Note以上代码中 在链表中间插入元素 是在链表的第 i 个位置之前插入节点如果是在第 i 个位置之后插入节点代码会有细微的变换请读者注意。 删除节点
删除链表中的节点与插入节点操作一样都需要考虑一下三个情况
待删除的链表为空删除的节点是非法的越界删除的节点分别位于链表的头部、中间位置或者尾部。
以下以图解的形式对第三种请款进行说明。前两种情况比较简单将直接在代码中进行展示。 1删除链表中间位置的节点需要先找到被删除节点的上一个节点 prevNode
2将 prevNode 的 next 指针指向 prev-next-next
3最后得到删除的链表。
示例代码
ListNode* removeNode(ListNode* head, int pos) {// 链表为空if (head nullptr) { return nullptr;}// 删除的节点是非法的int N getN(head); // 获取链表长度if (pos 0 || pos N) {return head;}// 情况三ListNode* preNode head;int i 1;while (i pos-1) { // 找到第 pos 个节点后提出循环preNode preNode-next;i;}// 删除头节点if (preNode head) { return preNode-next;}// 删除链表中间或尾部的节点preNode-next preNode-next-next;return head;
}修改节点
修改主要指的是修改节点的值。比如将第 i 个节点的值修改为指定值 val。思路清晰直接看代码
void modifyNthVal(ListNode* head, int n, int val) {if (head nullptr) {return;}int N getN(head); // 获取链表长度if (n 0 || n N) { // 越界return;}ListNode* cur head;while (--n) {cur cur-next; }cur-val val;
}参考资料
【书籍】大话数据结构
【文章】一文讲透链表操作看完你也能轻松写出正确的链表代码
【文章】链表基础知识 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家觉得有些地方需要补充欢迎评论区交流。
next; } cur-val val; } # 参考资料【书籍】大话数据结构【文章】[一文讲透链表操作看完你也能轻松写出正确的链表代码](https://www.cnblogs.com/lonely-wolf/p/15761239.html)【文章】[链表基础知识](https://algo.itcharge.cn/02.Linked-List/01.Linked-List-Basic/01.Linked-List-Basic/)---# 写在最后如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。如果大家觉得有些地方需要补充欢迎评论区交流。最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
