Linked List

1. 链表的定义

链表是一个数据的集合，其中每个元素包含下 一个元素的地址;即每个元素包含两部分: 数据和链。

2. 链表在内存中如何存储

链表的每个节点在内存中储存的地址不一定是相连的。链表的一个特点是每个节点除了包含节点数据外，还包含一个指针，指向下一个节点的位置。这意味着链表的节点可以分散在内存中的不同位置，而不需要是连续的。

示例： 链表，有三个节点

• 第一个节点（head）：数据为 1，指针指向地址 0x2008
• 第二个节点（second）：数据为 2，指针指向地址 0x300C
• 第三个节点（third）：数据为 3，指针为 NULL（表示链表的结束） > 假设 int 类型和指针类型在你的系统中占用4个字节（32位），并假设使用小端序（Little Endian）存储格式（在内存中低位字节在低地址，高位字节在高地址）

在这种情况下，链表在内存中的存储示意图如下：

地址       内容
0x1000    +----------------------------------------------------------+
          | data: 00000001 00000000 00000000 00000000                | // 值：1，位模式为小端序
0x1004    | next: 00001000 00100000 00000000 00000000                | // 地址：0x2008，小端序
          +----------------------------------------------------------+
              |
              v
0x2008    +----------------------------------------------------------+
          | data: 00000010 00000000 00000000 00000000                | // 值：2，位模式为小端序
0x200C    | next: 00001100 00110000 00000000 00000000                | // 地址：0x300C，小端序
          +----------------------------------------------------------+
              |
              v
0x300C    +----------------------------------------------------------+
          | data: 00000011 00000000 00000000 00000000                | // 值：3，位模式为小端序
0x3010    | next: 00000000 00000000 00000000 00000000                | // 地址：NULL，小端序
          +----------------------------------------------------------+

3. 链表的特点

3.1 链表的时间和空间复杂度

链表的所有操作的空间复杂度都是O(1)

3.1.1 插入操作

在头部插入：时间复杂度：O(1) 在尾部插入：时间复杂度：O(n)（若有尾指针，可优化到O(1)） 在中间插入：时间复杂度：O(n)（需要遍历到指定位置）

3.1.2 删除操作

删除头节点：时间复杂度：O(1) 删除尾节点：时间复杂度：O(n)（若有尾指针，可优化到O(1)） 删除中间节点：时间复杂度：O(n)（需要遍历到指定位置）

3.1.3 查找操作

按值查找：时间复杂度：O(n)（需要遍历整个链表） 按位置查找：时间复杂度：O(n)（需要遍历到指定位置）

3.1.4 访问操作

访问头节点：时间复杂度：O(1) 访问尾节点：时间复杂度：O(n)（若有尾指针，可优化到O(1)） 访问中间节点：时间复杂度：O(n)（需要遍历到指定位置）

3.1.5 更新操作

更新指定位置的节点：时间复杂度：O(n)（需要遍历到指定位置）

4. 链表的类型

前面只介绍了经典的单链表类型，其实链表还有很多其他类型：

• 单链表：每个节点包含数据和一个指向下一个节点的指针。
• 双链表：每个节点包含数据、一个指向下一个节点的指针和一个指向前一个节点的指针。双链表可以双向遍历，插入和删除操作更加灵活。
• 循环链表：最后一个节点指向第一个节点，形成一个环。循环链表可以用于需要循环访问数据的场景。
• 双向循环链表：结合了双链表和循环链表的特点，既可以双向遍历，又可以循环访问。