本文共 6713 字，大约阅读时间需要 22 分钟。

在上两篇文章中，我们介绍了基于静态数组和动态数组的顺序表，顺序表频繁查询而插入删除动作少的情况下，顺序表也适用于进行尾插的时候，因为相对于链表而言，顺序表在进行尾插时，顺序表不需要通过遍历来找到最后一个插入点，比较而言，顺序表尾插效率高。

但是，在进行头插和中插时，顺序表需要将插入元素位置之后的元素整体后移才能插入数据，这样做在有大量插入删除场景下即为麻烦且效率低，因此，提出了链表的思想。而链表在头插或者中插时，只需要创建一个新节点，然后将节点链入所插入位置即可。

链表概述

链表是一种常见的数据结构。数组可以存放数据，但是数组存放数据时必须提前指定数组包含元素个数，即数组长度。但是数组保存数据的缺点在于如果要保存元素大于数组大小时，则不能将所有内容保存入数组，而当要保存元素远小于数组大小时，又造成了空间的浪费。而链表其存储元素个数不受限定，当进行添加元素时，存储个数随之增加。

链表是一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称存储单元为一个节点。

typedef int DataType;typedef int DataType;typedef struct LinkNode{    DataType _data;//当前节点保存数据    struct LinkNode* _pNext;//指向链表中下一结点的指针}Node;

如下图，为链表结构示意图：

在链表中有一个头指针变量，图中head表示的就是头指针，这个指针变量保存一个地址。从图中的箭头可以看到该地址为一个变量的地址，也就是说头指针指向一个变量。这个变量称为元素，在链表中每一个元素包括两个部分：数据部分和指针部分。数据部分用来存放元素所包含的数据，而指针部分用来指向下一个元素。最后一个元素指针指向NULL，表示指向的地址为空。 从图可以看到，head头结点指向第一个元素，第一个元素中的指针又指向第二个元素，第二个元素的指针又指向第三个元素的地址，第三个元素的指针指向第四个元素，第四个元素的指针就指向为空。

链表的分类

• 单链表
• 双向链表
• 双向循环链表

需要注意的是，上述三种链表都有两种形式，分别为带头结点和不带头结点。

C语言实现不带头节点的单链表

具体代码实现如下：

#pragma once #include 
   
    #include 
    
     #include 
     
      /***************************************///链表的定义typedef int DataType;typedef struct LinkNode{    DataType _data;//当前节点保存数据    struct LinkNode* _pNext;//指向链表中下一结点的指针}Node;/***************************************///链表的初始化void LinkListInit(Node** pHead);//创建新结点Node* LinkListCreatNode(DataType data);//销毁结点void LinkListIDestroyNode(Node** pHead);//遍历打印链表void LinkListPrint(Node** pHead);//尾插元素void LinkListPushBack(Node** pHead, DataType data);//尾删元素void LinkListPopBack(Node** pHead);//头插元素void LinkListPushFront(Node** pHead, DataType data);//头删元素void LinkListPopFront(Node** pHead);//查找元素size_t LinkListFind(Node** pHead, DataType data);//任意位置的插入void LinkListInsert(Node** pHead, DataType data, Node* pos);//任意位置的删除void LinkListErase(Node** pHead, Node* pos);//求单链表长度size_t LinkListSize(Node** pHead);//销毁一个单链表void LinkListDestroy(Node** pHead);//判空size_t LinkListEmpty(Node** pHead);/***************************************///链表的初始化void LinkListInit(Node** pHead){    //考虑指针为空    assert(pHead);    *pHead = NULL;}//创建新结点Node* LinkListCreatNode(DataType data){    Node* pNewNode = (Node*)malloc(sizeof(Node));    assert(pNewNode);    pNewNode->_data = data;    pNewNode->_pNext = NULL;    return pNewNode;}//销毁结点void LinkListIDestroyNode(Node** pHead){    //释放该结点，并将头指针指向NULL，防止出现野指针    free(pHead);    *pHead = NULL;}//遍历打印链表void LinkListPrint(Node** pHead){    Node* pCur = *pHead;    for (pCur; pCur != NULL; pCur = pCur->_pNext)    {        printf("%d--->", pCur->_data);    }    printf("NULL\n");}//尾插元素void LinkListPushBack(Node** pHead, DataType data){    Node* NewNode = LinkListCreatNode(data);    assert(pHead);    //如果链表为空，则直接让头指针指向新申请的节点即可    if (*pHead == NULL)    {        *pHead = NewNode;        return;    }    //否则从头开始遍历链表，直到当前节点的指针域指向NULL，然后让当前节    //点的指针域指向新申请的节点即可    Node* pTail = *pHead;    while (pTail->_pNext)    {        pTail = pTail->_pNext;    }    pTail->_pNext = NewNode;}//尾删元素void LinkListPopBack(Node** pHead){    assert(pHead);    if (*pHead == NULL)    {        printf("链表为空，无法删除！\n");        return;    }    //如果当前只有一个结点，则释放该结点,    //并将头指针指向NULL，防止出现野指针--相当于销毁结点    if ((*pHead)->_pNext == NULL)    {        free(pHead);        *pHead = NULL;    }    //定义两个指针，依次向后走    //pTail不为空时，将其前一个结点指针pPreTail赋给pTail    //当pTail为空时，释放pTail，pPreTail指向NULL    Node* pTail = *pHead;    Node* pPreTail = NULL;    while (pTail->_pNext)    {        pPreTail = pTail;        pTail = pTail->_pNext;    }    free(pTail);    pPreTail->_pNext = NULL;}//头插元素void LinkListPushFront(Node** pHead, DataType data){    assert(pHead);    Node* NewNode = LinkListCreatNode(data);    NewNode->_pNext= (*pHead);    *pHead = NewNode;}//头删元素void LinkListPopFront(Node** pHead){    Node* pDel = NULL;    assert(pHead);    //考虑链表为空情况    if ((*pHead) == NULL)    {        printf("链表为空！无法删除！\n");        return;    }    pDel = *pHead;    *pHead = pDel->_pNext;    free(pDel);}//查找元素size_t LinkListFind(Node** pHead, DataType data){    assert(pHead);    //考虑链表为空的情况    if (*pHead == NULL)    {        printf("链表为空！无法查找！\n");        return -1;    }    Node* pFind = *pHead;    while (pFind && pFind->_data != data)        pFind = pFind->_pNext;    if (pFind != NULL)    {        printf("找到了数据%d\n", pFind->_data);        return 1;    }       else        printf("没有找到数据%d\n",data);    return -1;}//任意位置的插入void LinkListInsert(Node** pHead, Node* pos, DataType data){    assert(pHead);    //考虑pos位置的合法性    assert(pos);    //考虑空链表情况    Node* pNewNode = LinkListCreatNode(data);    if (*pHead == NULL)    {        *pHead = pNewNode;        return;    }    if (pos == NULL)    {        LinkListPushBack(pHead, data);        return;    }    if (pos == *pHead)    {        LinkListPushFront(pHead, data);        return;    }    Node* pCur = *pHead;    while (pCur->_pNext != NULL)    {        if (pCur->_pNext == pos)        {            pNewNode->_pNext = pos;            pCur->_pNext = pNewNode;        }        pCur = pCur->_pNext;    }    return;}//任意位置的删除void LinkListErase(Node** pHead, Node* pos){    assert(pHead);    assert(pos);    //考虑链表为空    if ((*pHead) == NULL)    {        printf("链表为空！无法删除！\n");        return;    }    if (pos == (*pHead))    {        LinkListPopFront(pHead);        return;    }    Node* pE = *pHead;    while ( pE != NULL)    {        if (pE->_pNext != NULL)        {            pE->_pNext = pos->_pNext;            LinkListIDestroyNode(pos);            return;        }        pE = pE->_pNext;        }    return;}//求单链表长度size_t LinkListSize(Node** pHead){    assert(pHead);    Node* pSize = *pHead;    size_t count = 0;    while (pSize != NULL)    {        pSize = pSize->_pNext;        count++;    }    printf("链表长度为%d\n",count);    return count;}//销毁一个单链表void LinkListDestroy(Node** pHead){    assert(pHead);    Node* pDpre = NULL;    Node* pD = *pHead;    //定义两个指针同时向链尾走，pD不为空时，用pDpre标记pD    //pD不断向后移同时释放pDpre，直至将整个链表结点全部释放    while (pD)    {        pDpre = pD;        pD = pD->_pNext;        free(pDpre);    }    //切记将头指针指向空，不然将变成野指针    *pHead = NULL;}//判空size_t LinkListEmpty(Node** pHead){    assert(pHead);    return ((*pHead) == NULL);}/***************************************///测试部分void LinkListTest(){    Node* p;    LinkListInit(&p);    LinkListPushBack(&p, 1);    LinkListPushBack(&p, 2);    LinkListPushBack(&p, 3);    LinkListPushBack(&p, 4);    LinkListPushBack(&p, 5);    LinkListPrint(&p);    LinkListPopBack(&p);    LinkListPrint(&p);    LinkListPushFront(&p, 5);    LinkListPushFront(&p, 6);    LinkListPrint(&p);    LinkListPopFront(&p);     LinkListPopFront(&p);    LinkListPrint(&p);    LinkListFind(&p, 2);    LinkListFind(&p, 5);    LinkListSize(&p);    LinkListInsert(&p,p,8);    LinkListPrint(&p);    //LinkListErase(&p,2);    //LinkListPrint(&p);}