虽然以前写过一次链表，但是真的已经忘得一干二净了
链表理论基础
- 链表：通过指针串联在一起的线性结构，每个节点都由数据域和指针域组成。
- 指针域：存放下一个节点的指针，最后一个节点的指针域指向null，也即空指针
- head：链表的入口节点，也即链表的头节点
链表的类型
-
单链表
以上所讲的最简单的链表为单链表（指针域指针只能指向下一个节点）
-
双链表
每个节点有两个指针域，一个指向下一个节点，一个指向上一个节点
可以向前、向后查询
（头结点处向前查询的指针为空指针）
-
循环链表
相当于单链表列表首尾相连，也即单链表最后一个指针指向head
可以用于解决约瑟夫环问题（这是什么问题？）
链表的存储方式
数组在内存中连续分布，而链表不是连续分布。
链表通过指针域的指针链接在内存中的各个节点，因此是胡乱分布在内存的某地址上的（取决于操作系统的内存管理）
链表的定义
-
如何定义一个单链表：
class ListNode: def _init_(self, val, next=None): self.val = val self.next = nextstruct ListNode{ int val; ListNode *next; ListNode(int x) : val(x), next(null){} //节点的构造函数 } -
注意构造函数，如果不定义构造函数，在初始化时就不能直接赋值：
//自己定义了构造函数 ListNode* head = new ListNode(5); //没有定义构造函数，使用默认构造函数 ListNode* head = new ListNode(); head->val = 5;
链表的操作
- 删除节点
如果链表中有节点A\B\C\D，现需要删除节点C，只需将B节点中的next指针指向D即可。
注意，在c++中，C节点依旧存在于内存当中，因此需要手动释放，但Python中有自己的回收机制，不需要手动释放文章来源：https://www.toymoban.com/news/detail-500749.html
- 添加节点
与上述相同，将前一个节点的next指针指向该节点，将该节点的next指针指向下一节点即可。文章来源地址https://www.toymoban.com/news/detail-500749.html
性能分析
- 链表操作，插入、删除的时间复杂度为O（1），但是查询的时间复杂度为O(n)，因为查询链表需要从头开始查询
- 数组操作，插入、删除时间复杂度为O(n)，因为数组牵一发而动全身，但是查询时间复杂度为O(1)
- 数组长度固定，想改动长度就要定义新数组；链表不固定
203.移除链表元素
- 注意虚拟节点的使用，为了更好地统一地管理头结点
- 以及以前写的是Python语言，现在改c++有些变动
- c++中要注意释放内存
707.设计链表
- 要学会自行定义链表结构体
- 学会初始化链表怎么写
- 在c++中，要写初始化，相应也要写
public: MyLinkdList(){ //初始化，此时不用定义数据类型，数据类型在下面private里面定义 _size = 0; _dummyHead = new ListNode(0); } private: int _size; ListNode* )dummyHead; - dummyHead： 虚拟头节点
206.反转链表
- 设置了
preNode,cur,nextNode三个节点，与此同时也要注意，如果head为空节点，那么nextNode是不存在的，所以要单独讨论 - 在设置反转后的末尾节点指向nullptr时，并不是让指向的节点deleta就行，直接delete节点会导致报错，应该要让她先指向nullptr，然后delete。
- 递归法没太懂
到了这里，关于代码随想录Day3|链表理论基础|203.移除链表元素|707.设计链表|206.反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
