概述
什么是链表
链表是一种物理存储单元上非连续，非顺序的存储结构。链表中的元素不一定是顺序存储的，为了保证链表中元素的连续性，一般使用一个指针来找到下一个元素。链表不具有随机访问的特性，在链表中根据索引来查找元素只能从头开始，它的时间复杂度是O(n)。
如上图所示，链表的节点包括两个部分：
- 存储数据元素的数据域（内存空间）
- 存储指向下一个节点地址的指针域
链表可以动态地进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。
链表的种类包括单链表、双链表、单向循环链表和双向循环链表。对于链表的每一个节点，我们可以使用结构体进行设计，其主要内容有数据元素和一个指向下一个节点的指针。链表的初始化主要完成以下工作：创建一个单链表的前置节点并向后逐步添加节点，一般指的是申请节点的空间，同时对一个节点赋空值 (null)。
总的来说，链表是一种灵活的数据结构，它允许我们在任何位置插入和删除元素，而不需要像数组那样移动大量的元素。然而，这种灵活性是以牺牲更多的内存为代价的。
链表和数组的差异
链表和数组是两种基本的数据结构，它们在内存存储上的表现不一样，所以也有各自的特点。
数组的特点：
- 在内存中，数组是一块连续的区域。
- 数组需要预留空间，在使用前需要提前申请所占内存的大小。
- 数组支持随机访问，时间复杂度为O(1)。
- 在数组起始位置处，插入数据和删除数据效率低。插入数据时，待插入位置的元素和它后面的所有元素都需要向后搬移。
链表的特点：
- 在内存中，链表的元素可以在任意地方，空间是分散的，不需要连续。
- 链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址。
- 查找数据时效率低,时间复杂度为O(n)，因为链表的空间是分散的，所以不具有随机访问性。
- 任意位置插入元素和删除元素效率较高，时间复杂度为O(1)。
总的来说，对于想要快速访问数据，不经常有插入和删除元素的时候，选择数组；对于需要经常的插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表。
链表的基本操作
插入
插入只需要考虑要插入位置前驱节点和后继节点（双向链表的情况下需要更新后继节点）即可，其他节点不受影响，因此在给定指针的情况下插入的操作时间复杂度为O(1)。这里给定指针中的指针指的是插入位置的前驱节点，伪代码如下：
temp = 待插入位置的前驱节点.next
待插入位置的前驱节点.next = 待插入指针
待插入指针.next = temp
删除
只需要将需要删除的节点的前驱指针的 next 指针修正为其下下个节点即可，注意考虑边界条件。伪代码如下：
待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next
遍历
遍历比较简单，直接上伪代码。
当前指针 = 头指针
while 当前节点不为空 {
print(当前节点)
当前指针 = 当前指针.next
}
链表结构的优缺点
链表作为一种基本的数据结构，有其独特的优点和缺点。
优点：
- 动态扩展性：链表是一种动态数据结构，可以在运行时根据需要增加或减少节点，非常方便快捷。
- 插入和删除效率高：在链表中插入和删除节点的时间复杂度为O(1)，远小于数组的O(n)。这是因为链表中的元素不需要连续存储，可以直接通过指针进行操作。
- 节省空间：链表中的节点只在需要时才会被分配内存，因此可以有效利用内存资源。
- 支持双向操作：链表中的每个节点都有指向下一个节点的指针，因此可以很容易地实现双向操作，比如回溯算法。
缺点：
- 访问元素效率低：相对于数组的直接索引访问，链表需要从头节点开始逐个访问节点，访问某个特定元素的时间复杂度为O(n)。
- 内存消耗：由于链表中的每个节点都需要存储指向下一个节点的指针，因此链表的内存消耗会比数组大。
总的来说，链表在处理大量数据、需要频繁插入和删除操作的场景下具有优势，但在需要频繁访问特定元素的场景下，数组可能会更有优势。
解题思路
链表的操作问题，一般题目中不允许我们修改节点的值，而只能修改节点的指向操作。
思路通常都不难，写对链表问题的技巧是：一定要先想清楚思路，并且必要的时候在草稿纸上画图，理清「穿针引线」的先后步骤，然后再编码。