数据结构 双向链表(1)
目录
1.链表的分类
2.双向链表的介绍
1.链表的分类
链表的种类非常多,链表按单向或双向、带头或不带头、循环或不循环这三个维度进行分类， 组合
起来共有8种链表结构，具体如下：
1.从单向和双向维度划分:
- 单向链表：每个节点只包含一个指向下一个节点的指针。数据只能沿着一个方向进行遍历，从链
表的头节点开始，依次访问每个节点，直到遇到空指针表示到达链表尾部。比如实现简单的线性数
据存储，像学生成绩的简单记录，依次存储每个学生的成绩 。
- 双向链表：每个节点除了有一个指向下一个节点的指针外，还有一个指向前一个节点的指针。这
使得链表的遍历可以双向进行，既可以从头节点向尾节点遍历，也可以从尾节点到头节点遍历。在
需要频繁地在链表中向前和向后查找节点的场景中比较适用，如实现浏览器的前进和后退功能 。
2.从带头和不带头维度划分:
- 带头链表：存在一个哨兵位的头节点，这个头节点不存储实际有效的数据，只是作为链表的一个
标志，方便对链表进行操作。比如在进行插入和删除操作时，不需要对第一个节点的情况进行特殊
处理，降低了代码的复杂性。
- 不带头链表：没有专门的头节点，链表的第一个节点就存储实际的数据，在对链表进行插入和删
除第一个节点操作时，需要单独处理这种特殊情况。
3.从循环和不循环维度划分:
- 循环链表：链表的最后一个节点的指针不再指向空，而是指向链表的头节点（对于带头链表）或
者第一个有效节点（对于不带头链表），形成一个环形结构，可以从任意一个节点开始遍历整个链
表。常用于实现一些需要循环处理数据的场景，如约瑟夫环问题。
- 不循环链表：链表的最后一个节点的指针指向空，表示链表结束，这是最常见的链表形式 。
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：无头单向非循环链表(单链表)
和双向带头循环链表:
- 无头单向非循环链表：结构相对简单，常作为其他复杂数据结构的子结构， 比如哈希表中的哈
希桶、图的邻接表等。此外，在笔试面试中经常出现，用于考察对链表基本操作（如插入、删除、
遍历等）的理解和掌握。我们之前所讲的单链表就是无头单向非循环链表。
- 带头双向循环链表：虽然结构相对复杂，但在实际应用中，当需要单独存储数据时较为常用。它
的优势在于插入和删除操作更加统一和简便，不需要对边界情况（如头节点、尾节点）进行过多的
特殊处理，提高了代码的可读性和可维护性 ，在实现一些复杂的数据结构（如操作系统中的进程
调度队列）时经常被使用。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来
很多优势，实现后而简单了，后面我们代码实现了就知道了。
2.双向链表
2.1 结构和概念
双向链表就是我们上面提到的 "带头双向循环链表" , 我们简称为"双向链表"。
注意：这里的“带头”跟前面在讲解单链表时我们说的“头结点”是两个概念，实际前面的在单链表阶
段称呼不严谨，但是为了更好的理解就直接称为单链表的头结点。
带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨
的”。
双向链表（Doubly Linked List）是链表的一种，它的每个节点除了存储数据元素外，还包含两个
指针，一个指向前驱节点，一个指向后继节点，从而使链表具备双向遍历的能力 。以下是关于双
向链表的详细介绍：
结构特点:
- 节点结构：双向链表的节点由三部分组成，分别是数据域（存储实际的数据，如整数、字符
等）、前驱指针（ prev ，指向前一个节点的地址）和后继指针（ next ，指向后一个节点的地
址） 。在C语言中，通常可以用结构体来定义双向链表的节点，示例代码如下：
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;- 头节点（哨兵位节点）：实际应用中，双向链表常带有头节点（也称为哨兵位节点），这个节点
不存储有效数据，仅作为链表的起始标志。头节点的 prev 指针指向链表的最后一个节点（形成
循环结构时）， next 指针指向链表的第一个有效节点。双向链表还可以是循环链表，即尾节点的
next 指针指向头节点，头节点的 prev 指针指向尾节点，构成一个环形结构。
双向链表除了上面的基本内容外，还有其初始化，链表的打印，尾插，头插以及尾删，头删和在特
定位置插入和删除等多种操作。我们在下一篇关于双向链表的代码内容实现中将会逐一详细介绍。
谢谢大家的观看。