链表

2023-10-082023-10-09数据结构与算法 / 数据结构20 分钟读完 (大约2971个字)0次访问

链表

一、结构特性

链表是通过指针将一系列离散的内存块串联在一起的线性表数据结构。

主要特点：

线性表数据结构
离散的内存空间
指针关联
动态申请内存空间

1.1 离散的的内存空间

链表是通过指针将一系列离散的内存块串联在一起的线性数据结构。

每一个内存块称为链表的 “节点”，节点包含两部分：数据和指针。

数据：保存的是真实数据，可以是任意类型
指针：保存的是下一个节点的内存地址

PS: 指针占用的空间大小根据操作系统及编译环境而定，大多为 8 字节或 4 字节

1 2	______ ______ ______ ______ ______ ______ \| data \| next \| -> \| data \| next \| -> \| data \| next \| -> NULL

链表的第一个节点称为 “头节点”，最后一个节点称为 “尾节点”。

链表节点在内存中不是连续存储的，而是通过指针相连，所以链表节点是比较散乱的。

1.2 动态申请内存空间

在内存空间的申请方式上，链表和数组是不一样的：

数组是一次性申请一大块连续的内存空间
而链表则是在需要的时候才动态申请，每次申请一个节点大小的内存空间

比如说，一开始链表只有 1 个节点：

1 2	______ ______ \| data \| next \| -> NULL

当需要新节点时，就动态生成一个节点：

1 2	______ ______ ______ ______ \| data \| next \| -> \| data \| next \| -> NULL

链表是按需使用内存空间，不够时申请，不需要时释放，在内存利用率上比数组要高。

二、常用操作

2.1 访问

访问某个位置的节点时，数组可以通过地址偏移算出节点的位置，直接随机访问。

但链表是一种链式离散的内存分布，没办法算出节点位置，所以链表不支持随机访问。

比如说，如果想要访问第 K 个节点，只能从前往后遍历，直到找到第 K 个节点。

ListNode findKth(ListNode head, int k) {
  ListNode p = head;
  for (int i = 0; i < k && p != null; i++) {
    p = p.next;
  }
  return p;
}

访问的时间复杂度是 O(n)。

2.2 插入

相比于数组的插入，链表的插入操作更加简单。

数组在插入之后，为了保持内存数据的连续性，一般都需要做数据搬移。

但链表本身就是离散的，无需维护内存数据连续性，因此只需要修改相邻节点的指针即可。

void insert(ListNode p, ListNode newNode) {
  newNode.next = p.next;
  p.next = newNode;
}

 ______ ______                              ______ ______
| data | next | --                     --> | data | next |
                 |                     |
                 |                     |
                 |    ______ ______    |
                 --> | data | next | ---

                        newNode

插入的时间复杂度是 O(1)。

2.3 删除

删除操作和插入操作类似，也只需要修改相邻节点的指针即可。


```java
void delete(ListNode p) {
  deleteNode = p.next;
  p.next = p.next.next;
  deleteNode.next = null;
}

                 ----------------------
                 |                    |
                 |                    |
 ______ ______   |    ______ ______   |     ______ ______
| data | next | --   | data | next |   --> | data | next |

                        deleteNode

删除的时间复杂度是 O(1)。

三、链表类型

3.1 单向链表

单向链表就是上面介绍的链表，节点中包含 2 个属性：数据和指针。

单向链表有明确的方向、头节点和尾节点。

3.2 双向链表

除了单向链表以外，还有一种双向链表，节点中会带有指向前一个节点的指针。

1 2	______ ______ ______ ______ ______ ______ ______ ______ ______ \| prev \| data \| next \| <=> \| prev \| data \| next \| <=> \| prev \| data \| next \|

双向链表和单向链表的结构差别不大，仅仅是多了一个前向指针。

不过由于多了一个前向指针，所以在插入和删除时，需要同时维护前后两个指针：

双向链表的插入，时间复杂度 O(1)：

void insert(ListNode p, ListNode newNode) {
  newNode.next = p.next;
  newNode.prev = p;
  p.next.prev = newNode;
  p.next = newNode;
}

双向链表的删除，时间复杂度 O(1)：

void delete(ListNode p) {
  deleteNode = p.next;
  p.next = p.next.next;
  p.next.prev = p;
  deleteNode.prev = deleteNode.next = null;
}

双向链表的优点是，可以支持 O(1) 时间复杂度的情况下找到前驱节点，这在某些情况下非常实用。

3.3 循环链表

还有一种特殊的链表，叫做循环链表。

循环是指链表的尾节点会指向头节点，从而形成一个环。

       ------------------------------------------
       |                                        |
       |                                        |
       v                                        |
 ______ ______      ______ ______      ______ ______
| data | next | -> | data | next | -> | data | next |

循环链表既可以是单链，也可以是双链，取决于节点的定义。

在循环链表中，没有头尾节点的说法，任意节点都可以视作头节点。

四、注意事项

4.1 链表的指针

在对链表进行操作时，需要特别注意链表指针的修改，不要弄错了。

链表指针的修改是有一定顺序的，如果指针指向错了，就很容易出现死循环、数据丢失等情况。

比如，单向链表的删除：

void insert(ListNode p, ListNode newNode) {
  newNode.next = p.next;
  p.next = newNode;
}

交换一下这2个操作：

void insert(ListNode p, ListNode newNode) {
  p.next = newNode;
  newNode.next = p.next;
}

就会导致链表出现环，而且后面的链表节点全都丢失了。

4.2 链表的环

在遍历循环链表时，注意判断遍历条件，否则有可能遍历出现死循环。

比如，对循环链表这样子遍历就会导致死循环：

ListNode p = head;
while (p != null) {
  // do something
  p = p.next;
}

循环链表是头尾相连的，不会出现 p == null 的情况。

4.3 内存碎片问题

如果频繁地对链表进行插入和删除，就会导致内存频繁地进行申请和释放，很容易造成内存碎片。

所以在使用链表时，需要注意一下这个内存碎片的情况。

五、优缺点

5.1 优点

长度不固定：灵活扩展，需要时申请，不需要时释放
内存效率高：不会浪费内存空间（指针不算浪费空间，是必要的）
插入删除操作效率高：复杂度为 O(1)

5.2 缺点

不支持随机访问：只能从头节点开始遍历
占用内存多：链表节点需要额外的空间存储指针信息
对缓存局部性不友好：因为链表节点是离散的，不连续

六、典型应用

6.1 单向链表

资源管理
- 单向链表可以用来管理资源，例如内存分配中的空闲块链表，通过将空闲的内存块连接成一个链表，可以方便地进行分配和释放。
队列实现
- 单向链表可以用于实现队列（FIFO）的数据结构，通过在链表的尾部添加元素，并在链表的头部移除元素，可以实现高效的入队和出队操作。
图的表示
- 在图的表示中，每个顶点通常包含一个指向其邻居顶点的链表。单向链表可以用于表示有向图或无向图中顶点的邻居关系。
任务调度
- 在任务调度系统中，可以使用单向链表来管理待执行的任务列表，通过将任务连接成一个链表，可以按照特定的顺序进行调度和执行。
多级反馈队列调度算法
- 多级反馈队列调度算法中，任务被分成多个优先级队列，并按照一定规则进行调度。每个队列可以使用单向链表来管理任务，实现按优先级进行任务调度。
符号表和字典实现
- 在符号表和字典的实现中，可以使用单向链表来存储键值对。每个节点包含一个键和一个值，并通过指针连接成一个链表，实现高效的查找、插入和删除操作。

6.2 双向链表

LRU缓存（Least Recently Used Cache）
- LRU缓存是一种常见的缓存替换策略，其中最近最少使用的数据被淘汰。双向链表可以用来实现LRU缓存，每次访问数据时，将其移到链表的头部，这样尾部的节点就是最近最少使用的数据，可以方便地淘汰。
双向队列（Deque）
- 双向队列是一种具有队列和栈的特性的数据结构，可以在队列的头部和尾部进行插入和删除操作。双向链表可以用来实现双向队列，提供高效的插入和删除操作。
图的表示
- 在图的表示中，每个顶点通常包含一个指向其邻居顶点的链表。双向链表可以用于表示有向图或无向图中顶点的邻居关系，每个顶点可以同时保存指向前一个邻居和后一个邻居的指针。
浏览器历史记录
- 在浏览器中，双向链表可以用来实现浏览器的历史记录功能。每次访问一个新的页面，将其添加到链表的尾部，可以方便地实现前进和后退功能。
文本编辑器的撤销和重做操作
- 在文本编辑器中，双向链表可以用来实现撤销和重做操作。每次编辑操作都可以将编辑内容添加到链表的尾部，可以通过向前或向后遍历链表来实现撤销和重做操作。
音乐播放器的播放列表
- 在音乐播放器中，双向链表可以用来实现播放列表，每个节点表示一个音乐文件，可以方便地在当前歌曲的前后插入或删除歌曲。

6.3 循环链表

约瑟夫问题（Josephus Problem）
- 在约瑟夫问题中，有n个人围成一个环形，每次从指定位置开始计数，并按照固定规则将当前位置的人移出环形，直到最后只剩下一个人。环形链表可以用来模拟和解决这个问题。
循环队列（Circular Queue）
- 循环队列是一种特殊的队列数据结构，当队列的尾部达到数组的末尾时，可以绕回数组的开头，形成一个循环。环形链表可以用来实现循环队列，提供高效的队列操作。
循环链表遍历
- 使用环形链表可以实现循环遍历，即从任意节点开始遍历整个链表，而不会出现遍历到尾节点后的终止条件。
环形缓冲区（Circular Buffer）
- 环形缓冲区是一种常见的数据结构，用于在固定大小的缓冲区中循环存储数据。环形链表可以用来实现环形缓冲区，实现高效的数据读写操作。
快慢指针算法（Floyd’s Cycle Detection Algorithm）
- 快慢指针算法是一种使用两个指针在环形链表中寻找环的算法。该算法可以应用于检测环形链表中是否存在环以及找到环的起始节点等问题。

参考

https://www.hello-algo.com/chapter_array_and_linkedlist/linked_list/

https://www.programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%93%BE%E8%A1%A8%E7%9A%84%E7%B1%BB%E5%9E%8B

https://time.geekbang.org/column/article/41013

链表

http://example.com/datastructure/list/linkedlist/

作者

jiaduo

发布于

2023-10-08

更新于

2023-10-09

许可协议

链表

链表