目录

1.什么是链表

2.链表常见几种形式

3.无头单向非循环链表的实现

3.1结点结构的定义

3.2函数接口的实现

3.2.1尾插

3.2.2尾删

4. 带头双向循环链表的实现

4.1结点结构的定义

4.2函数接口的实现

5.两种链表的差异

①尾插与尾删的时间复杂度

②头插与头删的时间复杂度

③函数形参为何一个是二级指针，一个是一级指针？

完整源码

无头单向非循环链表

SList.h

SList.c

test.c

带头双向循环链表

List.h

List.c

test.c

正文

1.什么是链表

像数组一样，链表也用来表示一系列的元素。事实上，能用数组来做的事情，一般也可以用链表来做。然而，链表的实现跟数组是不一样的，在不同场景它们会有不同的性能表现。

计算机的内存就像一大堆格子，每格都可以用来保存比特形式的数据。当要创建数组时，程序会在内存中找出一组连续的空格子，给它们起个名字，以便你的应用存放数据。

我们之前说过，计算机能够直接跳到数组的某一索引上。如果代码要求它读取索引 4的值，那么计算机只需一步就可以完成任务。重申一次，之所以能够这样，是因为程序事先知道了数组开头所在的内存地址——例如地址是 1000——当它想去索引 4时，便会自动跳到 1004处。

与数组不同的是，组成链表的格子不是连续的。它们可以分布在内存的各个地方。这种不相邻的格子，就叫作结点。

那么问题来了，计算机怎么知道这些分散的结点里，哪些属于这个链表，哪些属于其他链表呢？这就是链表的关键了：每个结点除了保存数据，它还保存着链表里的下一结点的内存地址。

这份用来指示下一结点的内存地址的额外数据，被称为链。链表如下图所示。  

注意：

1.从上图可以看出，链式结构在逻辑上是来连续的，但是在物理上不一定连续。

2.现实中的结点一般都是从堆上来申请的。

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

2.链表常见几种形式

①单向或者双向

②带头或者不带头

③循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用到的还是这两种结构：

1. 无头单向非循环链表

结构简单，一般不会用来单独进行存储数据。实际中更多是作为其它数据结构的子结构，如哈希表、图的邻接表等等。另外这种结构在笔试面试中出现比较多。

2. 带头双向循环链表

结构最复杂，一般用于单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后发现结构会带来很多优势，实现反而简单了。

3.无头单向非循环链表的实现

就我个人而言，我认为虽然无头单向非循环链表是这几个链表中结构最简单的，但是实现却是最复杂的。我们学会了头单向非循环链表的实现，别的链表实现应当不在话下。

3.1结点结构的定义

typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

如上文所讲，一个结点包含的内容有数据data和保存下一个结点的地址的指针。

链表正式由一个个这样的结点串连起来的，所以我们只需要记住排在最前面的头结点的位置，就能访问链表里任意一个结点。

注意：无头单向非循环链表里的头结点指的是链表中的第一个结点，它本身也存储着有效数据。而后面所讲的带头双向循环链表中的头结点仅仅是作为链表起始的标志，并不会存储有效数据。

3.2函数接口的实现

//申请一个结点
SLTNode* BuySLTNode(SLTDataType data);
//创建一个链表，包含数据为0~n
SLTNode* CreateSList(int n);
//释放内存
void SLTDestroy(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType data);
//尾删
void SLTPopBack(SLTNode** pphead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType data);
//头删
void SLTPopFront(SLTNode** pphead);
//查找data的结点
SLTNode* SLTFind(SLTNode** pphead, SLTDataType data);
//在pos位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data);
//在pos位置后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType data);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//打印链表内容
void SLTPrint(SLTNode* phead);

由于代码量过大，为了避免影响阅读体验太差，我将完整代码置于文章末尾。此处，我们来细致的学习两个函数尾插与尾删，其它函数与其原理几乎相同。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType data);
//尾删
void SLTPopBack(SLTNode** pphead);

3.2.1尾插

void SLTPushBack(SLTNode** pphead, SLTDataType data)
{
  SLTNode* newNode = BuySLTNode(data);
  //若为第一次插入，则分情况处理
  if (*pphead==NULL)
  {
    *pphead = newNode;
    return;
  }
  //找尾
  SLTNode* tail = *pphead;
  while(tail->next)
  {
    tail = tail->next;
  }
  //找到了，进行尾插
  tail->next = newNode;
}

首先将tail也指向头结点，通过变化tail来找到尾结点，如下图所示为找尾的过程：

此时，tail所指向的结点的next为NULL，则循环结束，进行尾插。尾插只需要将tail所指向的结点的next指针赋值为newNode即可。

3.2.2尾删

void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //分情况处理
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //找尾
  SLTNode* tail = *pphead;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  //找到了，进行尾删
  free(tail->next);
  tail->next = NULL;
}

同样的尾删也是先找尾，但与尾插的找尾有一点不同的是while循环的判断条件不相同。原因是我们删掉尾结点后，还有重要的一步是将尾结点的前一个结点（也就是新的尾结点）的next置为NULL。所以这里的tail指向的是尾结点的前一个结点。

此时tail->next->next 为NULL，所以循环结束，进行尾删。尾删只需要释放掉尾结点，并将新的尾结点的next置为NULL。