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

数据结构单链表

9月前 作者：在冬天去看海 分类：Toy博客 阅读(44) 违法举报

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

数据结构单链表,数据结构

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

在我们开始讲链表之前，我们是写了顺序表，顺序表就是类似一个数组的东西，它的存放是连续的，优点有很多，比如支持我们随机访问，连续存放，命中率高，区别于单链表我们可以用类似数组的下标进行访问，这大大的提高我们的效率，但是也有缺点，空间不够就要需要扩容，扩容存在消耗的，头部或者中间位置的插入删除，需要挪动，挪动数据也是存在消耗的。避免频繁扩容，一次一般都是按倍数扩容，可能存在空间扩容。

链表的优点：
按需申请空间，不用释放空间。
头部或者中间位置的插入和删除，不需要挪动数据。
不存在空间浪费。

链表的缺陷：
每一个数据，都要存放一个指针去链表后面节点的地址。
不支持随机访问。

链表的结构

typedef int SLNodedataType;
typedef struct SList
{
	SLNodedataType data;
	struct SList* next;
	
}SLNode;

这个就是我们单链表的基本代码，我们来用图更加清清楚的表示一下它完整的样子。
数据结构单链表,数据结构
这就我们基本的逻辑结构，它前一个的next是存放后面的地址的，这样就能找到我们下一个节点。

单链表使用的时候相比和顺序表比较的话，它的使用不会浪费空间，我们需要一个节点就可以开辟一个节点出来供我们使用。但是它存储就不是连续的了。

那我们现在开始写代码来实现单链表。
单链表
首先我们要创建一个结构体。

typedef int SLNodedataType;
typedef struct SList
{
	SLNodedataType data;
	struct SList* next;
	
}SLNode;

接下来我们首先要打印我们的单链表
在这之前我们应该创建节点，创捷节点很简单，就是按照我们上面的图的前一个存放后面的地址。

//创建节点
	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
	assert(n1);
	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
	assert(n2);
	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
	assert(n3);
	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
	assert(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;

那下面就是我们的打印单链表。

void SListPrint(SLNode* plist)
{
	SLNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");

}

我们来测试一下看看效果。

数据结构单链表,数据结构
可以看到我们的单链表也是成功的打印，那接下来就是要写出我们的尾插函数。
写之前我们先来分析分析，首先尾插一个节点进去，那我们是不是要有一个这样的节点，竟然这样就可以写一个创造节点的函数。就叫他CreateSListNode

SLNode* CreateSListNode(SLNodedataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

写完这个那我们写一个尾插函数，尾插的时候我们要想一想要传什么地址过去，如果是有数据的话其实我们传一级地址就行，但是如果是空的话，就得传二级，因为我们要改变plist的位置。但是也其实是相当于头插，没节点的时候，总不能在空指针后面插入。那我们写一个 吧。

void SListPushBcak(SLNode** plist, SLNodedataType x)
{
	SLNode*newnode=CreateSListNode(x);
	assert(plist);

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

}

看一下我们编译的结果

数据结构单链表,数据结构
最后也是成功的尾插进去，那尾插之后就应该要写一个尾删。
写尾删的时候，我们要先考虑怎么找到最后，这和尾插一样，遍历一遍找到最后一个，然后free掉就行了。

数据结构单链表,数据结构
代码

void SListPopBack(SLNode** plist)
{
	SLNode* tail = *plist;
	SLNode* prev = NULL;
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}

这其实就是用了一个双指针的方法找最后一个的前一个，但是我们还需要注意链表不能为空，空了怎么删除啊。所以改进一下。

void SListPopBack(SLNode** plist)
{
	assert(plist);
	assert(*plist);
	SLNode* tail = *plist;
	SLNode* prev = NULL;
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}

void test1()
{
	//创建节点
	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
	assert(n1);
	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
	assert(n2);
	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
	assert(n3);
	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
	assert(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;

	SListPrint(n1);

	SListPushBcak(&n1, 5);
	SListPushBcak(&n1, 6);
	SListPushBcak(&n1, 7);
	SListPushBcak(&n1, 8);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPopBack(&n1);
	SListPrint(n1);
}

不过其实我们也可以不用双指针的办法。
那也整一个玩玩吧


void SListPopBack(SLNode** plist)
{
	assert(plist);
	assert(*plist);
	SLNode* tail = *plist;
	
	while (tail->next->next != NULL)
	{
		
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;

其实道理是一样的，就是找下下一个的节点是不是为空。
尾插写好就是头插，来吧展示。

void SListPushFront(SLNode** plist, SLNodedataType x)
{
	assert(plist);
	SLNode* newnode = CreateSListNode(x);
	if (*plist == NULL)
	{
		*plist = newnode;
	}
	else
	{
		newnode->next = *plist;
		*plist = newnode;
	}

}

其实想明白也不难，接下来就是头删。

void test1()
{
	//创建节点
	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
	assert(n1);
	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
	assert(n2);
	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
	assert(n3);
	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
	assert(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;

	SListPrint(n1);

	SListPushBcak(&n1, 5);
	SListPushBcak(&n1, 6);
	SListPushBcak(&n1, 7);
	SListPushBcak(&n1, 8);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPopBack(&n1);
	SListPrint(n1);

	SListPushFront(&n1, 111);
	SListPushFront(&n1, 222);
	SListPrint(n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPrint(n1);

}

void SListPopFront(SLNode** plist)
{
	assert(plist);
	assert(*plist);
	SLNode* cur = (*plist)->next;
	free(*plist);
	*plist = cur;
}

我们在写一个查找功能的代码

SLNode* SLFind(SLNode* plist, SLNodedataType x);

查找我们可以返回这个节点，这样就能和其他功能一起用，比如修改数据，或者在任意位置插入和删除。

SLNode* SLFind(SLNode* plist, SLNodedataType x)
{
	SLNode* pos = plist;
	while (pos->data == x)
	{
		return pos;
		pos = pos->next;
	}
}

这是只考虑找到的情况下，但是难免有时候会出现找不到的情况，让我们来看一下吧，写一个找不到情况下和找到情况下的代码。‘

SLNode* SLFind(SLNode* plist, SLNodedataType x)
{
	SLNode* pos = plist;
	while (pos != NULL)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
	return NULL;
}

然后我们可以写一个函数来判断有没有找到。

SLNode*pos = SLFind(n1, 111);
	if (pos != NULL)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}

我们看完整代码。

void test1()
{
	//创建节点
	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
	assert(n1);
	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
	assert(n2);
	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
	assert(n3);
	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
	assert(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;

	SListPrint(n1);

	SListPushBcak(&n1, 5);
	SListPushBcak(&n1, 6);
	SListPushBcak(&n1, 7);
	SListPushBcak(&n1, 8);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPopBack(&n1);
	SListPrint(n1);

	SListPushFront(&n1, 111);
	SListPushFront(&n1, 222);
	SListPrint(n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPrint(n1);

	SLNode*pos = SLFind(n1, 111);
	if (pos != NULL)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}

}

我们如果要找111发现没有找到，因为头删的时候改掉，其实我们竟然这样写了就可以写一个修改的代码，这里就不演示了。
接下来我们要写的是在任意位置删除和插入节点。

void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x)
{
	assert(plist);
	assert(pos);
	SLNode* newnode = CreateSListNode(x);
	if (pos == *plist)
	{
		SListPushFront(plist, x);
	}
	
	else
	{
		SLNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;

	}
}

测试代码

void test1()
{
	//创建节点
	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
	assert(n1);
	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
	assert(n2);
	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
	assert(n3);
	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
	assert(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;

	SListPrint(n1);

	SListPushBcak(&n1, 5);
	SListPushBcak(&n1, 6);
	SListPushBcak(&n1, 7);
	SListPushBcak(&n1, 8);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPopBack(&n1);
	SListPrint(n1);

	SListPushFront(&n1, 111);
	SListPushFront(&n1, 222);
	SListPrint(n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPrint(n1);

	SLNode*pos = SLFind(n1,3);
	if (pos != NULL)
	{
		printf("找到了\n");
		SListPushInsert(&n1, pos, 10086);
	}
	else
	{
		printf("找不到\n");
	}
	SListPrint(n1);
}

在任意位置删除

void SListPopInsert(SLNode** plist, SLNode* pos)
{
	assert(plist);
	assert(*plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPopFront(plist);
	}
	else
	{
		SLNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

其实还有可以在任意位置后删除，这样更快，就不用找那个位置前一个位置了，这里就不展示了，
完整代码

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLNodedataType;
typedef struct SList
{
	SLNodedataType data;
	struct SList* next;
	
}SLNode;


void SListPrint(SLNode* plist);

SLNode* CreateSListNode(SLNodedataType x);


void SListPushBcak(SLNode** plist, SLNodedataType x);

void SListPopBack(SLNode** plist);

void SListPushFront(SLNode** plist, SLNodedataType x);

void SListPopFront(SLNode** plist);

SLNode* SLFind(SLNode* plist, SLNodedataType x);

void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x);

void SListPopInsert(SLNode** plist, SLNode* pos);



#include"SList.h"

void SListPrint(SLNode* plist)
{
	SLNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");

}





SLNode* CreateSListNode(SLNodedataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPushBcak(SLNode** plist, SLNodedataType x)
{
	SLNode*newnode=CreateSListNode(x);
	assert(plist);

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

}


void SListPopBack(SLNode** plist)
{
	assert(plist);
	assert(*plist);
	SLNode* tail = *plist;
	SLNode* prev = NULL;
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}
//
//void SListPopBack(SLNode** plist)
//{
//	assert(plist);
//	assert(*plist);
//	SLNode* tail = *plist;
//	
//	while (tail->next->next != NULL)
//	{
//		
//		tail = tail->next;
//	}
//	free(tail->next);
//	tail->next = NULL;
//	
//}



void SListPushFront(SLNode** plist, SLNodedataType x)
{
	assert(plist);
	SLNode* newnode = CreateSListNode(x);
	if (*plist == NULL)
	{
		*plist = newnode;
	}
	else
	{
		newnode->next = *plist;
		*plist = newnode;
	}

}

void SListPopFront(SLNode** plist)
{
	assert(plist);
	assert(*plist);
	SLNode* cur = (*plist)->next;
	free(*plist);
	*plist = cur;
}


//SLNode* SLFind(SLNode* plist, SLNodedataType x)
//{
//	SLNode* pos = plist;
//	while (pos->data == x)
//	{
//		return pos;
//		pos = pos->next;
//	}
//}

SLNode* SLFind(SLNode* plist, SLNodedataType x)
{
	SLNode* pos = plist;
	while (pos != NULL)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
	return NULL;
}


void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x)
{
	assert(plist);
	assert(pos);
	SLNode* newnode = CreateSListNode(x);
	if (pos == *plist)
	{
		SListPushFront(plist, x);
	}
	
	else
	{
		SLNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;

	}
}

void SListPopInsert(SLNode** plist, SLNode* pos)
{
	assert(plist);
	assert(*plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPopFront(plist);
	}
	else
	{
		SLNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

测试主函数的也发一下吧，大家可以不用放一起测试，有点看不过来。

#include"SList.h"

void test1()
{
	//创建节点
	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
	assert(n1);
	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
	assert(n2);
	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
	assert(n3);
	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
	assert(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;

	SListPrint(n1);

	SListPushBcak(&n1, 5);
	SListPushBcak(&n1, 6);
	SListPushBcak(&n1, 7);
	SListPushBcak(&n1, 8);
	SListPrint(n1);
	SListPopBack(&n1);
	SListPopBack(&n1);
	SListPrint(n1);

	SListPushFront(&n1, 111);
	SListPushFront(&n1, 222);
	SListPrint(n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPopFront(&n1);
	SListPrint(n1);

	SLNode*pos = SLFind(n1,3);
	if (pos != NULL)
	{
		printf("找到了\n");
		SListPushInsert(&n1, pos, 10086);
	}
	else
	{
		printf("找不到\n");
	}
	SListPrint(n1);
}
int main()
{
	test1();
	return 0;
}

今天的分享就到这里，我们下次再见。文章来源地址https://www.toymoban.com/news/detail-653888.html

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

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

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

相关文章

  • 【数据结构】单链表（超全）

    【数据结构】单链表（超全）

    前言：  上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N) O ( N ) 效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那

    2024年02月11日
    浏览(40)
  • 数据结构—单链表

    数据结构—单链表

    目录 1.前言 2.了解单链表 3.单链表代码实现       3.1 单链表结构体实现       3.2 创建节点       3.3  打印单链表       3.4 尾插        3.5  头插        3. 6 头删       3.7  尾删       3.8  查找       3.9  插入            3.9.1 在pos位置之前插入             3.9.

    2023年04月20日
    浏览(104)
  • 【数据结构】单链表（详解）

    【数据结构】单链表（详解）

    所属专栏：初始数据结构 博主首页：初阳785 代码托管：chuyang785 感谢大家的支持，您的点赞和关注是对我最大的支持！！！ 博主也会更加的努力，创作出更优质的博文！！ 关注我，关注我，关注我，重要的事情说三遍！！！！！！！！ 前面我们已经用顺序表方式来实现接口

    2023年04月24日
    浏览(52)

  • 数据结构:单链表

    单链表的全称为\\\"不带头单向不循环链表\\\" 注意:         下文提到的头节点与带头链表时两个概念,文中的头节点指的是第一个有效节点,二带头节点中的头指的是第一个无效节点 链表和顺序表一样,都是线性表,逻辑结构上是线性的,但不同的是,链表在物理结构上不是线性的

    2024年01月21日
    浏览(40)
  • 数据结构——单链表

    数据结构——单链表

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

    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)
  • 【数据结构】单链表(一)

    【数据结构】单链表(一)

    作者：日出等日落 专栏：数据结构 想变成仲夏夜的一只萤火虫，只要抓住你的注意力，就已经满足了。 目录 前言：  单链表的结构 ：  逻辑结构： 物理结构： BuySLTNode（动态申请一个结点）：   CreateSList(//循环创建结点)： SLTPrint（单链表打印）：  单链表的功能：  SL

    2024年02月01日
    浏览(44)
  • 数据结构·单链表

    数据结构·单链表

            不可否认的是，前几节我们讲解的顺序表存在一下几点问题：         1. 中间、头部的插入和删除，需要移动一整串数据，时间复杂度O(N)         2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗         3. 增容一般是2倍的增长，这势

    2024年01月25日
    浏览(75)
  • 【数据结构】单链表详解

    【数据结构】单链表详解

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

    2024年02月09日
    浏览(34)
  • 数据结构——单链表（下）

    数据结构——单链表（下）

    🌇个人主页：_麦麦_ 📚今日名言：年轻时候的我以为坚持是永不动摇，到这个年纪明白了坚持就是犹疑着，退缩着，心猿意马着，一步三停着，还在往前走。——《十二月历》 目录 一、引言  二、单链表剩余功能的实现         1.单链表的查找         2. 单链表指定位

    2024年01月17日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包