您现在的位置是：首页 >技术教程 >单链表—C语言实现数据结构网站首页技术教程

本期带大家一起用C语言实现单链表???

一、链表的概念?

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。

二、链表中数据元素的构成? ?

每个元素本身由两部分组成：

1、本身的信息，称为“数据域”

2、指向直接后继的指针，称为“指针域”

三、链表的结构? ? ?

1、带哨兵位或者不带哨兵位 ?

2、循环或者不循环 ? ?

3、单向或者双向 ? ? ?

但是我们常用的链表主要是单链表和带头双向循环链表，一个结构最简单，一个结构最复杂。

下面简单介绍一下两个链表的特性(补充说明)

无头单向非循环链表：也就是我们俗称的单链表。其结构简单，一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶、栈的链式结构等。因为单链表本身有缺陷，所以为常见的考核点之一。

带头双向循环链表：结构最复杂，一般用来单独存储数据。实际使用的链表，大多都是带头双向循环链表。虽然这种链表结构最复杂，但是其实有很多优势，并且在一定程度上对单链表的缺陷做出了一定的纠正。

而我们本篇博客就是对结构最简单的 单链表 进行讲解并实现
也是为了和带头双向循环链表做个对比

对于带头双向循环链表的话，之前以前我们已经总结过了,感兴趣的小伙伴可以在下面的链接当中查看
带头双向循环链表

四、 单链表的实现✅✅

单链表的结构为
存储的有效数据data
指向后一个数据地址的指针next

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

这里我们使用typedef对我们所存储的数据，以及单链表结构体重命名，方便我们后续修改 ? ? ?

链表的一开始是空的。所以我们插入数据时，需要让plist指向我们新节点。就相当于改变plist的指向。plist是一级指针，那么要改变plist就要传它的地址&plist，为二级指针，所以也需要用二级指针来接收该参数。

二、接口的实现✅✅

1.单链表的创建以及初始化

我们插入数据，都需要创建节点。因为链表是按需分配的，创建即用。如果使用局部变量的话，那么在函数调用结束后节点就销毁了，那么肯定就需要使用动态内存开辟新的节点：

SLTNode* CreatSLTnode(SLTDataType x)
{

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

1.单链表的尾插

从尾部插入数据，需要分两种情况考虑：链表为空、链表有节点

如果链表为空，那么就需要创建节点，并且将创建的节点赋给原链表；
如果链表不为空，则需要找到链表的尾部，然后将新节点到尾部的后面链接就可以

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode* newnode=CreatSLTnode(x);

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

2.单链表的头插

我们直接创建新节点，并且将新节点的 next 链接为原来的头，然后将头变为新节点，就可以了
因为就头插来说，如果链表为空，那么头部也为空，所以可以直接链接起来

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = CreatSLTnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.单链表的尾删

尾删需要判断链表是否为空，并且需要将链表中 节点数 为单个节点和多个节点的情况分开讨论。

如果是单个节点删除，那么只需要释放节点，将节点置空

如果是两个及以上节点删除，尾删需要将删除元素的前一个链接为空指针，需要删除尾结点，而完成这两个步骤的方法就是遍历单链表，通过条件来求出这两个位置。找到这两个位置后，释放尾结点，将尾结点的前一个位置的next置空

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;

	}
}

需要注意的是我们的循环终止条件不能写成tail->next!=NULL，在没有指向前一个节点的时候
当我们写成tail->next!=NULL时候，跳出循环之后free(tail)的时候，销毁了这个节点并且将tail=NULL，但是其实没有起到作用，我们通过调试看看

可以看到的是，没有起到真正的销毁，所以我们这里的循环条件还是要写成
tail->next->next!=NULL,然后再销毁节点

4.单链表的头删

对于空链表，直接断言判断就可以。

对于1个及以上节点，那么就是释放头结点，并且头结点的next设定为头。

void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);
	//一个节点
	//多个节点
	SLTNode* cur = *pphead;
	*pphead = cur->next;

	free(cur);
	cur = NULL;

}

5.单链表的查找

对于查找来说，相对比较简单。查找链表中某个元素是否存在，只需要遍历链表，查看里面是否有这个值
如果找到了，返回这个节点的地址
没找到，返回空指针

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

这里我将空链表定成不可以查找，其实空链表也可以查找，只不过是返回NULL而已

6. 删除pos位置的节点

删除pos位置的节点，需要考虑此时链表是否为空，但这只是一部分，只需要用断言处理一下就好。

而我们着重处理的为，头删和多个节点删除的情况。

如果是头删，那么删除的就是第一个节点，那么此时就需要将头变为pos->next，并且释放pos位置。头删情况也完美处理了单个节点删除时的情况。

如果是多个节点，那么就需要找到pos的前一个位置，将 pos 前一个位置prev的 next 链接为我当前 pos 的 next。然后释放我的pos节点。

void SLTPop(SLTNode** pphead, SLTNode* pos)
{
	
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	if (pos->next == NULL)
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
		return;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
			tail = tail->next;
		tail->next = pos->next;
		free(pos);
		pos = NULL;

	}

}

7. 在pos的位置插入

在pos的位置插入，这里我们需要遍历链表，然后在对此操作

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = prev->next;
		prev->next = newnode;

	}

}

这里的来解释一下最后几行代码
当我们找到了pos节点之后，我们prev->next找到了pos节点
这时候我们创建的新节点newnode的next指向下一个节点prev->next
也就是指向pos节点
然后将prev->next赋值为newnode，也就是原来pos的位置现在变成了newnode

8. 在pos的位置之后插入

我只需要让 新节点newnode 和 pos 位置的下一个节点链接，然后将pos位置的next变为我的新节点即可。

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTNode* newnode = CreatSLTnode(x);
		pos->next = newnode;
	}
	else
	{

		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;
	}
}

其实这段代码还可以更加简单，不知道你发现没有
其实只需要就行
仔细体会一下

	SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;

9. 单链表的销毁

因为单链表是由不同地址的节点串联起来的。它不像数组，存储连续，只要释放起始位置。

如果我仅仅释放*pphead，那么只释放了我的第一个节点，后面的节点没释放，函数调用结束后，这些节点也找不到了。所以我们需要逐个销毁。

首先，使用 cur 拷贝头部位置。然后使用循环迭代。迭代过程中，需要记住我的 cur->next ，否则 cur 被释放后，无法找到下一个节点，然后逐个释放就可以了。

注意：当销毁后，记得把*pphead 置空`，防止销毁链表后对链表误操作而导致的野指针问题

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

10.单链表的打印

打印整个链表，只需要遍历链表，控制好循环的停止条件：

void SLTPrint(SLTNode* phead)
{

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

五、完整代码

SList.h

#pragma once

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);

//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushBack(SLTNode** pphead, SLTDataType x); 
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//销毁
void SLTDestroy(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);
//在pos的位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

void SLTPop(SLTNode** pphead, SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS


#include"Slist.h"

SLTNode* CreatSLTnode(SLTDataType x)
{

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = CreatSLTnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode* newnode=CreatSLTnode(x);

	SLTNode* tail = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next != NULL)
		{
			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!= NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;

	}
}

void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);
	//一个节点
	//多个节点
	SLTNode* cur = *pphead;
	*pphead = cur->next;

	free(cur);
	cur = NULL;

}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = prev->next;
		prev->next = newnode;

	}

}


void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTNode* newnode = CreatSLTnode(x);
		pos->next = newnode;
	}
	else
	{

		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;


	}


}


//删除pos位置的值
void SLTPop(SLTNode** pphead, SLTNode* pos)
{
	
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	if (pos->next == NULL)
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
		return;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
			tail = tail->next;
		tail->next = pos->next;
		free(pos);
		pos = NULL;

	}

}


void SLTPrint(SLTNode* phead)
{

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



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

test.c

#define _CRT_SECURE_NO_WARNINGS

#include"Slist.h"


int main()
{

    SLTNode* Slist = NULL;
    printf("原数据：");
    SLTPushBack(&Slist, 1);
    SLTPushBack(&Slist, 2);
    SLTPushBack(&Slist, 3);
    SLTPushBack(&Slist, 4);
    SLTPushBack(&Slist, 5);
    SLTPushBack(&Slist, 6);
    SLTPrint(Slist);

    printf("头插：");
    SLTPushFront(&Slist, 7);
    SLTPrint(Slist);

    printf("尾插：");
    SLTPushBack(&Slist, 8);
    SLTPrint(Slist);
    printf("头删：");
    SLTPopFront(&Slist);
    SLTPrint(Slist);
    printf("尾删：");
    SLTPopBack(&Slist);
    SLTPrint(Slist);
    printf("在pos的位置插入:");
    SLTNode* pos1 = SLTFind(Slist, 3);
    if (pos1!=NULL)
    {
        SLTInsert(&Slist, pos1, 20);
        SLTPrint(Slist);
    }


    printf("在pos的位置之后插入:");
    SLTNode* pos2 = SLTFind(Slist, 3);
    if (pos2 != NULL)
    {
        SLTInsertAfter(&Slist, pos1, 30);
        SLTPrint(Slist);
    }

    printf("删除指定位置:");
    SLTNode* pos3 = SLTFind(Slist, 3);
    if (pos3!= NULL)
    {
        SLTPop(&Slist, pos3);
        SLTPrint(Slist);
    }
    SLTDestroy(&Slist);
    return 0;

}

测试结果

六、感谢与交流✅

???如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的，疑惑的话，或者什么比较好的建议的话，可以发到评论区，
我们一起解决，共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️???