C++小记 -链表

链表

文章目录

• 链表
• 链表基础理论
• • 链表的类型
  • • 单链表
    • 双链表
    • 循环链表
    • 链表的存储方式
    • 链表的定义
    • 链表的操作
    • • 添加节点
      • 删除节点
      • 性能分析
      • 构建链表
      • 删除节点（内存泄漏的坑）
      • • 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 vector& vec) {if (vec.empty()) return nullptr;ListNode* head = new ListNode(vec[0]);ListNode* cur = head;for (int i = 1; i 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 #include 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 vector& vec) {if (vec.empty()) return nullptr;ListNode* head = new ListNode(vec[0]);ListNode* cur = head;for (int i = 1; i 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 val next;}cout vector 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;}