链表的学习，要多画图，分析其中的逻辑关系，便于理解

下面是对单链表所有操作的代码以及详细注释，便于复习

目录

整体声明

创建节点

单链表尾插

单链表的尾删

单链表打印

单链表的头插

单链表头删

单链表查找

任意位置插入

任意位置的删除

链表中所有的节点计数

单链表的销毁

---

---

        我们对【无头+单向+非循环】链表实现增删查改的功能分别进行代码实现，并对步骤尽可能进行详细分析。

整体声明

// 单链表中的常规操作
// 单链表尾插
// 注意：并不是所有的方法都要在头文件中声明
//      一般只要将其他用户需要调用的方法在头文件中声明

// 单链表节点的定义
typedef struct SListNode
{
	DataType data;             // 节点中的值域
	struct SListNode* next;    // 下一个节点的地址
}SListNode;
 
 
///
// 单链表中的常规操作
// 单链表尾插
// 注意：并不是所有的方法都要在头文件中声明
//      一般只要将其他用户需要调用的方法在头文件中声明
void SListPushBack(SListNode** pplist, DataType x);
 
// 单链表的尾删
void SListPopBack(SListNode** pplist);
 
// 单链表的头插
void SListPushFront(SListNode** pplist, DataType x);
 
// 单链表头删
void SListPopFront(SListNode** pplist);
 
// 单链表查找
SListNode* SListFind(SListNode* plist, DataType x);
 
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, DataType x);
 
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
 
void SListDestroy(SListNode** plist);
 
 
// 测试链表
void TestSList();

创建节点

链表内部自己实现的时候要使用的方式
用户可以不用知道，该方法不需要在头文件中声明

SListNode* BuySListNode(DataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (NULL == newNode)
	{
		printf("创建节点失败!!!\n");
		exit(0);  // 暴力方式处理
	}
 
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

单链表尾插

pplist内部现在保存的时候实参plist的地址

*pplist ===> 实参plist

void SListPushBack(SListNode** pplist, DataType x)
{
	assert(pplist);  // pplist是空：链表不存在
 
					 // 空链表---需要让pplist指向刚刚插入的新节点
	if (NULL == *pplist)
	{
		*pplist = BuySListNode(x);
	}
	else
	{
		// pplist的链表不为空
		// 1. 找到原链表中的最后一个节点
		SListNode* cur = *pplist;
		while (cur->next)
		{
			// 获取cur的下一个节点
			// cur++;   // 注意下一个节点是通过next指针域获取
			cur = cur->next;
		}
 
		// 2. 插入新节点
		cur->next = BuySListNode(x);
	}
}

单链表的尾删

void SListPopBack(SListNode** pplist)
{
	assert(pplist);   // 保证：pplist指向实参plist
 
					  // 1. 空链表
	if (NULL == *pplist)
		return;
	else if (NULL == (*pplist)->next)
	{
		// 2. 链表中只有一个节点
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		// 3. 链表中有多个节点(至少是2个)
		// a. 找到最后一个节点并保存其前一个节点
		SListNode* cur = *pplist;
		SListNode* prev = NULL;   // 保存cur的前一个节点
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;
		}
 
		// cur是最后一个节点   prev刚好是cur的前一个
		free(cur);
		prev->next = NULL;
	}
 
}

单链表打印

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

单链表的头插

/将x插入到第一个节点之前----插入成功后x就是链表中第一个节点

//时间复杂度0（1）
void SListPushFront(SListNode** pplist, DataType x)
{
	//将x插入到第一个节点之前----插入成功后x就是链表中第一个节点
	assert(pplist);
	
	//申请一个新的节点
	SListNode* newNode = BuySListNode(x);
 
	if (*pplist == NULL)  //链表为空
	{
		*pplist = newNode;
	}
	else
	{
		newNode->next = *pplist;
		*pplist = newNode;
	}
}

单链表头删

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
 
	//空链表直接返回
	if (NULL == *pplist)
	{
		return;
	}
 
	//只有一个节点
	else if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
 
	//多个节点, delNode为要删除的节点
	else
	{
		SListNode* delNode = *pplist;//把第一个节点定义为要删除的节点
		*pplist = delNode->next; //让*pplist指向下一个节点
		free(delNode);
	}
}

单链表查找

//遍历整个链表，将x与结点中的值域进行比较，相等，直接改节点地址
    //如果不相等，继续往后便利 cur = cur->next，直到都没有，返回null

SListNode* SListFind(SListNode* plist, DataType x)  
{
	//遍历整个链表，将x与结点中的值域进行比较，相等，直接改节点地址
	//如果不相等，继续往后便利 cur = cur->next，直到都没有，返回null
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

任意位置插入

// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
//不带头节点的单链表，新节点无法插入到pos之前,而且我们不知道链表的第一个节点，无法遍历
//无法知道pos的前一个是谁,所以只能插入到pos之后

 
void SListInsertAfter(SListNode* pos, DataType x) //任意位置插入
{
	SListNode* newNode = NULL;
	if (NULL == pos)
		return;
 
	newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

任意位置的删除

// 单链表删除pos位置之后的值

// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos)  //任意位置的删除，实际删除pos之后的节点
{
	SListNode* delNode = NULL;
	//pos不为空且不是最后一个节点
	if (pos == NULL || pos->next == NULL)
		return;
 
	delNode = pos->next;
	if (NULL == delNode)
		return;
 
	pos->data = delNode->data;
	pos->next = delNode->next;
	free(delNode);
}

链表中所有的节点计数

int SListSize(SListNode* plist)  //当前链表中所有的节点计数
{
	SListNode* cur = plist;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
 
	return count;
}

单链表的销毁

void SListDestroy(SListNode** pplist)//单链表的销毁
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur)
	{
		*pplist = cur->next;
		free(cur);
		cur = *pplist;
	}
	*pplist = NULL;
}