数据结构 （7）线性表的链式存储

前言

       线性表是一种基本的数据结构，用于存储线性序列的元素。线性表的存储方式主要有两种：顺序存储和链式存储。链式存储，即链表，是一种非常灵活和高效的存储方式，特别适用于需要频繁插入和删除操作的场景。

链表的基本概念

     链表是一种通过节点（Node）相互链接构成的线性数据结构。每个节点包含两部分：

1. 数据域（Data Field）：用于存储数据元素。
2. 指针域（Pointer Field）：用于存储指向下一个节点的指针（或引用）。

     根据链表的不同结构，可以分为以下几种类型：

1. 单向链表（Singly Linked List）：每个节点只包含一个指向下一个节点的指针。
2. 双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向下一个节点，一个指向上一个节点。
3. 循环链表（Circular Linked List）：最后一个节点的指针指向头节点，形成一个环。

单向链表

基本操作

1. 初始化链表：创建一个头节点，并初始化其指针为nullptr。
2. 插入操作：
   • 头插法：在新节点中存储数据，将其next指向当前头节点，然后更新头节点为新节点。
   • 尾插法：遍历链表找到最后一个节点，将新节点的next设置为nullptr，然后最后一个节点的next指向新节点。
3. 删除操作：根据给定条件找到待删除节点的前一个节点，然后将其next指向待删除节点的next。
4. 查找操作：遍历链表，找到满足条件的节点。
5. 遍历链表：从头节点开始，依次访问每个节点的数据域，直到遇到nullptr。

双向链表

基本操作

1. 初始化链表：创建一个头节点，并初始化其prev和next指针为nullptr。
2. 插入操作：
   • 头插法：更新新节点的next为当前头节点，更新当前头节点的prev为新节点，然后更新头节点为新节点，并设置新节点的prev为nullptr。
   • 尾插法：遍历链表找到最后一个节点，将新节点的prev指向最后一个节点，新节点的next设置为nullptr，然后最后一个节点的next指向新节点。
3. 删除操作：根据给定条件找到待删除节点，更新其前一个节点的next和后一个节点的prev。
4. 查找操作：从头节点开始，依次访问每个节点的数据域，直到找到满足条件的节点或遍历到nullptr。
5. 遍历链表：从头节点开始，可以向前或向后遍历。

循环链表

        循环链表与单向链表或双向链表的主要区别在于最后一个节点的指针不是指向nullptr，而是指向头节点。

基本操作

1. 初始化链表：创建一个头节点，并初始化其指针指向自身。
2. 插入操作：类似于单向链表或双向链表，只是最后一个节点的指针需要指向头节点。
3. 删除操作：更新相关节点的指针，使其形成一个连续的环。
4. 查找操作：从头节点开始遍历，直到找到满足条件的节点或回到头节点。
5. 遍历链表：从头节点开始，直到再次回到头节点。

链表的优缺点

优点

1. 插入和删除效率高：不需要移动大量元素，只需调整指针。
2. 内存利用率高：不需要预先分配固定大小的数组。
3. 灵活性强：可以动态调整链表的大小。

缺点

1. 访问效率低：需要从头节点开始遍历，无法直接通过索引访问元素。
2. 占用额外空间：每个节点需要存储指针。

总结

        链表是一种非常灵活的数据结构，适用于需要频繁插入和删除操作的场景。不同类型的链表（单向链表、双向链表、循环链表）适用于不同的应用场景。了解链表的基本结构和操作对于掌握数据结构非常重要。

 结语   

帝是我的见证人

所以我竭尽全力让它成功

！！！