单链表详解(附图解，结尾附全部源码)

下面开始带大家对单链表的增删查改进行图解

首先给大家介绍一下链表

链表就是每一个结构体中包含一个数据和一个结构体指针，这个指针就相当于锁链的作用将下一个结构体给锁住，但是每个结构体的空间是相对独立的。

图解：

1 首先实现尾插

如果我们要尾插，那就要把尾节点找到，然后用next指针进行连接

图解：

下面是代码实现

这里我考虑了一种特殊情况，就是如果链表为空的时候，我们就直接让头节点链接上。

这里必须要用到二阶指针来判定第一个节点是否为空的状态。

(如果用一阶指针的话，那么出了这个函数的作用域之后空间被销毁了，相当于你白忙活了）

每次用完记得把空间释放掉，不然存在内存泄漏

SL* BuyNewnode(DataSL x)
{
	SL* Newnode = (SL*)malloc(sizeof(SL));
	if (Newnode==NULL)
	{
		perror("malloc");
		assert(Newnode);
	}
	Newnode->data = x;
	Newnode->next = NULL;
	return Newnode;
}


void DistorySL(SL** pphead)
{
    SL* tail = *pphead;
	if (tail)
		return;
	else
	{
		while (tail->next)
		{
			SL* cur = tail->next;
			tail->next = NULL;
			tail->data = 0;
			free(tail);
			tail = cur;
		}
		tail->next = NULL;
		tail->data = 0;
		free(tail);
	}
}


void BackPushSL(SL** pphead, DataSL x)//尾插
{
	SL* tail = *pphead;
	SL* Newnode = BuyNewnode(x);
	if (tail == NULL)
	{
		*pphead = Newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = Newnode;
	}
}

2 然后实现尾删

void BackPopSL(SL** pphead)//尾删
{
	assert(pphead);
	assert(*pphead);//空链表不删
	SL* tail = *pphead;
	if (tail->next==NULL)
	{
		tail->data = 0;
		free(tail);
	}
	else
	{
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

3 然后实现头插

void FrontPushSL(SL** pphead, DataSL x)
{
	assert(pphead);
	SL* tail = *pphead;
	SL* Newnode= BuyNewnode(x);
	if (tail == NULL)
	{
		tail = BuyNewnode(x);
	}
	else
	{
		Newnode->next = tail;
	}
	*pphead = Newnode;
}

4 然后实现头删

void FrontPopSL(SL** pphead)
{
	assert(pphead);
	SL* tail = (*pphead)->next;
	free(*pphead);
	(*pphead)->next = NULL;
	*pphead = tail;
}

5 然后实现中间插入（配合查找）

中间插入分两种情况前插和后插

SL* FindSL(SL** pphead, DataSL x)
{
	SL* tail = *pphead;
	while (tail)
	{
		if (tail->data == x)
		{
			break;
		}
		else
		{
			tail = tail->next;
		}
	}
	return tail;
}


void FrontInsertSL(SL** pphead,SL* pos,DataSL x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	SL* Newnode = BuyNewnode(x);
	SL* cur = tail;
	if (*pphead == NULL)
	{
		FrontPushSL(&tail,x);
	}
	while (tail!= pos)
	{
		cur = tail;
		tail = tail->next;
	}
	cur->next = BuyNewnode(x);
	cur->next->next = pos;
}

后插的情况类似

SL* FindSL(SL** pphead, DataSL x)
{
	SL* tail = *pphead;
	while (tail)
	{
		if (tail->data == x)
		{
			break;
		}
		else
		{
			tail = tail->next;
		}
	}
	return tail;
}



void AfterInsertSL(SL** pphead, SL* pos, DataSL x)
{
	assert(pphead);
	assert(pos);
	SL* Newnode = BuyNewnode(x);
	SL* tail = *pphead;
	while (tail != pos)
	{
		tail = tail->next;
	}
	SL* cur = tail->next;
	tail->next = Newnode;
	Newnode->next = cur;
}

6 接着实现查删节点(原理和上面差不多，大家可以自行画图）

void EraseSL(SL** pphead, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	if (tail==pos)
	{
		BackPopSL(tail);
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
	SL* cur = tail->next;
	tail->next = tail->next->next;
	cur->data = 0;
	cur->next = NULL;
	free(cur->next);
	}
}

7 最后实现改某个节点的内容

void ReviseSL(SL** pphead, SL* pos, DataSL x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	if (tail== pos)
	{
		tail->data = x;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next->data = x;
	}
}

下面附所有的源码

SingleSeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataSL;
typedef struct SingleSqList SL;
typedef struct SingleSqList 
{
	DataSL data;
	SL* next;
}SL;

//开辟节点
SL* BuyNewnode(DataSL x);
//打印单链表的值
void SLPrint(SL* pphead);
//销毁链表
void DistorySL(SL** pphead);

singleSeqList.h

//对链表的增删查改
//头插尾插，头删尾删
void BackPushSL(SL** pphead,DataSL x);
void BackPopSL(SL** pphead);

void FrontPopSL(SL** pphead);
void FrontPushSL(SL** pphead, DataSL x);

//前插
void FrontInsertSL(SL** pphead,SL* pos,DataSL x);


//后插
void AfterInsertSL(SL** pphead, SL* pos, DataSL x);



//查找节点
SL* FindSL(SL** pphead, DataSL x);

//删除某个节点
void EraseSL(SL** pphead, SL* pos);

//修改某个节点的内容
void ReviseSL(SL** pphead, SL* pos, DataSL x);


SingleSeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SingleSqList.h"


void SLPrint(SL** pphead)
{
	SL* tail = *pphead;
	if (tail == NULL)
	{
		return;
	}
	while (tail->next)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("%d", tail->data);
}

void DistorySL(SL** pphead)
{
    SL* tail = *pphead;
	if (tail)
		return;
	else
	{
		while (tail->next)
		{
			SL* cur = tail->next;
			tail->next = NULL;
			tail->data = 0;
			free(tail);
			tail = cur;
		}
		tail->next = NULL;
		tail->data = 0;
		free(tail);
	}
}




SL* BuyNewnode(DataSL x)
{
	SL* Newnode = (SL*)malloc(sizeof(SL));
	if (Newnode==NULL)
	{
		perror("malloc");
		assert(Newnode);
	}
	Newnode->data = x;
	Newnode->next = NULL;
	return Newnode;
}


void BackPushSL(SL** pphead, DataSL x)//尾插
{
	assert(pphead);
	SL* tail = *pphead;
	SL* Newnode = BuyNewnode(x);
	if (tail == NULL)
	{
		*pphead = Newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = Newnode;
	}
}


void BackPopSL(SL** pphead)//尾删
{
	assert(pphead);
	assert(*pphead);//空链表不删
	SL* tail = *pphead;
	if (tail->next==NULL)
	{
		tail->data = 0;
		free(tail);
	}
	else
	{
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

void FrontPushSL(SL** pphead, DataSL x)
{
	assert(pphead);
	SL* tail = *pphead;
	SL* Newnode= BuyNewnode(x);
	if (tail == NULL)
	{
		tail = BuyNewnode(x);
	}
	else
	{
		Newnode->next = tail;
	}
	*pphead = Newnode;
}


void FrontPopSL(SL** pphead)
{
	assert(pphead);
	SL* tail = (*pphead)->next;
	free(*pphead);
	(*pphead)->next = NULL;
	*pphead = tail;
}


SL* FindSL(SL** pphead, DataSL x)
{
	SL* tail = *pphead;
	while (tail)
	{
		if (tail->data == x)
		{
			break;
		}
		else
		{
			tail = tail->next;
		}
	}
	return tail;
}



void FrontInsertSL(SL** pphead,SL* pos,DataSL x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	SL* Newnode = BuyNewnode(x);
	SL* cur = tail;
	if (*pphead == NULL)
	{
		FrontPushSL(&tail,x);
	}
	while (tail!= pos)
	{
		cur = tail;
		tail = tail->next;
	}
	cur->next = BuyNewnode(x);
	cur->next->next = pos;
}

void AfterInsertSL(SL** pphead, SL* pos, DataSL x)
{
	assert(pphead);
	assert(pos);
	SL* Newnode = BuyNewnode(x);
	SL* tail = *pphead;
	while (tail != pos)
	{
		tail = tail->next;
	}
	SL* cur = tail->next;
	tail->next = Newnode;
	Newnode->next = cur;
}


void EraseSL(SL** pphead, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	if (tail==pos)
	{
		BackPopSL(tail);
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
	SL* cur = tail->next;
	tail->next = tail->next->next;
	cur->data = 0;
	cur->next = NULL;
	free(cur->next);
	}
}


void ReviseSL(SL** pphead, SL* pos, DataSL x)
{
	assert(pphead);
	assert(pos);
	SL* tail = *pphead;
	if (tail== pos)
	{
		tail->data = x;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next->data = x;
	}
}

链表每个功能我基本都实现了一遍这里就不一一的展现。（目前测试还未遇到问题）