🌈赏金任务 - 链表都有哪几类，对应的特点是什么？

lingxi · 2023 年3 月 13 日 10:22

赏金任务每周更新，请持续关注哦

题目

模拟面试场景，面试官提问以下问题，你如何回答。
链表都有哪几类，对应的特点是什么？

参与方式

本帖下方回复你的答案即可

赏金

100元京东购物卡

活动时间

2023年3月13日 - 2023年3月19日

本周赏金任务汇总：🌈 赏金任务发布 2023-03-13

本问题参与赏金活动，详情点击赏金活动上线啦丨做赏金任务挑战千元奖金查看活动介绍

difei · 2023 年3 月 15 日 03:57

链表分类和特点

链表是一种常见的数据结构，用于存储一系列元素。链表可以分为以下几类：

单向链表（Singly Linked List）：单向链表中，每个节点只有一个指向下一个节点的指针。这种链表的优点是空间复杂度较低，缺点是查找元素的效率较低。
双向链表（Doubly Linked List）：双向链表中，每个节点既有一个指向下一个节点的指针，也有一个指向前一个节点的指针。这种链表的优点是在查找某个元素的前驱或后继时效率较高，但是需要额外的指针空间。
循环链表（Circular Linked List）：循环链表中，最后一个节点指向第一个节点，形成一个环。这种链表的优点是可以很方便地实现循环操作，缺点是需要额外的指针空间。
双向循环链表（Doubly Circular Linked List）：双向循环链表是双向链表和循环链表的结合体，每个节点既有一个指向下一个节点的指针，也有一个指向前一个节点的指针，最后一个节点指向第一个节点，形成一个环。

链表的特点是可以高效地进行插入和删除操作，但查找元素的效率较低，需要遍历整个链表。链表还可以动态地分配内存空间，而不像数组一样需要一开始就指定大小。

TESTCASE · 2023 年3 月 15 日 04:26

一共4种分别是以下这四种：
单向链表、双向链表、循环链表、双向循环链表
1、单向链表（Singly linked list）：
特点：
每个节点只有一个指针指向下一个节点，最后一个节点指向 NULL。单向链表只能顺序遍历，不能回溯。插入和删除节点的时间复杂度为 O(1)，但是访问特定节点的时间复杂度为 O(n)。
实际运用场景：
单向链表常用于实现栈、队列和哈希表等数据结构。例如，在实现一个队列时，可以使用单向链表作为底层数据结构。在队列的尾部添加元素时，只需要在链表的末尾插入一个新节点；在队列的头部删除元素时，只需要将链表的头节点指针指向下一个节点即可。单向链表还可以用于实现基数排序、拓扑排序和 Dijkstra 算法等算法。
2、双向链表（Doubly linked list）：
特点：
每个节点同时有指向前一个节点和下一个节点的指针。因此，双向链表可以前后遍历。插入和删除节点的时间复杂度为 O(1)，但是每个节点需要额外存储一个指针，增加了空间复杂度。
实际运用场景：
双向链表常用于实现 LRU 缓存淘汰算法、LRU-K 缓存淘汰算法和快速排序等算法。例如，在实现 LRU 缓存淘汰算法时，可以使用双向链表作为底层数据结构。当缓存中的某个数据被访问时，可以将该数据所在的节点移动到链表的末尾，这样，最近访问的数据就位于链表的末尾，最少访问的数据就位于链表的头部。
3、循环链表（Circular linked list）：
特点：
最后一个节点指向第一个节点，形成一个循环。循环链表可以用于实现队列和环形缓冲区等数据结构。
实际运用场景：
循环链表常用于实现音乐播放器、游戏中的循环地图和环形缓冲区等场景。例如，在实现一个音乐播放器时，可以使用循环链表来管理播放列表。当播放到最后一首歌时，可以自动跳转到第一首歌，从而形成一个循环播放的效果。
4、双向循环链表（Doubly circular linked list）：
特点：
同时具有双向链表和循环链表的特点。
实际运用场景：
双向循环链表可以同时具有双向链表和循环链表的特点，常用于实现哈希表和 LRU 缓存淘汰算法等数据结构和算法。例如，在实现哈希表时，可以使用双向循环链表来处理哈希冲突。当多个键映射到同一个哈希桶时，可以使用双向循环链表将它们连接起来，形成一个链表。当需要查找某个键时，只需要遍历该哈希桶对应的链表即可。双向循环链表还可以用于实现 LRU 缓存淘汰算法，它可以在 O(1) 的时间复杂度内将最少访问的数据删除，并将新的数据插入到链表的末尾。

wiki918 · 2023 年3 月 15 日 07:28

1.什么是链表

链表一种线性的数据结构，通过指针将一个个零散的内存块连接起来，链表的每个内存块称为结点。

什么是链表，什么又是节点呢？看图：
链表可以看成一条项链，节点就是其中一环。一环一环套起来，就形成了项链（链表）。

2.链表的种类

a.单链表

每个结点除了存储数据data外，还需要记录下个结点的地址，称为后继指针next。
单链表有两个特殊的结点，分别是第一个结点——头结点和最后一个结点——尾结点。
头结点：用来记录链表的基地址。
尾结点：尾结点的后继指针指向一个空地址NULL。

b. 双向链表

每个结点除了存储数据data外，还会会记录上一个结点和下一个结点的地址。
单链表和双向链表的区别
单链表的结点只有一个指向，即后继指针next指向下一个结点。
双向链表的结点有两个指向，一个后继指针next指向下一个结点，还有一个前驱指针prev指向上一个结点。

c. 循环单链表

带头结点的循环单链表当head等于head->next时链表为空,不带头结点的循环单链表当head等于NULL时链表为空。

d. 循环双链表

和循环单链表类似，循环双链表的构造源自双链表，即将终端节点的next指针指向链表中第一个结点，将链表中第一个结点的prior指针指向终端结点，如上图所示。循环双链表同样有带头结点和不带头结点之分。带头结点的循环双链表head->next和 head->prior两个指针都等于head时链表为空,不带头结点的循环双链表当head等于NULL时链表为空。

e. 静态链表

静态链表借助一维数组来表示,如上图所示。上图中的左图是静态链表,右图是其对应的一般链表。一般链表结点空间来自于整个内存,静态链表则来自于一个结构体数组（或者向量vector）。数组中每一个结点（结构体结点，而非链表节点）含有两个分量:一个是数据元素分量data;另一个是指针分量（注意这里的指针不是地址，而是一个类似于数组下标的索引，是一个数字）,指示了当前结点的直接后继结点在数组中的位置(这和一般链表中next指针的地位是同等的)

3.链表的特性

由于链表的内存空间是零散的，所以不支持随机访问。
插入、删除不需要移动数据，所以效率高。
因为链表的每个内存块都不是连续的，所以不需要提前计算内存的大小，内存空间可以根据结点数量的改变而改变。

1078894520_5590 · 2023 年3 月 20 日 03:20

链表类型	特点	优点	缺点	适用场景
单向链表（Singly Linked List）	每个节点只有一个指针，指向下一个节点。	1.插入、删除元素的时间复杂度为O(1)； 2.空间利用率高。	1.不能随机访问元素，必须从头节点开始遍历； 2.不方便反向遍历； 3.删除元素需要找到前驱节点，增加了时间复杂度。	适合对数据的插入、删除操作比较频繁的场景。
双向链表（Doubly Linked List）	每个节点有两个指针，分别指向前一个节点和后一个节点。	1.支持双向遍历，可以快速访问前驱和后继节点； 2.删除元素时不需要查找前驱节点，时间复杂度为O(1)。	1.相比单向链表，需要多维护一个指针，占用更多空间； 2.插入、删除操作需要修改前驱节点和后继节点的指针，增加了时间复杂度。	适合需要双向遍历或者需要频繁进行插入、删除操作的场景。
循环链表（Circular Linked List）	最后一个节点的指针指向第一个节点。	1.可以无限循环遍历； 2.在实现某些算法时有较好的应用。	1.相比单向链表、双向链表，需要特殊处理尾节点的指针，增加了时间复杂度； 2.删除节点需要先找到前驱节点，增加了时间复杂度。	适合需要循环遍历的场景，如轮播图、哈希表等。
带头节点的链表（Linked List with Head Node）	头节点存储链表长度等信息，不存储数据。	1.插入、删除操作时不需要特殊处理头节点，简化了操作； 2.可以快速获取链表长度等信息。	1.相比普通链表，需要额外维护头节点，占用更多空间； 2.头节点的引入增加了代码的复杂度。	适合需要频繁获取链表长度等信息或者需要进行复杂操作的场景。
带尾节点的链表（Linked List with Tail Node）	尾节点存储最后一个节点的指针，可以快速访问尾节点。	1.插入元素时不需要遍历链表查找尾节点，时间复杂度为O(1)； 2.可以快速访问尾节点。	1.相比普通链表，需要额外维护尾节点，占用更多空间； 2.删除尾节点时需要遍历链表查找前驱节点，增加了时间复杂度。	适合需要频繁在链表末尾进行插入操作或需要快速访问链表末尾节点的场景。