几分钟彻底了解单链表、带头链表、双向链表、循环链表、带头双向循环链表速通，知识解析与实现。_各种链表的优缺点

 单链表

单链表作为一种基本的数据结构，它的的优点与缺点往往要与顺序表进行比较。

下面先说结论：

链表：

优点：1、可以在任意位置插入与删除，时间复杂度O（1）。

           2、可以随时申请和释放空间、而顺序表需要扩容。（这个很重要，但对于顺序表来讲这个也不是太大的问题，因为顺序表会随着容量变大的扩容频率会越来越低）

缺点：（可以理解与顺序表的优点相照应）

         1、不支持随机访问（如下标访问）。

         2、Cpu高速缓存命中率低，因为内存分配不连续（这个学了计算机组成相关知识会有所了解，不要求过多注意）

顺序表

优点：1、尾插尾删效率高（这个对于链表来说是个奢求，看后面的双向链表解释就明白了）

            2、下标随机访问（因为内存分配连续）

            3、CPU高速缓存命中率高，因为内存分配连续（与上面同理解释）。

缺点 ：1、前半部分插入删除困难，因为需要挪动数据。（内存连续嘛，可以理解）。

              2、空间不够，需扩容，用不完会浪费空间（影响不是那么致命）。

对链表初步了解后，开始将各种链表，着重讲解单链表与带头循环双向链表，一个用得最多、一个功能最完善。

首先是不带头节点的单链表，结构最简单（与后面的链表比较）

     前言：之所以先讲不带头节点的单链表，是因为对比带头单链表，大多数情况都不需要带头单链表。而且，对于大多数的单链表的题目都基本默认不带头节点，要学会使用不带头的，会后面指针的理解有帮助。

图解

 如果都给Node1-Node3都附加上一个地址的话，那可以更加直观的理解链表的结构。

 

 所以next指向的是一个地址，而且还是结构体的地址。

  结构体为： 

 
typedef int Nodedata
 
 typedef struct Node
{
  Nodedata value;
  struct Node* next;
}Node;

     应用方面：如队列的实现等，对于需要用到链表的时候都先优先考虑不带头节点的单链表，因为结构简单，满足需求就可以了。

带头单链表

图解：

与不带头单链表的不同点：在部分情况下，可以达到很好的效果，看题分析，只要经常出来头节点是否为空时候，就用带头的。

双向链表 ,结构比单链表复杂，但解决了单链表中的节点不能访问它的前节点来处理问题的问题。

图解：

 结构体为： 

typedef int Nodedata
 
 typedef struct Node
{
  Nodedata value;
  struct Node* next;
  struct Node* prev;
}Node;

循环链表，结构没有比单链表复杂，但在进行插入操作时比单链表复杂，通过配合双向链表使用效果最佳。

图解：

 结构体为：

typedef int Nodedata
 
 typedef struct Node
{
  Nodedata value;
  struct Node* next;
  struct Node* prev;
}Node;

带头循环双向链表，C++的STL的List的数据结构，链表中结构最复杂、功能最完善（链表中的王者），除了下标访问，基本填补了单链表的各种限制，但实现复杂，实战中慎用。

图解：

 结构体为：

typedef int Nodedata
 
 typedef struct Node
{
  Nodedata value;
  struct Node* next;
  struct Node* prev;
}Node;

 应用方面：无论是中间插入还是删除都十分简单，C++的STL的list就是基于这种类型的链表，使用起来十分方便，但是就是结构复杂，当做题时，使用单链表还是不能满足需求时，可以考虑使用这种数据结构。

单链表和带头循环双向链表的代码实现（码云远程仓库中，学C的话将class改成strcut使用即可）：

单链表的增删查改 · hylprogramming/数据结构的各类型代码实现 - 码云 - 开源中国 (gitee.com)

循环链表的实现 · hylprogramming/数据结构的各类型代码实现 - 码云 - 开源中国 (gitee.com)