1. Toy模板网首页
  2. > Toy博客

单链表的基本操作

10月前 作者：蛋超饭不要加蛋 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了单链表的基本操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

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

二.链表的分类

三.单链表的基本操作 

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;
}

输出结果：

单链表的基本操作,数据结构和算法,链表,数据结构

        写是为了不停地思考，创作是为了更好地思考，种一棵树最好的时间是十年前，其次是现在。单链表就暂时学到这啦，如果对您有所帮助，欢迎一键三连~ 文章来源地址https://www.toymoban.com/news/detail-814914.html

到了这里，关于单链表的基本操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

    数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

      头文件和源文件分开有很多好处：可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性，同时也可以使代码结构更清晰，方便代码的管理和维护。 LinkList.h test.cpp                  （下面所有函数都默认在类中实现）   我们以

    2024年02月07日
    浏览(58)
  • 数据结构——单链表基本操作实现 (c++)

    数据结构——单链表基本操作实现 (c++)

    单链表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这里存储单元可以是连续的，也可以是不连续的），为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系，除了存储信息本身外还要存储一个指示其直接后继的信息（地址）. 这两部分信

    2024年02月03日
    浏览(68)
  • 【数据结构】单链表基本操作：查找、插入、删除、创建

    【数据结构】单链表基本操作：查找、插入、删除、创建

     链表由结点组成，结点由数据域和指针域组成。其中，数据域存放的就是数据元素，指针域存放下一个结点的地址。数据元素可以只有一个，也可以有多个不同类型的数据元素，甚至是数组。下图和代码来自《C Primer Plus》，该链表每个节结点同时含char类型和int类型。 ​​

    2024年02月02日
    浏览(64)

  • 数据结构——单链表上基本操作的实现

    1.按位序插入（带头结点） ： ==ListInsert(L, i, e): ==在表L 中的第 i 个位置上插入指定元素 e = 找到第 i-1 个结点 ( 前驱结点 ) ，将新结点 插入其后；其中头结点可以看作第 0 个结点，故 i=1 时也适用。 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; // 在第 i 个位置插入

    2024年01月21日
    浏览(57)

  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 【数据结构】C语言实现双链表的基本操作

    【数据结构】C语言实现双链表的基本操作

    大家好，很高兴又和大家见面啦！！！ 经过前面几个篇章的内容分享，相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中，咱们将介绍双链表的创建以及一些基本操作，接下来跟我一起

    2024年02月04日
    浏览(63)
  • 数据结构 2.1 线性表的定义和基本操作

    数据结构 2.1 线性表的定义和基本操作

    数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构） 线性表是具有 相同数据类型 的n（n=0）个数据元素的 有限序列 ，其中n为表长，当n=0时，线性表是一个空表。 每个数据元素所占空间一样大，有次序。 几个概念 1.ai是线性表中的第i个 i表示元素线性表中的

    2024年02月07日
    浏览(53)
  • c语言数据结构——链表的实现及其基本操作

    c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题： 中间/头部的插入删除，时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插

    2023年04月09日
    浏览(85)
  • 【数据结构】 循环双链表的基本操作 （C语言版）

    【数据结构】 循环双链表的基本操作 （C语言版）

    目录 一、循环双链表 1、循环双链表的定义： 2、循环双链表的优缺点： 二、循环双链表的基本操作算法（C语言）    1、宏定义  2、创建结构体 3、循环双链表的初始化  4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

    2024年01月22日
    浏览(59)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样，但本文并未采用 #define 定义容量的写法，这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟，后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中，重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包