单链表详解（1）

一、顺序表的弊端

1.往顺序表中间插入元素时时间要移动顺序表的一部分，当顺序表足够大时，这时时间复杂度会时O(n),运行效率会降低；

2.顺序表在空间不够时增容用到realloc函数，这个函数需要拷贝原数据，申请新空间，释放旧空间，这也降低了运行效率；

3.顺序表增容后可能存在空间浪费的问题。

基于此我们引入了链表的概念。

二、单链表的定义

链表是线性表的一种，链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑结构是通过链表中的指针链接次序实现的

单链表的结构：

单链表就像是一节一节车厢构成的火车，每一节都称为一个节点，节点里面有两部分：数据域和指针域；指针域指向的是下一个节点的地址，依次类推；

struct SListNode
{
    int data;
    struct SListNode* next;
}

通过next指针我们可以从头一直访问到最后一个节点。

三、单链表的实现

1、头文件

#pragma once

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

typedef int SLTDataType;

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

//单链表的打印
void SLTPrint(SLTNode* phead);

//申请一个节点
SLTNode* SLTBuyNode(SLTDataType x);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找节点
SLTNode* SLTNodeFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsertFront(SLTNode** pphead, SLTNode* pos,SLTDataType x);

//在指定位置之后插入数据
void SLTInsertBack( SLTNode* pos, SLTDataType x);

//删除指定位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除指定位置之后的数据
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SLTDestroy(SLTNode** pphead);

单链表中的数据域 不一定是int型，可能时其他类型，为了方便适应不同情况，我们将单链表中的数据同意重命名为SLTDataType

 测试中定义的单链表是SLTNode* plist=NULL；将这个作为实参传入函数，但是涉及到链表的修改我们需要传地址，所以在函数声明时用到二级指针。

2、函数定义

单链表的打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}


void test01()
{
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
	SLTPrint(plist);
}
int main()
{
	test01();
	return 0;
}

运行结果：

在这里我们先看到test01里面的内容，这里手续开辟了四个节点的空间，并且给每一个节点的数据域赋值，最后按照顺序利用它们各自的next指针将它们连接在一起；plist代表的是头节点是node1的链表；

接着看到SLTPrint函数：传plist，不需要传地址，打印不涉及到修改；用phead接收，代表链表的头节点，再定义一个pcur代表在遍历过程中此刻是哪个节点；进入循环，最开始是头节点，我们打印它的数据也就是1，然后pcur=pcur->next 表示这个时候pcur成为了第二个节点，因为pcur->next存储的是第二个节点的地址，赋值给pcur就实现了链表节点的遍历，依次打印并且遍历节点，最后到最后一个节点打印完4之后pcur被赋值为NULL，因为最后一个节点的指针域指向的内容NULL；然后循环结束，这样就实现了单链表的打印。

申请节点

上面在打印链表的时候为了方便引入和展示我们是手续申请的节点，实际上，节点的申请只是在需要申请的时候去申请一个，这恰好也是单链表的优点所在，介绍如下：

//申请一个节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

我们在申请节点时，要传入指定的数据作为节点的数据域，在函数内部，定义一个新节点newnode并且使用malloc函数开辟空间，判断开辟是否成功，成功之后，给newnode数据域赋值为传入的数据，再把指针域赋值为NULL，最后返回这个新节点。

单链表尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;//找到最后一个节点
		}
		ptail->next = newnode;
	}
}

尾插传入的是plist的额地址，用二级指针接收，首先断言看pphead是否为空，接着给要尾插的数据申请一个新的节点。尾插时存在两种情况，一是这个链表*pphead是空的，对于空链表直接赋值就行，此时这个新节点也成为了头节点；二是尾插时链表不是空的，那么我们需要先找到尾节点，定义一个节点ptail表示要去找到的尾节点，利用循环通过next去移动此时可以操作到的节点，注意循环条件是ptail->next 因为如果是ptail作为条件最后ptial是NULL而不是最后一个节点，当ptail->next指向NULL时，循环结束，此时ptail就是尾节点，因为在一条单链表中只有尾节点的指针域为NULL。

相关测试：

链表为空时：

 链表不为空时

 单链表头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode=SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插在单链表头部插入，此时头节点发生改变，我们使newnode的next指向*pphead，让newnode插入链表并且在称为新的第一个节点，再将*pphead赋值为newnoded，完成新的头节点的设置；

注意此时就算原链表是空的，我们这样写也能确保正常的插入（newnode的next指向NULL；newnode称为新的头节点，指针域是NULL）

相关测试：

 单链表尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	
	else
	{
        SLTNode* ptail=*pphead;
	    SLTNode* pre = *pphead;
		while (ptail->next)
		{
			pre = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		pre->next = NULL;
	}
}

首先单链表要进行删除操作，要先保证单链表不为空（*pphead！=NULL）

如果单链表只有一个节点那么就直接释放头节点并赋为NULL；若是不为空我们需要找到尾节点以及尾节点之前的节点，因为除了要释放最后一个节点之外还要把倒数第二个节点的next置为空；利用循环，当ptail成为最后一个节点时，pre在ptail赋值操作之前那么pre就是倒数第二个节点。找到这两个结点之后，释放尾节点，并赋为空，最后将倒数第二个节点的next赋为空。

单链表头删

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

头删会把头节点释放，如果不提钱存放头节点直接释放的话之后就找不到链表后面的节点了，所以先定义一个next节点保存头节点的下一个节点。在释放完头节点之后，让下一个节点成为新的头节点。