如何实现单链表的基本操作？

本文共计4288个文字，预计阅读时间需要18分钟。

目录一. 链表的基本概念和结构二. 链表的分类三. 单链表的基本操作 1. 创建一个节点 2. 打印链表 3. 尾部插入 4. 头部插入 5. 尾部删除 6. 头部删除 7. 查找 8. 指定位插入 9. 指定位删除 10. 销毁链表一. 链表的基本概念和结构

目录

一.链表的基本概念和结构

二.链表的分类

三.单链表的基本操作

1.创建一个节点

2.打印

3.尾插

4.头插

5.尾删

6.头删

7.查找

8.指定位置插入

9.指定位置删除

10.销毁

---

一.链表的基本概念和结构

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

结构：链表是有各个节点通过指针连接在一起的，每个节点分为数据域和指针域，每个节点的指针域指向下一个节点的地址，最后一个节点的指针域为空。

逻辑结构如下图所示

物理结构：逻辑结构看起来是连续的，但是由于链表的节点是在堆上开辟的，地址可能连续，也可能不连续

二.链表的分类

1.单向和双向：

2.带头和不带头

3.循环和不循环

通过上面三种分类我们可以得知，组合起来链表总共有8中结构，但是我们经常使用的不带头无循环单链表和带头双向循环链表，此篇文章暂时只讨论第一种结构的基本操作

三.单链表的基本操作

单链表的基本操作有尾插、尾删、头插、头删、指定位置插入、指定位置删除、查找、销毁等操作，下面我们来实现这些操作

// 1、无头+单向+非循环链表增删查改实现

typedef int SLTDateType;

typedef struct SListNode

{

SLTDateType data;

struct SListNode* next;

}SListNode;

// 动态申请一个结点

SListNode* BuySListNode(SLTDateType x);

// 单链表打印

void SListPrint(SListNode* plist);

// 单链表尾插

void SListPushBack(SListNode** pplist, SLTDateType x);

// 单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x);

// 单链表的尾删

void SListPopBack(SListNode** pplist);

// 单链表头删

void SListPopFront(SListNode** pplist);

// 单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x);

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

void SListInsertAfter(SListNode* pos, SLTDateType x);

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

void SListEraseAfter(SListNode* pos);

1.创建一个节点

链表和顺序表一样，依然是使用结构体来实现，然后利用动态内存管理函数开辟相应的空间，结构体含有一个数据变量和指针变量

SListNode* BuySListNode(SLTDateType x)//传入数据变量 { SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));//开辟一个节点 if (newnode == NULL)//检查是否开辟成功 { perror("SLTBynode error"); return NULL; } newnode->data = x;//将数据变量赋给data newnode->next = NULL;//指针变量初始化为空指针 return newnode;//返回开辟的节点地址 }

2.打印

打印链表和打印顺序表思想相似，从前到后一次遍历每个节点并打印数据变量，链表访问下一个节点需要找到下一个节点的地址，而下一个的地址存储在当前指针指向的节点的指针域，所以要使指针的值改为当前节点的指针域，此时指针便指向了下一个节点了，即cur=cur->next,使指针指向下一个节点

void SListPrint(SListNode* plist) { SListNode* cur = plist;//定义一个临时指针进行遍历，最好不要动头结点 while (cur)//指针进行遍历，直到指针指向空即遍历结束 { printf("%d->", cur->data);//打印链表数据变量 cur = cur->next;//指针指向下一个节点 } printf("NULL\n"); }

3.尾插

尾插即将新节点插入到链表的尾部，插入过程：先调用开辟节点的函数开辟一个新节点，如果链表为空，则直接将头指针指向新节点，如果非空，链表的最后一个节点指针域通常为空，所以我们需要一个临时指针找到链表的最后一个节点，然后将最后的节点指针域指向新节点，如图所示

void SListPushBack(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x);//创建一个新节点 if (*pplist == NULL) { *pplist = newnode;//如果链表是空则直接将头结点指向新节点 } else { SListNode* cur = *pplist;//定义一个临时指针，遍历找到尾节点 while (cur->next)//直到最后一个节点结束 { cur = cur->next;//指针往后走一个节点 } cur->next = newnode;//将尾节点的指针域指向新节点 } }

4.头插

链表的头插即将新节点插入到链表最前面，成为链表的第一个节点，插入过程：先调用开辟节点的函数创建一个新节点，若链表为空，则直接将头结点直接指向新节点，若非空，将新节点的指针域指向第一个节点，然后将链表的头指针指向新节点，如图所示

void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x);//开辟新节点 if (*pplist == NULL) { *pplist = newnode;//若链表为空表，则直接将头指针指向新节点 } else { newnode->next = *pplist;//新节点的指针域指向链表 *pplist = newnode;//头指针指向新向新节点 } }

5.尾删

链表的尾删即删去链表的最后一个节点，删除过程：先判断链表是否为空，为空则不能删除，我们用assert断言函数检查链表是否为空表，若非空，如果只有一个节点，我们只需要删除这个节点然后将头指针置空，如果不止一个节点，我们需要找到最后一个节点的前面的一个几点，然后通过前一个的节点指针域释放最后一个节点，此时前一个节点变成新的最后一个节点，因此我们需要将其指针域置空，如图所示

void SListPopBack(SListNode** pplist) { assert(*pplist);//判断链表是否为空 SListNode* cur = *pplist;//定义临时指针,用来找到最后一个节点的前一个节点 if ((*pplist)->next == NULL)//判断是否只有一个节点 { free(*pplist);//删除这个节点 *pplist = NULL;//头指针置空 } else { while (cur->next->next)//遍历到最后一个节点的前一个节点 { cur = cur->next; } free(cur->next);//删除最后一个元素 cur->next = NULL;//前一个节点已成新的最后一个元素，指针域置空 } }

6.头删

链表的头删即删去链表的第一个节点，删除过程：先判断链表是否为空，为空则不能删除直接退出函数，如果只有一个节点，则直接将该节点删除，然后将头指针置空，如果不止一个节点，则需要一个临时指针指向第二个节点，通过头指针将第一个元素删除，此时第二个节点成为新的第一个节点，然后将头指针指向临时指针，即头指针指向新的第一个节点，如图所示

void SListPopFront(SListNode** pplist) { assert(*pplist);//判断链表是否为空 SListNode* cur = *pplist;//定义临时指针指向第二个节点 if ((*pplist)->next == NULL)//判断是否只有一个节点 { free(*pplist);//删除该节点 *pplist = NULL;//头指针置空 } else { cur= cur->next;//临时指针指向第二个节点 free(*pplist);//删除第一个节点 *pplist = cur;//头指针指向第二个节点 } }

7.查找

链表的查找和顺序表思想相似，从前往后遍历每个节点的数据与查找的数据相比较，相等则返回该节点的地址，找不到则返回NULL

SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist;//定义临时指针遍历链表 while (cur)//临时指针为空则遍历结束 { if (cur->data == x)//节点的数据和查找的数据比较 return cur;//返回该节点的地址 cur = cur->next;//临时指针往后走一个节点 } return NULL;//没有找到则返回空 }

8.指定位置插入

链表指定位置一般是在指定位置后面插入元素，插入元素过程：先判断位置是否合法，在创建一个新节点，然后通过给定位置的next找到后面一个节点，然后将新节点的指针域指向后面一个节点，然后指定位置指针域指向新节点，如图所示

特别值得注意的是，图中的1和2顺序不能倒过来，如果倒过来，即先让指定位置指针域先指向新指针，就找不到指定位置的后一个节点了

void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos);//判断位置是否合法 SListNode*newnode=BuySListNode(x);//创建新节点 newnode->next = pos->next;//新节点指针域指向指定位置后一个节点 pos->next = newnode;//指定位置指针域指向新节点 }

9.指定位置删除

链表的指定位置删除一般是删除指定位置之后的节点，删除过程：先判断位置是否合法，然后需要定义一个临时指针找到给定位置的后一个节点，然后将指定位置指针域指向要删除的节点后一个节点，然后再删除指定位置后一个节点，如图所示

void SListEraseAfter(SListNode* pos) { assert(pos&&pos->next);//判断位置是否合法 SListNode* cur = pos->next;//定义临时指针指向指定位置的后一个节点 pos->next = pos->next->next;//让指定位置指针域指向要删除节点的后一个接地那 free(cur);//删除指定位置后一个节点 }

10.销毁

单链表的销毁需要两个临时指针，第一个指针指向前面一个元素，第二个指针指向后一个元素，依次从前往后遍历，删除掉第一个指针指向的节点，然后第一个指针指向第二个指针指向的节点，第二个指针往后走一个节点，然后继续删除掉第一个指针指向的节点，知道第二指针指向为空，此时第一个指针指向最后一个节点，再继续删除掉第一个指针指向的节点，即全部删除完成

void SListDestroy(SListNode* plist) { SListNode* cur = plist;//定义第一个临时指针，指向相对前一个节点 SListNode* next = plist;//定义第二个临时指针，指向相对前一个节点 while (next)//遍历，直到第二个节点指向空 { cur = next; next = next->next; free(cur); } }

以上就是单链表的一些基本操作，下面看全部代码：

SList.c

#include"SList.h" SListNode* BuySListNode(SLTDateType x)//传入数据变量 { SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));//开辟一个节点 if (newnode == NULL)//检查是否开辟成功 { perror("SLTBynode error"); return NULL; } newnode->data = x;//将数据变量赋给data newnode->next = NULL;//指针变量初始化为空指针 return newnode;//返回开辟的节点地址 } void SListPrint(SListNode* plist) { SListNode* cur = plist;//定义一个临时指针进行遍历，最好不要动头结点 while (cur)//指针进行遍历，直到指针指向空即遍历结束 { printf("%d->", cur->data);//打印链表数据变量 cur = cur->next;//指针指向下一个节点 } printf("NULL\n"); } void SListPushBack(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x);//创建一个新节点 if (*pplist == NULL) { *pplist = newnode;//如果链表是空则直接将头结点指向新节点 } else { SListNode* cur = *pplist;//定义一个临时指针，遍历找到尾节点 while (cur->next)//直到最后一个节点结束 { cur = cur->next;//指针往后走一个节点 } cur->next = newnode;//将尾节点的指针域指向新节点 } } void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x);//开辟新节点 if (*pplist == NULL) { *pplist = newnode;//若链表为空表，则直接将头指针指向新节点 } else { newnode->next = *pplist;//新节点的指针域指向链表 *pplist = newnode;//头指针指向新向新节点 } } void SListPopBack(SListNode** pplist) { assert(*pplist);//判断链表是否为空 SListNode* cur = *pplist;//定义临时指针,用来找到最后一个节点的前一个节点 if ((*pplist)->next == NULL)//判断是否只有一个节点 { free(*pplist);//删除这个节点 *pplist = NULL;//头指针置空 } else { while (cur->next->next)//遍历到最后一个节点的前一个节点 { cur = cur->next; } free(cur->next);//删除最后一个元素 cur->next = NULL;//前一个节点已成新的最后一个元素，指针域置空 } } void SListPopFront(SListNode** pplist) { assert(*pplist);//判断链表是否为空 SListNode* cur = *pplist;//定义临时指针指向第二个节点 if ((*pplist)->next == NULL)//判断是否只有一个节点 { free(*pplist);//删除该节点 *pplist = NULL;//头指针置空 } else { cur= cur->next;//临时指针指向第二个节点 free(*pplist);//删除第一个节点 *pplist = cur;//头指针指向第二个节点 } } SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist;//定义临时指针遍历链表 while (cur)//临时指针为空则遍历结束 { if (cur->data == x)//节点的数据和查找的数据比较 return cur;//返回该节点的地址 cur = cur->next;//临时指针往后走一个节点 } return NULL;//没有找到则返回空 } void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos);//判断位置是否合法 SListNode*newnode=BuySListNode(x);//创建新节点 newnode->next = pos->next;//新节点指针域指向指定位置后一个节点 pos->next = newnode;//指定位置指针域指向新节点 } void SListEraseAfter(SListNode* pos) { assert(pos&&pos->next);//判断位置是否合法 SListNode* cur = pos->next;//定义临时指针指向指定位置的后一个节点 pos->next = pos->next->next;//让指定位置指针域指向要删除节点的后一个接地那 free(cur);//删除指定位置后一个节点 } void SListDestroy(SListNode* plist) { SListNode* cur = plist;//定义第一个临时指针，指向相对前一个节点 SListNode* next = plist;//定义第二个临时指针，指向相对前一个节点 while (next)//遍历，直到第二个节点指向空 { cur = next; next = next->next; free(cur); } }

SList.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDateType; typedef struct SLT { SLTDateType data; struct SLT* next; }SListNode; //创建一个节点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode* plist);

test.c

#include"SList.h" void TestSList() { SListNode* node = NULL; SListPushBack(&node, 1); SListPushBack(&node, 2); SListPushBack(&node, 3); SListPushBack(&node, 4); SListPushBack(&node, 5); SListPushFront(&node, 0); SListPopBack(&node); SListPopFront(&node); SListNode* pos=SListFind(node, 3); SListPrint(node); //SListInsertAfter(pos,100); //SListPrint(node); SListEraseAfter(pos); SListPrint(node); SListDestroy(node); } int main() { TestSList(); return 0; }

输出结果：

写是为了不停地思考，创作是为了更好地思考，种一棵树最好的时间是十年前，其次是现在。单链表就暂时学到这啦，如果对您有所帮助，欢迎一键三连~