网站开发视频,优设网网址,新乡优化,计算机平面设计主要做什么链表 文章目录 链表链表基础理论链表的类型单链表双链表循环链表 链表的存储方式链表的定义链表的操作添加节点删除节点 性能分析构建链表删除节点#xff08;内存泄漏的坑#xff09;1.直接移除2.使用虚拟头结点3.delete指针后#xff0c;要将指针置为NULL#xff01;内存泄漏的坑1.直接移除2.使用虚拟头结点3.delete指针后要将指针置为NULL 完整代码示例 链表基础理论
什么是链表链表是一种通过指针串联在一起的线性结构每一个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个节点的指针域指向null空指针的意思。
链表的入口节点称为链表的头结点也就是head。
链表的类型
单链表 双链表 单链表中的指针域只能指向节点的下一个节点。
双链表每一个节点有两个指针域一个指向下一个节点一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
循环链表
循环链表顾名思义就是链表首尾相连。
循环链表可以用来解决约瑟夫环 链表的存储方式
数组是在内存中是连续分布的但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 而是散乱分布在内存中的某地址上分配机制取决于操作系统的内存管理。 这个链表起始节点为2 终止节点为7 各个节点分布在内存的不同地址空间上通过指针串联在一起。
链表的定义
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};有同学说了我不定义构造函数行不行答案是可以的C默认生成一个构造函数。
但是这个构造函数不会初始化任何成员变量下面我来举两个例子
通过自己定义构造函数初始化节点
ListNode* head new ListNode(5);使用默认构造函数初始化节点
ListNode* head new ListNode();
head-val 5;所以如果不定义构造函数使用默认构造函数的话在初始化的时候就不能直接给变量赋值
链表的操作
添加节点 删除节点
删除D节点如图所示
delete root;只要将C节点的next指针 指向E节点就可以了。
那有同学说了D节点不是依然存留在内存里么只不过是没有在这个链表里而已。
是这样的所以在C里最好是再手动释放这个D节点释放这块内存。
性能分析 数组在定义的时候长度就是固定的如果想改动数组的长度就需要重新定义一个新的数组。
链表的长度可以是不固定的并且可以动态增删 适合数据量不固定频繁增删较少查询的场景。
构建链表
// 数组构造链表
ListNode* construct_array(const vectorint vec) {if (vec.empty()) return nullptr;ListNode* head new ListNode(vec[0]);ListNode* cur head;for (int i 1; i vec.size(); i) {cur-next new ListNode(vec[i]);cur cur-next;}cur-next NULL;return head;
}删除节点内存泄漏的坑
1.直接移除
ListNode* removeElements1(ListNode* head, int val) {// 删除头节点while (head!NULL head-val val){ListNode* tmp head;head head-next;delete tmp;tmp NULL;}// 删除非头节点ListNode* cur head;while (cur ! NULL cur-next ! NULL){if (cur-next-val val){ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;tmp NULL;}else{cur cur-next;}}return head;
}2.使用虚拟头结点
ListNode* removeElements2(ListNode* head, int val) {ListNode* dummyHead new ListNode(0); // 设置一个虚拟头结点dummyHead-next head; // 将虚拟头结点指向head这样方便后面做删除操作ListNode* cur dummyHead;while (cur-next ! NULL) {if (cur-next-val val) {ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;tmp NULL; }else {cur cur-next;}}head dummyHead-next;delete dummyHead;return head;
}3.delete指针后要将指针置为NULL
在delete指针后将指针置为NULL。例如delete tmp; tmp NULL; 在delete指针后将指针置为NULL。例如delete tmp; tmp NULL; 在delete指针后将指针置为NULL。例如delete tmp; tmp NULL;
不然会发生内存泄漏
不然会发生内存泄漏
不然会发生内存泄漏
完整代码示例
#include iostream
#include vector
using namespace std;// 单链表
struct ListNode
{int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode() : val(NULL), next(NULL){} // 节点的构造函数ListNode(int x) : val(x), next(NULL){} // 节点的构造函数
};// 数组构造链表
ListNode* construct_array(const vectorint vec) {if (vec.empty()) return nullptr;ListNode* head new ListNode(vec[0]);ListNode* cur head;for (int i 1; i vec.size(); i) {cur-next new ListNode(vec[i]);cur cur-next;}cur-next NULL;return head;
}// 添加节点
void append(ListNode* head, int value){if (!head){head new ListNode(value);}else{ListNode* cur head;while (cur-next){cur cur-next;}cur-next new ListNode(value);}
}/* 删除节点
在delete指针后将指针置为NULL。例如delete tmp; tmp NULL;
在delete指针后将指针置为NULL。例如delete tmp; tmp NULL;
在delete指针后将指针置为NULL。例如delete tmp; tmp NULL;
*/
ListNode* removeElements(ListNode* head, int val) {// 删除头节点while (head ! NULL head-val val){ListNode* tmp head;head head-next;delete tmp;tmp NULL;}// 删除非头节点ListNode* cur head;while (cur ! NULL cur-next ! NULL){if (cur-next-val val){ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;tmp NULL;}else{cur cur-next;}}return head;
}// 打印链表
void printList(ListNode* head){ListNode* cur head;while (cur){cout cur-val ;cur cur-next;}cout endl;
}int main() {vectorint arry { 1, 3, 3, 4, 5 };ListNode* head construct_array(arry);printList(head);append(head, 6);printList(head);head removeElements(head, 3);printList(head);system(PAUSE);return 0;
}
