[数据结构与算法]数据结构 - 链表

前言

? ? ? ? ? 学习 链表 内容！

一、链表简介

1. 从名字 “链表” 拆开理解：
   • 链：像链子
   • 表：数据集合。就是一堆数据，数据按照一定顺序排列。按照一定顺序排列的元素集合就是表。
   • 链表的概念：链表中存储的是数据，按照一定顺序排列，每一个数据的前面的数据叫做前驱，后面的数据叫做后继。
     
2. 每个节点由两部分组成，数据（节点存放的值）与 下一个节点的地址。节点间通过指针连接起来。
   每一个数据在内存中存储都需要占据一块内存空间，任何一块内存空间都有相应的一个地址。根据首地址和数据类型（占据的内存空间的大小：通过首地址（地址一般指的是首地址）和定义变量的类型（字节大小）就可以确定数据所占唯一的内存空间大小。找到对应的内存空间，然后从内存空间中读写数据即可。
   
3. 链表在内存中的存储：在内存中是散乱存放的，只要内存中有位置，节点就可以存放，节点间通过指针连接。区别于数组，数组在内存中是集中存放在一起的。
   
4. 双向链表
   
5. 循环链表：头尾相连
   
6. 特点：插入删除效率高，读取（查找）效率低。

二、链表的操作

1. 查找：从头结点开始 -> 效率低，需要一个一个判断
2. 更新数据：需要先找到数据 -> 查找，从头结点开始一个一个判断 -> 找到之后替换数据
3. 插入数据
   • 头部插入：新节点在新链表的第一位，新节点的 next 指向原链表的头结点。指向是一个逻辑概念，怎么用代码实现：通过给 next 指针赋值的方式实现更改指向。
     
   • 中间插入：要插入的节点的 next 指向后一个节点，前一个节点 next 指向要插入的节点。
     
   • 尾部插入：最后一个节点的 next 指向新节点。
     
4. 删除数据
   • 删除头节点：头节点删除，第二节点成为头节点
   • 删除中间节点：前节点的 next 指向后节点
     
   • 删除尾节点：直接删除即可

三、具体操作

1. 链表的定义

    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) {} 
   };
   

2. 增加节点

   • 哨兵节点
   • 头插
   • 中间插入
   • 尾部插入
     • 设定场景：本来没有链表，先创建一个出来，然后尾插
     • 定义一个插入函数
     • 处理头节点：第一次调用插入函数时如果链表为空，那么添加的节点一定是头节点，需要首先处理头节点，只调用一次
     • 在尾部插入
       • 找到尾节点：定义一个临时节点，通过遍历找到尾节点，并且此时临时节点指向的就是尾节点
       • 在尾节点插入

3. 删除节点

   • 根据节点内容删除
   • 根据节点位置删除（索引）
   • 删除节点时需要考虑的一些特殊情况
     • 空链表问题
     • 越界索引
     • 删除头节点
   • 步骤
     • 删除非头节点：需要记录当前节点的前一个节点，因为删除当前节点时需要将当前节点的前一个节点的指针指向当前节点的后一个节点。