3.1.链表

链表

链表是一种常见的基础数据结构，它由一系列节点组成，这些节点不必在内存中相连，而是通过指针相互连接，形成一个链式结构。以下是链表的详细定义：

• 节点结构：链表中的每个节点至少包含两个部分，即数据域和指针域。
• • 数据域：用于存储节点的数据，可以是各种数据类型，例如整数、字符、字符串，也可以是更复杂的结构体或对象。
  • 指针域：存储指向下一个节点的地址（在单向链表中）或指向前一个节点和后一个节点的地址（在双向链表中），通过指针将各个节点链接在一起，形成链表的链式结构。
• 链表类型
  • 单向链表：每个节点只有一个指针域，指向后继节点。链表有一个头指针，指向链表的第一个节点，最后一个节点的指针域通常为NULL，表示链表的结束。
  • 双向链表：每个节点有两个指针域，一个指向前驱节点，一个指向后继节点。这样可以在两个方向上遍历链表，增加了操作的灵活性。
  • 循环链表：可以是单向循环链表或双向循环链表。在单向循环链表中，最后一个节点的指针指向链表的头节点，形成一个环；双向循环链表中，头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。

简单链表

也是单向链表，每个节点包含一个数据和一个指向下一个节点的指针，最后一个节点的指针指向nullptr（空指针）。如图：

在前面的定义中也提到，链表的各个节点并不必须是在内存中连续的，所以对于链表来说，优缺点就很显而易见了，优点就是执行插入和删除等操作十分灵活，而在随机访问元素时效率较低。数组在删除和插入元素的时候，最坏的情况是删除和插入第一个元素，这样要把整个数组的所有元素前移或者后移一位，复杂度为O(n)，最好的情况是删除和插入最后一个元素，复杂度为O(1)，平均复杂度也为O(n/2)=O(n)。下面用几个图来解释一下删除和插入操作与普通的数组有什么不同。

1.链表的删除

对于链表的删除，我们只需要改变要删除的节点的前驱元的指针即可，十分便捷

2.链表的插入

而链表的插入就需要改变一个指针和新建一个指针了，不过相较于数组的操作简单的多，

双向链表

相较于简单链表，每个节点新增了一个指向前驱元的指针，第一个元素的前指针指向nullptr。

这样做的好处就是可以从后往前遍历链表，更灵活。

循环链表

相较于前两个，循环链表就是在前面的基础上进行了闭环。单向循环链表就是把最后一个节点的指针指向第一个节点，双向循环链表就是把第一个节点的前指针指向最后一个节点，最后一个节点的后指针指向第一个节点，这里就不进行画图演示了。