【数据结构】单链表详解

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

当我们学完顺序表的时候,我们发现了好多问题如下:

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

如何解决上面的问题呢??今天就跟着小张一起学习单链表吧!!

链表的概念及结构

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

注意:1.链式结构在逻辑上是连续的,但是在物理上不一定连续
2.结点一般都是在堆上申请出来的(malloc)
3.从堆上申请的空间,是按照一定策略来分配的,两次申请的空间可能连续,也可能不连续

单链表

【数据结构】单链表详解,数据结构

单链表的接口实现

void  printdata(info* phead)//打印单链表
info* BuySListNode(int x)//创建新结点
void pushback(info** pphead, int x)//尾插
void pushFront(info** pphead, int x)//头插
void popFront(info** pphead)//头删
void popBack(info** pphead)//尾删
info* SListFind(info* pphead, int x)//单链表查找
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
void SeqListErase(info** pphead, info* pos)//删除pos位置的值
void SListInsertAfter(info* pos, int x)//单链表在pos位置之后插入x
void SListEraseAfter(info* pos)//删除pos的后一个位置

0.结构体定义单个结点

typedef struct info {
	int data;//data存数据
	struct info* next;//info*next存放下一个结点的地址

}info;

1.创建新结点

info* BuySListNode(int x)
{
	info* newnode = (info*)malloc(sizeof(info));//空间申请
	assert(newnode);//断言,新结点是否申请到了
	newnode->data = x;//数据赋值
	newnode->next = NULL;//指向的地址赋值
	return newnode;//将申请好的空间首地址返回回去



}

【数据结构】单链表详解,数据结构

断言,如果没申请到空间,mallo返回空指针,断言newnode就会报错

为什么要用二级指针传参在尾插,头插,尾删,头删中

分析:【数据结构】单链表详解,数据结构

2.尾插

void pushback(info** pphead, int x)//尾插
{
	info* newnode = BuySListNode(x);//将创建好的新结点的地址保存在newnode变量中
	

	if (*pphead == NULL)//链表无结点
	{
		*pphead = newnode;// 将创建好的头节点的地址给给*pphead,作为新头节点的地址
	}
	else
	{
		info* tail = *pphead;//定义一个指针,先指向头结点的地址
		while (tail->next != NULL)//循环遍历找尾结点
		{
			tail = tail->next;//指针指向下一个结点

		}
		tail->next = newnode;//找到尾结点,将尾结点的next存放新接结点的地址

	}

}

分析:
【数据结构】单链表详解,数据结构

文字解释:大体上就是直接将最后一个结点的next存入新结点的地址,然后将新结点的next存入空(NULL)。
申请新的结点,如果pphead为空地址,链表还没有结点,将新结点的地址传给pphead,新结点的地址就是头结点的地址,如果该链表中已经存在结点,定义一个指针先存放头节点的地址,然后遍历整个链表,循环寻找哪个结点的next为NULL,不是的话就将tail指向下一个结点,对应操作为tail = tail->next;结点的next为NULL,那个结点就是尾结点,找到尾结点之后将尾结点的next存入要插入新结点的地址,新结点的next已经在 BuySListNode(int x)置为空地址

3.打印链表

void  printdata(info* phead)
{
	info* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");


}

分析【数据结构】单链表详解,数据结构
文字描述:定义一个指针cur指向头结点,使用这个指针循环遍历,这个指针指向的不为空的话就继续循环,在循环中打印cur->data,对应的操作是printf(“%d->”, cur->data);打印%d后面加->是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur = cur->next;,继续打印。

4.头插

void pushFront(info** pphead, int x)//头插
{
	info* newnode = BuySListNode(x);//创建新结点,将新结点的地址存放在newnode指针变量中
	newnode->next = *pphead;//新结点的下一个结点应该为旧头结点的地址
	*pphead = newnode;//新头结点的地址更新为newnode指针所指向的地址


}

分析
【数据结构】单链表详解,数据结构

文字描述:将创建的新结点的地址存放在newnode指针变量中,pphead为原先头结点的地址,头插一个新结点后,应该将新结点的next存放原先头结点的地址,对应操作为newnode->next = pphead;然后保存在pphead应该为新的头结点的地址,也就是newnode所指向的地址,对应操作为pphead = newnode;

5.头删

void popFront(info** pphead)
{
	info* p =(*pphead)->next;//定义指针存放头结点的下一个结点的地址
	free(*pphead);//释放头结点
	*pphead = p;//头结点地址更新为原先头结点的下一个结点的地址
}

分析:
【数据结构】单链表详解,数据结构

6.尾删

void popBack(info** pphead)
{
	info* tailprev = NULL;
	info* tail = *pphead;


	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
    }
	else
	{while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;
       }
		free(tail);
		tailprev->next = NULL;
	}
}

分析:【数据结构】单链表详解,数据结构

7.修改

info* SListFind(info* pphead, int x)
{
	info* cur = pphead;//cur指针保存pphead指针接收的地址
	while (cur)
	{
		if (cur->data == x)
		{  //cur->data==y可以将查找出来的值修改为y,不用单独写修改函数,传参也要多一个y
			return cur;//找到的话返回该结点的地址
		}
		cur = cur->next;//cur指向下一个结点的地址
    }
	return NULL;

}

分析:
【数据结构】单链表详解,数据结构

8.pos指针指向结点的地址的前一个位置前插插入(随便插)

SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{
	assert(pphead);//头结点地址不能为空
	if (pos == *pphead)//pos指针指向结点的地址为头结点,相当于头插
	{
		pushFront(*pphead, x);//调用头插函数

	}
	else
	{
		info* prev = *pphead;//定义一个prev指针,先让他保存头结点的地址
		while (prev->next != pos)//循环遍历找pos指针指向结点的前一个结点
		{
			prev = prev->next;

        }
		info* newnode=BuySListNode(x);//申请新结点,将申请好的结点地址存放在newnode指针变量里面
		prev->next = newnode;//使之前pos指针指向的结点的前一个结点的next存入插入新结点的地址,
		newnode->next = pos;//然后新结点的next存入pos指向结点的地址
}
}

分析:【数据结构】单链表详解,数据结构

9.删除pos位置的值

void SeqListErase(info** pphead, info* pos)
{
	if (pos == *pphead)//删除结点是否为头结点
	{
		popFront(*pphead);//头删
    }
	else
	{
		info* prev = *pphead;//定义一个prev指针,先让他存放头结点的地址
		while (prev->next != pos)//循环遍历寻找哪个结点的next存放的是pos指针指向的结点的地址
		{
			prev = prev->next;//prev指针指向下一个结点
        }
		prev->next = pos->next;//pos指针指向的结点的上一个结点的next存放pos指针指向的结点的下一个结点的地址
		free(pos);//释放掉pos指针指向的那块空间

    }
}

分析:【数据结构】单链表详解,数据结构

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

void SListInsertAfter(info* pos, int x)
{
	assert(pos);//防止在空指针
	info* newnode=BuySListNode(x);//申请新结点
	newnode->next = pos->next;
	pos->next = newnode;

}

分析:【数据结构】单链表详解,数据结构
那么1,2是否可以反过来

	pos->next = newnode;
	newnode->next = pos->next;
	

不行,d3的地址会丢失
出现下图的情况:【数据结构】单链表详解,数据结构

11.删除pos的后一个位置

void SListEraseAfter(info* pos)
{
	assert(pos);//防止pos指向空地址
	if (pos->next == NULL)//如果pos指针指向最后一个结点
		return;//直接退出,不往下执行
	info* del = pos->next;//保存pos指针指向结点的下一个结点的地址
	pos->next = del->next;//更新pos指针指向的结点的下一个结点为pos指针指向结点下下一个结点的地址
	free(del);//释放掉保存pos指针指向结点的下一个结点的地址的空间。

}

分析:【数据结构】单链表详解,数据结构

12.完整源码

#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct info {
	int data;
	struct info* next;

}info;
void  printdata(info* phead)
{
	info* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");


}
info* BuySListNode(int x)
{
	info* newnode = (info*)malloc(sizeof(info));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;



}
void pushback(info** pphead, int x)//尾插
{
	info* newnode = BuySListNode(x);
	

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		info* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;

		}
		tail->next = newnode;

	}













}
void pushFront(info** pphead, int x)//头插
{
	info* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;


}
void popFront(info** pphead)//头删
{
	info* p =(*pphead)->next;
	free(*pphead);
	*pphead = p;







}
void popBack(info** pphead)//尾删
{
	info* tailprev = NULL;
	info* tail = *pphead;


	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;





	}
	else
	{

		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;


		}
		free(tail);
		tailprev->next = NULL;
	}
}
info* SListFind(info* pphead, int x)//查找
{
	info* cur = pphead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;





	}
	return NULL;
}
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{
	assert(*pphead);
	if (pos == *pphead)
	{
		pushFront(*pphead, x);

	}
	else
	{
		info* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;

        }
		info* newnode=BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;








	}










}
void SeqListErase(info** pphead, info* pos)
{
	if (pos == *pphead)
	{
		popFront(*pphead);

    
	}
	else
	{
		info* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;



		}
		prev->next = pos->next;
		free(pos);

    }





}
void SListInsertAfter(info* pos, int x)
{
	assert(pos);
	info* newnode=BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListEraseAfter(info* pos)
{
	assert(pos);
	if (pos->next == NULL)
		return;
	info* del = pos->next;
	pos->next = del->next;
	free(del);

}

int main()
{

	info* n1 = (info*)malloc(sizeof(info));
	info* n2 = (info*)malloc(sizeof(info));
	info* n3 = (info*)malloc(sizeof(info));
	info* n4 = (info*)malloc(sizeof(info));
	assert(n1 && n2 && n3 && n4);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;



	printf("原链表:");
	printdata(n1);
	printf("\n");
	printf("尾插:");
	pushback(&n1, 5);
	pushback(&n1, 6);
	pushback(&n1, 7);
	pushback(&n1, 8);
	printdata(n1);
	printf("\n");
	printf("头插:");
    pushFront(&n1, 10);
	pushFront(&n1, 20);
	printdata(n1);
	printf("\n");
	printf("头删:");
	popFront(&n1);
	printdata(n1);
	printf("\n");
	printf("尾删:");
	popBack(&n1);
	popBack(&n1);
	printdata(n1);
	printf("\n");
	printf("查找到并修改:");
	SListFind(n1, 3)->data = 80;
	printdata(n1);
	printf("\n");
	printf("pos指针指向结点的地址的前一个位置前插插入:");
	SeqListInsert(&n1, n4, 100);
	printdata(n1);
	printf("\n");
	printf("删除pos位置的值:");
	SeqListErase(&n1, n4);
	printdata(n1);
	printf("\n");
	printf("单链表在pos位置之后插入x:");
	SListInsertAfter(n2, 1000);
	printdata(n1);
	printf("\n");
	printf("删除pos的后一个位置:");
	SListEraseAfter(n1);
	printdata(n1);
	printf("\n");

}

13.代码编译运行

【数据结构】单链表详解,数据结构文章来源地址https://www.toymoban.com/news/detail-700592.html

到了这里,关于【数据结构】单链表详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • [数据结构]链表之单链表(详解)

    在学习 链表 之前,我们已经学习了 顺序表 了 根据 顺序表 的特点,我们可以发现 顺序表 有优点,也有一些缺陷。 所以根据 顺序表 的缺点,链表就横空出世啦~ **概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次

    2023年04月08日
    浏览(56)
  • 数据结构学习分享之单链表详解

        💓博主CSDN:杭电码农-NEO💓🎉🎉🎉       ⏩专栏分类:数据结构学习分享(持续更新中🫵)⏪🎉🎉🎉     让我们紧接上一章顺序表的概念,引出链表,我们说顺序表每次增容需要申请新的空间,会产生很多空间碎片,代价比较高,并且我们扩容一般是扩两倍,还是会有一些

    2024年02月02日
    浏览(49)
  • 数据结构入门 — 链表详解_单链表

    数据结构入门 — 单链表详解 * 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 第一篇:数据结构入门 — 链表详解_单链表 第二篇:数据结构入门 — 链表详解_双向链表 第三篇:数据结构入门

    2024年02月11日
    浏览(55)
  • 数据结构之单链表详解(C语言手撕)

    ​ 🎉文章简介: 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 从图片中可以看出,链表的每个节点都是一个结构体,该结构体中有一个存储数据的变量和一个指向下一节点的结构体指针; 在逻辑上

    2024年03月10日
    浏览(45)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(60)
  • 【数据结构与算法】顺序表与链表(单链表和双链表)超详解图示与源码。

                                                       大家好,今天我们来学习数据结构中的顺序表与链表!源码在最后附上 首先我们先来认识一下 顺序表 :                                       **如上图所示:很多人会以为数组就是顺序表,顺序表就是数组,这

    2024年02月21日
    浏览(60)
  • 数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表)

    目录  一.什么是链表 二.链表的实现 节点的插入 头插法 尾插法 指定位置插入 节点的删除 删除第一次出现的节点 删除所有节点 节点的查找 链表的清空 链表的长度 前言: 在上一篇文章中,我们认识了线性数据结构中的顺序表,而本篇文章则是介绍线性数据结

    2024年02月05日
    浏览(61)
  • 【数据结构】数据结构小试牛刀之单链表

    不讲虚的啦,直接肝! 单链表所要实现的功能罗列如下: 初始化工作我们先初始化一个节点类型,类型中包括了数据域和指针域,数据与中保存着该节点要保存的数据,指针域则保存着链表下一个节点的地址: 然后我们在创建一个函数,用于创建一个新的节点,因为后面我

    2023年04月24日
    浏览(62)
  • 数据结构——单链表

    我们需要在程序中存储一系列的数据,这些数据不是一成不变的,需要满足随时的动态增删查改。 顺序表,虽然能满足这些要求,可是顺序表在头插或者中间插入数据时,需要将数据一个一个挪动,效率较低;而且需要频繁的扩容,扩容也是需要付出一定的代价。 为有效解

    2023年04月17日
    浏览(53)
  • 数据结构之单链表

    目录 1.什么是链表。 2.链表的优点 3.单链表的实现 1.单链表的结构体 2.节点的创建 3.参数的调用 4.头插  5.尾插 7.头删 8.尾删 8.在pos节点前插入x 9.在pos节点前插入x 10.删除pos位置节点  对于顺序表我们发现,在此基础上仍存在了些许不足: 1.中间或头部的插入时间复杂度为O

    2024年02月05日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包