在之前我们系统的学习了数据结构中基础的概念、时间复杂度，并且用代码实现了顺序表（Contiguous_List），在对顺序表的学习和实现的文章总结中，我们提到了顺序表的优势在于可以直接访问顺序表中任意一个元素，但是劣势在于如果再头部或者中间位置进行插入或者删除操作，移动元素所产生时空开销较大。在这篇文章中我们将要进行学习的链表（Linked_List）在计算机内存中不一定连续，也可以有效的降低插入和删除元素所产生的时空开销，但相比较顺序表有着优秀时空开销的链表同样也有它的缺点，我们将对链表进行系统的学习并使用代码对他进行实现。

数据结构学习目录：

数据结构系列学习(一) - An Introduction to Data Structure

数据结构系列学习（二） - 顺序表详解（Contiguous_List）

学习：

为了避免插入和删除所产生的巨大的时空开销，线性表有另外一种表现形式——链表。链表相较于顺序表不同的是链表并不是连续存储的。

链表是由一些列不必在内存中相连的结构组成的。每一个结构均含有表元素和指向包含该元素后继元素的结构的指针。我们也把这个指针叫做Next指针。最后一个单元的Next指针指向NULL，此处的NULL为0.

特点：逻辑相邻，但是物理上并不一定相邻
因为数据元素在物理上并不要求连续，则是虚了顺序表可以随机访问的优势
单链表：用一组任意的存储单元，存储线性表的数据元素（这组数据可以连续，也可以不连续。
所以为了表示每个节点An和其后继节点An+1之间逻辑关系，每一个节点不仅仅需要保存自己的有效值（数值域），还需要保存下一个节点的地址（指针域））
单链表一般分为两种实现方式：带头节点（常用）、不带头节点（实现起来相对比较麻烦）

代码实现：

注：这里我们实现的是不带头节点的单链表。

链表的结构体设计：

在学习链表的过程中，我们已经知道链表包含数据域（data）和指针域（next），我们在设计结构体的时候也应该与这两个东西保持一致，在这里我们先重新定义范型int类型为Elem_type，所以链表中的数据域自然也就是Elemtype类型了，链表中的指针域就是链表结构体类型的指针：

typedef int Elem_type;//给出范型重命名
typedef struct Node{
    Elem_type data;//数据域(保存数据的有效值)
    struct Node* next;//指针域（保存有效节点，也就是node的节点）
}Node,*PNode;//将结构体重命名为Node，结构体类型的指针变量命名为PNode

函数功能说明：

实现链表首先要明确的就是我们即将要实现的链表能做什么，也就是链表应该具有哪些功能，下面就是链表应该具有的功能：

初始化函数（Init_List）

头部插入函数(Insert_head)

尾部插入函数(Insert_tail)

按位置插入函数(Insert_pos)

头部删除函数(Delete_head)

尾部删除函数(Delete_tail)

按位置删除函数(Delete_pos)

按值删除函数(Delete_val)

查找函数(Search)

判空函数(IsEmpty)

清空函数(Clear)

销毁函数(Destroy)

打印函数(Show)

获取有效个数（长度）函数（Get_length）

头文件（Linked_List.h）中的函数声明：

//1 初始化
void Init_List(struct Node* plist);
//2 头插
bool Insert_head(struct Node* plist,Elem_type val);
//3 尾插
bool Insert_tail(struct Node* plist,Elem_type val);
//4 按位置插
bool Insert_pos(struct Node* plist,int pos,Elem_type val);
//5 头删
bool Delete_head(struct Node* plist);
//6 尾删
bool Delete_tail(struct Node* plist);
//7 按位置删
bool Delete_pos(struct Node* plist,int pos);
//8 按值删
bool Delete_val(struct Node* plist,Elem_type val);
//9 查找 返回的是查找到的这个节点的地址
struct Node* Search(struct Node* plist,Elem_type val);
//10 判空
bool IsEmpty(struct Node* plist);
//11 清空
bool Clear(struct Node* plist);
//12 销毁
bool destroy(struct Node* plist);
//13 打印
void Show(struct Node* plist);
//14 获取有效个数（长度）
int Get_length(struct Node* plist);

源文件（Linked_List.cpp）中函数功能的具体实现：

1.初始化函数（Init_List）:

我们要初始化链表首先要做的就是将plist的指针域置为NULL：

代码：

void Init_List(struct Node* plist)
{
    //1 判断plist是否为空地址(安全性处理)
    assert(plist != NULL);
    //2 对于plist指向的头节点里面的每一个成员变量进行赋值
    plist->next = nullptr;//将链表中的头节点的next赋值为空
}

插入函数组（Insert）：?

在写插入函数组之前，我们首先应该知道对于链表中的插入操作（头部插入、尾部插入、按位置插入）到底是怎样完成的，这里我们给出一张图：

我们以上面画的链表结构图为例子，这是链表的初始状态、pnewnode代表的是待插入的新节点：

我们知道，在不带头节点的单链表中初始节点的数据域为空，且Next指针指向下一个节点的数据域，那么如果我要执行插入操作，我就操纵本来应该指向下一个节点数据域的Next指针这时指向pnewnode节点的数据域，然后再操纵pnewnode的next指针指向下一个节点的数据域，使其形成一个环形结构即可，如图：

这就是链表中插入的操作演示。?

问题：链表的插入需不需要判满？

在写头部插入函数之前，我们先来探讨一个问题，链表的插入需不需要判满？

在之前的顺序表的文章中曾经说过，顺序表是我们申请的一整块连续的内存，顺序表在存储结构和物理上都是连续的，因此在顺序表的插入和删除操作中，我们首先要做的就是判断顺序表是否已满，如果满了就进行扩容操作再进行添加或删除操作，如果没满就直接进行添加或删除操作，顺序表的添加或删除操作是将被移动元素前面或者后面的全部元素进行移动，时空开销较大。

相较于顺序表，链表本身是是线性表的另一种表现形式，链表在存储结构上连续，但在物理上是不连续的。链表中存在两个成员一个是存储数据的数据域另一个是指阵域，存储下一个节点的地址，这也就是在链表中物理空间不连续但是在存储结构上是连续的原因。链表中的节点都是一步步通过malloc函数申请而得来的，申请完节点之后，通过对新节点的数据域进行赋值，通过修改指针域的指向来达到添加新节点的目的，所以只要堆区还有足够的空间，链表就无需判满。

2.头部插入函数(Insert_head)：

我们要插入数据，就必须要在链表新节点的数据域中存放该数据，而链表的新节点是需要通过malloc函数在堆区进行申请的，所以大致的过程就能表示为：对指针做安全性处理，在堆区申请pnewnode新节点的内存空间，申请完成之后将数据存放在新节点的数据域中，修改pnewnode的next域，然后再更新plist的头节点：

代码：??

bool Insert_head(struct Node* plist,Elem_type val)
{
    //1 安全性处理
    assert(plist != NULL);
    //2 购买新节点
    struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
    // 安全性处理
    assert(pnewnode != NULL);
    //3 插入数据
    pnewnode->data = val;
    //4 插入操作 将新节点的next指向前驱节点的next
    pnewnode->next = plist->next;
    //将新节点的地址赋值给前驱节点的next域（这里的前驱节点就是原先的头节点plist）
    plist->next = pnewnode;
    return true;
}

3.尾部插入函数(Insert_tail)：

和写头部插入函数相似，我们在写尾部插入函数的时候，也需要先申请新节点，将我们要插入的值赋值给新节点的数据域，修改原先末尾节点的next，使其保存新节点的地址，然后将新节点的next赋值为空：

代码：

bool Insert_tail(struct Node* plist,Elem_type val)
{
    //1 安全性处理
    assert(plist != nullptr);
    //2 购买新节点
    struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
    assert(pnewnode != nullptr);
    pnewnode->data = val;
    //3 使用一个新指针指向链表的头部
    pnewnode->next = nullptr;
    //4 申请新指针
    struct Node *p = plist;
    //5 通过for循环找到需要插入的位置
    //注：不需要前驱的函数，例如查找、判断有效值的个数，打印函数直接使用指向头节点的for循环即可
    //但是这里我们是需要前驱的，所以使用指向头节点的for循环进行遍历
    for(;p->next!= nullptr;p=p->next){
        p->next = pnewnode;
    }
    pnewnode->next = p->next;
    p->next = pnewnode;
    return true;
}

4.按位置插入函数(Insert_pos)：

我们默认pos = 0为头插，当pos等于n时，新节点就插入在头节点之后的第n个有效节点之后，例如，我们要将地址为600的新节点插入在pos = 2处，首先我们要做的就是向堆区申请新节点（使用malloc函数），使用一个新指针指向单链表的头节点，定义循环，循环条件为i < pos，找到要插入的位置，因为我们新定义的指针p指向的是头节点，所以遍历到pos位置的p节点的next域存放的是下一个节点的地址，我们将这个地址赋值给新节点的next域，然后我们再将新节点的地址给到p指针指向节点的next域从而实现节点的添加操作。

如图：

代码：

bool Insert_pos(struct Node* plist,int pos,Elem_type val)
{
    //1 安全性处理
    assert(plist != nullptr && pos >= 0 && pos <= Get_length(plist));
    //2 购买新节点
    struct Node* pnewnode = (struct Node *)malloc(1 * sizeof(struct Node));
    //3 找到待插入位置
    struct Node *p = plist;
    for(int i = 0;i < pos;i++){
        p = p->next;
    }
    pnewnode->next = p->next;
    p->next = pnewnode;
    return true;
}

删除函数组（Delete）：?

5.头部删除函数(Delete_head)：

首先需要明确的是，我们删除的是头节点之后的第一个有效有效节点。我们第一步先对单链表进行判空，如果为空则返回为假。定义一个新指针指向待删除节点，因为我们头删的上一个节点就是头节点，本身有plist指针的存在所以我们无需再定义一个指针。然后我们进行跨越指向操作，也就是使头节点的指针直接指向头节点之后的第二个有效节点，因为我们定义的p指针指向的是第一个有效节点，所以p的next域保存的就是下一个节点的地址，我们将p的next域中保存的地址赋值给plist的next域，也就是通过使第二个有效节点的地址替换掉原先保存第一个有效节点地址的plist的next域。这样我们的跨越指向操作就可以完成了。

如图：

代码：

bool Delete_head(struct Node* plist)
{
    //1 安全性处理
    assert(plist != NULL);
    //2 判空
    if(IsEmpty(plist)){
        return false;
    }
    //3 申请一个新指针p指向待删除节点
    struct Node *p = plist->next;
    //4 申请一个新指针q指向待删除节点前面的节点（前驱）
//    struct Node *q = plist; 因为头删的上一个节点就是头节点
    //5跨越指向（让待删除节点上一个节点的next域保存下一个节点的地址）
    plist->next = p->next;
    //释放待删除节点
    free(p);
    return true;
}

6.尾部删除函数(Delete_tail)：

我们删除的是链表中的最后一个节点。尾部删除函数和头部删除的思想类似，都需要我们先定位到待删除节点。我们可以先申请一个指针p指向头节点，从头节点开始遍历至倒数第二个节点(循环条件为p的next域不为空)，我们再申请一个指针q指向头节点，从头节点开始遍历至最后一个节点(循环条件为q的next域的next域不为空或q的next域不为p)，现在我们将q的next域保存的空地址赋值给p的next域即可。

如图：

代码：

bool Delete_tail(struct Node* plist)
{
    //1 安全性处理
    assert(plist != NULL);
    //2 判空
    if(IsEmpty(plist)){
        return false;
    }
    struct Node *p = plist;
    for(;p->next != nullptr;p = p->next);//此时for循环执行结束，p指向尾节点
    struct Node *q = plist;
//    for(;q->next->next = nullptr;q = q->next);
    for(;q->next != p;q = q->next);
    q->next = p->next;
    free(p);
    return true;
}

7.按位置删除函数(Delete_pos)：

我们默认pos等于0的时候为头删，所以pos = n时，我们就删除掉头节点之后的第n个节点。首先进行判空，如果链表为空则返回为假。定义一个新指针q指向头节点，从头节点开始遍历找到待删除节点的上一个节点，用指针保存这个节点的next域（这里的next域就相当于是待删除节点的地址），再定义一个新指针p指向头节点，将待删除节点的地址赋值给p，此时p的next域就相当于是待删除节点的下一个节点了，然后我们再将p的next域赋值给q的next域，这样我们就完成跨越指向了。

如图：代码：

bool Delete_pos(struct Node* plist,int pos)
{
    //1 安全性处理
    assert(plist != NULL && pos >= 0 && pos != Get_length(plist));
    if(IsEmpty(plist)){
        return false;
    }
    struct Node *q = plist;
    for(int i = 0;i < pos;i++){
        q = q->next;
    }
    struct Node *p = plist;
    p = q->next;
    q->next = p->next;
    free(q);
    return true;
}

8.按值删除函数(Delete_val)：

首先进行判空操作，如果单链表为空则返回为假，定义新指针p保存搜索函数返回的地址，如果搜索函数没找到返回的是空地址也返回为假。定义新指针q指向头节点，开始循环遍历直到找到待删除数据的那个节点，此时p的next域就是待删除节点后面一个节点的地址，将这个节点的地址赋值给q的next域，这样，我们就实现了跨越指向。

代码：

bool Delete_val(struct Node* plist,Elem_type val)
{
    //1 安全性处理
    assert(plist != nullptr);
    if(IsEmpty(plist)){
        return false;
    }
    struct Node *p = Search(plist,val);
    if(p == nullptr){
        return false;
    }
    struct Node *q = plist;
    for(; q->next != p;q = q->next);
    q->next = p->next;
    free(p);
    return true;
}

函数中循环的不同：

我们在之前写插入和删除函数的时候，如果是按位置插入删除或者按值进行删除的话需要通过循环来找到目标位置，而且在插入或者删除函数中的操作通常都是需要使用到节点的前驱的，所以在定义新指针的时候我们通常使用新指针保存的是头节点的地址。但是在查找函数中，我们并不需要使用节点的前驱，我们只需要读取节点的数据域即可，所以我们就使用新定义的指针保存第一个有效节点即可。

所以在插入删除函数组和查找打印函数组中使用到的循环是不一样的。

前者的for循环是需要前驱的，用代码来表示也就是：

struct Node *p = plist;//plist为头节点的地址
for(struct Node *p;p->next != nullptr;p = p->next)

后者的for循环是不需要前驱的，用代码来表示也就是：

struct Node *p = plist -> next;
for(struct Node *p;p != nullptr;p = p->next)

9.查找函数(Search)：

首先我们对单链表进行判空，如果为空则返回为假，使用一个新指针指向单链表头节点后的第一个有效节点，定义循环，循环条件为p不为空（因为最后一个节点的next为空），当p指向节点的数据域中的值和要查找的值相吻合时，返回p的地址，也就是要查找的值的地址。

代码：

struct Node* Search(struct Node* plist,Elem_type val)
{
    //1 安全性处理
    assert(plist != NULL);
    if(IsEmpty(plist)){
        return NULL;
    }
    for(struct Node *p = plist ->next;p != nullptr;p = p->next){
        if(p->data == val){
            return p;
        }
    }
    return nullptr;
}

10.判空函数(IsEmpty)：

判空函数很好理解，我们知道单链表中的头节点中的数据域是不存放任何值的，next存放了下一个节点的地址，那么如果单链表中的头节点的next域为空的话，也就代表着单链表为空了。

代码：?

bool IsEmpty(struct Node* plist)
{
    //2 当头节点的next指针指向空，则代表单链表为空
    return plist->next == nullptr;
}

11.清空函数(Clear)：

在链表中，清空和销毁的概念相似，我们可以在清空函数中调用销毁函数。

代码：

bool Clear(struct Node* plist)
{
    destroy(plist);
    return true;
}

12.销毁函数(Destroy)：

这里我们实现销毁函数的方式为无限头删，直到它满足判空函数为止，再返回真。

bool destroy(struct Node* plist)
{
    //1 安全性处理
    while(!IsEmpty(plist)){
        Delete_head(plist);
    }
    return true;
}

13.打印函数(Show)：

如果我们需要打印链表中的有效值，首先我们定义一个新指针指向头节点之后的第一个有效节点，定义循环，循环条件为p不为空，每循环至一个节点就将这个节点的数据域中的值打印。

代码：

void Show(struct Node* plist)
{
    //1 安全性处理
    assert(plist != NULL);
    //2 定义新指针指向链表
    struct Node *p = plist->next;
    for(;p!= nullptr;p = p->next){
        printf("%3d", p->data);
    }
}

14.获取长度函数(Get_length)：

int Get_length(struct Node* plist)
{
    assert(plist != nullptr);
    int count = 0;
    struct Node *p = plist->next;
    for(;p!= nullptr;p = p->next){
        count++;
    }
    return count;
}

测试：?

测试插入函数组：

测试初始化函数、按位置插函数：

我们创建一个名为head链表，并创建10个空间对它进行数值的插入（1～10）：

#include<cstdio>
#include<cassert>
#include "Linked_List.h"
int main()
{
    struct Node head;
    Init_List(&head);//头节点
    for(int i = 0;i < 10;i++){
        Insert_pos(&head,i,i + 1);
    }
    printf("原始数据为：");
    Show(&head);
    return 0;
}

运行结果：

测试头插函数：

Insert_head(&head,100);
printf("\n变更后的数据为：");
Show(&head);

运行结果：?

测试尾插函数：

    Insert_tail(&head,100);
    printf("\n变更后的数据为：");
    Show(&head);

运行结果：

测试删除函数组：

测试头删函数：

    Delete_head(&head);
    printf("\n变更后的数据为：");
    Show(&head);

运行结果：

测试尾删函数：?

    Delete_tail(&head);
    printf("\n变更后的数据为：");
    Show(&head);

运行结果：

测试按位置删函数：?

    Delete_pos(&head,2);
    printf("\n变更后的数据为：");
    Show(&head);

测试按值删函数：

    Delete_val(&head,2);
    printf("\n变更后的数据为：");
    Show(&head);

运行结果：

测试清空函数：

    Clear(&head);
    printf("\n变更后的数据为：");
    Show(&head);

运行结果：?

?测试销毁函数：

    destroy(&head);
    printf("\n变更后的数据为：");
    Show(&head);

运行结果：

测试获取长度函数：?

    int len = Get_length(&head);
    printf("\n链表的有效长度为：%d\n",len);

运行结果：

测试查找函数：

假设我们在链表中要查找的值为3：

    struct Node *p = Search(&head,3);
    printf("\n元素在链表中的地址为：%p\n",p);

运行结果：

但如果我们查找一个原先链表中没有的100：

    struct Node *p = Search(&head,100);
    printf("\n元素在链表中的地址为：%p\n",p);

如图，返回值是我们原先设定好的空值(nullptr)

总结：?

链表是线性表的另外一种表现形式，相较于顺序表而言有着明显的优点和缺点，当我们使用这两种数据结构的时候应该理解他们的原理，并按照他们的特性在不同的场景里面进行区分和使用。链表比顺序表更加抽象，它也是我们对内存结构的准确利用，了解和熟练地使用链表这种数据结构是我们作为程序员必须拥有的技能，后续带头节点的单链表、循环链表、双向链表我会持续跟进。