目录

      一、什么是链表

      二、单链表的实现

            1、动态申请一个结点

            2、单链表打印

            3、单链表尾插

            4、单链表的尾删

            5、单链表的头插

            6、单链表头删

            7、单链表查找

            8、单链表在pos位置之后插入x

            9、单链表删除pos位置之后的值

            10、单链表在pos位置之前插入x

            11、单链表删除pos位置的值

            12、销毁链表

      三、源代码

            1、SList.h

            2、SList.c

            3、test.c

一、什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

单链表的声明如下：

//声明单链表
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

链表的逻辑结构：

链表的物理结构：

注意：

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

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

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

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：

每个链表都是由一节节的链结组成的，我们称之为节点。其中，每一个节点都是由两部分组成的，存储数据的部分叫做数据域，存储地址的部分叫做指针域。指向第一个节点的指针称之为头指针。

二、单链表的实现

  1、动态申请一个结点 

在链表中插入一个数据，首先需要先动态申请一个结点，并将该结点的数值域与指针域进行赋值，指针域都设置为NULL。

//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

  2、单链表打印

 在这里我的思路是用while循环将链表遍历一遍，从首个结点开始移动，直到NULL结束。

//打印链表
void SLTPprint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

  3、单链表尾插

尾插就需要我们先动态开辟一个新的节点 。然后让前面的指针指向新的节点。但是要分两种情况如下图所示：

因为链表为NULL时，plist指针指向的是空，此时不能进行解引用操作，所以如果为NULL时，直接进行赋值就行。当链表不为空时，直接在后面进行尾插。 

注意：

在这里使用的是二级指针，因为需要改变结构体里面的数值，而头指针是一个结构体类型的指针，而指针也是一种变量。假设我们用的是一级指针，当链表为空，我们进行尾插的时候，我们会将头指针内的数据改为新节点的地址。我们可以找到，一级指针的传递方式不会引起实参的变化。因此，当此函数结束后，我们的头指针依旧是空。因此，我们这里需要传入的是二级指针，从而实现地址传递。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;//找尾while (tail->next){tail = tail->next;}tail->next = newnode;}
}

  4、单链表的尾删

在这里首先要要声明一下，保证链表不为空，然后再分两种情况：(1)如果链表长度大于1时，只需要将倒是第二个节点的指针域设置为空指针，并且将最后一个节点释放掉。(2)如果链表长度为1时，只需将头指针置空，第一个节点释放掉就行。

//单链表尾删
void SLTPopBack(SLTNode** pphead)
{//暴力的检查assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}	
}

  5、单链表的头插

头插也是先要开辟一个新的节点，然后直接让新节点的next链接到头节点上，最后重新更新一下头节点。

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

  6、单链表头删

头删首先还是要声明一下，保证链表不为空，然后保存头指针指向指针域中所对的地址空间，最后释放头节点即可。

//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

  7、单链表查找

 直接用while循环将链表遍历一遍。注意返回值返回的是空指针或者所查元素的地址。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}elsecur = cur->next;}return NULL;
}

  8、单链表在pos位置之后插入x

在pos位置之后插入x时，pos位置所对的节点的指针域中就记录了后面的节点位置。因此可以直接插入x所对应的节点。

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

  9、单链表删除pos位置之后的值

在删除pos位置之后的节点时，如果pos->next为空时，说明pos位置就是最后一个节点，它的后面已经没有节点了，所以直接返回即可，如果pos->next不为空时，要保存住这个位置，然后重新链接pos->next = pos->next->next(就相当于下面代码中pos->next = nextNode->next)，最后释放pos->next。

//删除pos之后的值
void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* nextNode = pos->next;pos->next = nextNode->next;free(nextNode);}
}

  10、单链表在pos位置之前插入x

在pos位置前面插入新的节点，分两种情况：(1)如果pos的位置就是头节点时，就相当于头插。(2)如果pos位置不是头节点时，要找到pos位置原链表的前方的节点。然后让该节点指向所插入的节点，然后让所插入的节点指向pos所对的节点。

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}

  11、单链表删除pos位置的值

删除pos位置的节点，分两种情况：(1)如果pos的位置就是头节点时，就相当于头删。(2)如果pos的位置不是头节点时，先保存pos位置后面的节点，然后让该节点链接pos位置之前的节点，最后再释放掉pos位置的节点。

//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

  12、销毁链表

销毁链表的时候，我们不能简单只释放头指针。这样是没有将空间完全释放掉的，这只是释放了头节点。所以可以设置一个指针cur，让它用while循环将链表从头到尾都释放一遍，最后将头指针设置为空。一定要将头指针设置为空指针！否则会出现野指针的问题！

//销毁
void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

三、源代码

  1、SList.h

#pragma once
#include 
#include 
#include typedef int SLTDataType;//声明单链表
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x);
//创建循环节点
SLTNode* CreateSList(int n);
//打印链表
void SLTPprint(SLTNode* phead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//尾插尾删
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
//头插头删
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的值
void SLTEraseAfter(SLTNode* pos);//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);//销毁
void SLTDestroy(SLTNode** pphead);

  2、SList.c

#include "SList.h"//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//创建循环节点
SLTNode* CreateSList(int n)
{SLTNode* phead = NULL, * ptail = NULL;for (int i = 0; i < n; i++){SLTNode* newnode = BuySLTNode(i);if (phead == NULL){ptail = phead = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}//打印链表
void SLTPprint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){//printf("[%d | %p]->", cur->data, cur->next);printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;//找尾while (tail->next){tail = tail->next;}tail->next = newnode;}
}
void SLTPopBack(SLTNode** pphead)
{//暴力的检查assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}	
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}elsecur = cur->next;}return NULL;
}//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}//删除pos之后的值
void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* nextNode = pos->next;pos->next = nextNode->next;free(nextNode);}
}//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}//销毁
void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

  3、test.c

TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPprint(plist);SLTPopBack(&plist);SLTPprint(plist);SLTPushFront(&plist, 100);SLTPushFront(&plist, 200);SLTPprint(plist);SLTPopFront(&plist);SLTPprint(plist);SLTNode* p = SLTFind(plist, 2);SLTInsertAfter(p, 30);SLTPprint(plist);p = SLTFind(plist, 1);SLTEraseAfter(p);SLTPprint(plist);SLTDestroy(&plist);}
int main()
{TestSList1();return 0;}

本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。

  老铁们，记着点赞加关注哦!!!