本文是详解链表的基本使用方法，可流畅操作链表，功能上实现了顺序表的增删查改，这里特定位置的插入和删除可做头插尾插的特殊实现。

链表的优缺点🤔

一个实质性的问题就是为啥我们要用链表？

其实相对于我们之前的线性顺序表结构，链表的操作更为复杂，但是由于可以不用按顺序存储，链表在头尾插入时可以达到 O（1）的复杂度。

最主要的就是他可以克服像数组链表一样需要预先知道插入数据的大小才行，链表用多少就开多少，这样就可以使得计算机空间得到充分利用；但是同时他又失去了顺序表随机读取的优点，线性表的链式存储如果要找一个数，必须要从头开始找起，十分麻烦。

链表的分类🤔他们分别是，

链表不是简简单单的一个链表，他有8大结构分别是：

1. 单链表 or 双链表
2. 带头 or 不带头
3. 循环 or 不循环

单链表：

双链表：

带头结点单链表：

带头结点双链表：

循环单链表：

循环带头结点双链表：

带头循环双向链表虽然是链表中最复杂的结构，但它的代码操作却是最简单的，也是现实中实际运用最为广泛的一种。

单链表👏

表中每一个数据都包含两个部分，该元素和下一元素的地址，由下一元素的地址就能链接到各个元素从而形成“ 表 ”的结构，在表尾不需要在寻访下一元素时我们只需放入 NULL 即可。

那么首先我们就要定义一个结构体：

#pragma once 
typedef int Seqtype;
typedef struct Seqlist
{
 Seqtype data;
 struct Seqlist* Next;//下一节点的地址
}Seqlist;

尾插🤔

为了写起来方便，我把打印功能单独拿出来先定义好：

void print(Seqlist** plist)
{
	Seqlist* begin = *plist;
	while (begin!=NULL)
	{
		printf("%d->", begin->data);
		begin = begin->Next;
	}
	printf("无内容\n");
}

链表的特点就是要多少开多少，根据尾插的逻辑分析一下，那么在尾插之前我们需要先 malloc 一块空间出来，把要插的数据初始化好，再在已有链表结构中寻找尾节点进行插入即可。

void pushback( Seqlist** plist, Seqtype x)
{
	Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));
	node->data = x;
	node->Next = NULL;
	Seqlist* tail = *plist;
	if (tail == NULL)
	{
		tail = node;
	}//处理为空的特殊情况
	else
	{		
		while (tail->Next != NULL)
		{
			tail = tail->Next;
		}//寻找尾结点
		tail->Next = node;//插入数据
	}
}

==但是注意==，一上来就去找尾结点的话，因为在 test.c 里面 plist 已经被初始化成 NULL，那为了避免 tail 一上来就没了这种尬尴的情况，我们加入一个判断：

if(*plist == NULL)
{
*plist = node;
}
else
{
……//上面的pushback
}

动态申请节点🤔

因为考虑到要时常进行 malloc 开辟空间，所以我们单独拎出来写成一个函数方便调用：

Seqlist* newmalloc(Seqtype x)
{
	Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));
	node->data = x;
	node->Next = NULL;
	return node;
}

头插🤔

尾插一但明了了，其他的接口就是信手拈来，头插不需要挪数据，直接开辟空间就行。

void pushfront(Seqlist** plist, Seqtype x)
{
    assert(*plist);
	Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));
	node->data = x;
	node->Next = *plist;
	*plist = node;
}

因为头插会对首元素地址做出修改，plist 会因此更改，因此这里采用传址调用。

头删🤔

头删思路就是把打头的元素 free 掉，再把指向下一个元素地址的指针放入即可：

void popfront(Seqlist** plist)
{
	Seqlist* node = (*plist)->Next;;
	free(*plist);
	*plist = node;
}

尾删🤔

尾删思路同头删一个道理，遍历找到尾结点，将其free掉，但是这里需要一个处理：

我们在 free 掉最后一个元素后，其地址就不能访问，那么前一个节点存放的寻址指针就是一个野指针，所以需要双指针维护一个 NULL 的 Next 参数。其次还需注意当前链表是否为空或者只有一个元素。

void popback(Seqlist** plist)
{
    assert(*plist);
	if (*plist == NULL)
	{
		return;
	}
	else
	{
		Seqlist* pre = NULL;//跟进 tail 防止free后产生野指针
		Seqlist* tail = *plist;
		while (tail->Next != NULL)
		{
			pre = tail;
			tail = tail->Next;
		}
		free(tail);
		pre->Next = NULL;
	}
}

销毁链表🤔

结束时不要忘了销毁链表

void destroy(Seqlist** plist)
{
	assert(*plist);
	Seqlist* node = *plist;
	Seqlist* pre = *plist;
	while (node->Next == NULL)
	{
		if (pre->Next != NULL)
		{
			pre = pre->Next;
		}
		else
		{
			free(node);
			node = NULL;
			node = *plist;
		}
	}
	free(pre);
	pre = NULL;
}

任意位置插入🤔

void insert(Seqlist** plist, Seqtype x, Seqtype pos)
{
	assert(*plist);
	if (pos == *plist)
	{
		pushfront(plist,x);
	}
	else
	{
		Seqlist* node = newmalloc(x);
		Seqlist* pre = *plist;
		while (pre->Next != pos)
		{
			pre = pre->Next;
		}
		pre->Next = node;
		node->Next = pos;
	}
}

任意位置删除🤔

void erase(Seqlist** plist, Seqlist* pos)
{
	assert(*plist);
	if (*plist == pos)
	{
		popfront(plist);
	}
	else
	{
		Seqlist* pre = *plist;
		while (pre->Next != pos)
		{
			pre = pre->Next;
		}
		pre->Next = pos->Next;
		free(pos);
		pos = NULL;
	}
}

完整代码：

test.c：

# define _CRT_SECURE_NO_WARNINGS 
#include"Slist.h"
void test()
{
	Seqlist* plist = NULL;
	//增删查改自行组合
}
int main()
{
	test();
	return 0;
}

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int Seqtype;
typedef struct Seqlist
{
	Seqtype data;
	struct Seqlist* Next;//下一节点的地址
}Seqlist;

void pushback(Seqlist* plist, Seqtype x);//尾插
void pushfront(Seqlist** plist, Seqtype x);//头插
void print(Seqlist** plist);//打印链表
void destroy(Seqlist** plist);//销毁链表
void popfront(Seqlist** plist);//头删
void popback(Seqlist** plist);//尾删
void insert(Seqlist** plist, Seqtype x, Seqtype pos);//pos位置插入
void erase(Seqlist** plist, Seqtype pos);//pos位置删除
Seqlist* newmalloc(Seqtype);//开辟新节点

# define _CRT_SECURE_NO_WARNINGS 
#include"Slist.h"
void print(Seqlist** plist)
{
	Seqlist* begin = *plist;
	while (begin!=NULL)
	{
		printf("%d->", begin->data);
		begin = begin->Next;
	}
	printf("无内容\n");
}
void pushback( Seqlist** plist, Seqtype x)
{
	Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));
	node->data = x;
	node->Next = NULL;
	Seqlist* tail = *plist;
	if (tail == NULL)
	{
		tail = node;
	}
	else
	{		
		while (tail->Next != NULL)
		{
			tail = tail->Next;
		}
		tail->Next = node;
	}
}
void pushfront(Seqlist** plist, Seqtype x)
{
	Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));
	node->data = x;
	node->Next = *plist;
	*plist = node;
}
void popfront(Seqlist** plist)
{
	Seqlist* node = (*plist)->Next;;
	free(*plist);
	*plist = node;
}
void popback(Seqlist** plist)
{
	if (*plist == NULL)
	{
		return;
	}
	else
	{
		Seqlist* pre = NULL;
		Seqlist* tail = *plist;
		while (tail->Next != NULL)
		{
			pre = tail;
			tail = tail->Next;
		}
		free(tail);
		pre->Next = NULL;
	}
}
Seqlist* newmalloc(Seqtype x)
{
	Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));
	node->data = x;
	node->Next = NULL;
	return node;
}

void destroy(Seqlist** plist)
{
	assert(*plist);
	Seqlist* node = *plist;
	Seqlist* pre = *plist;
	while (node->Next == NULL)
	{
		if (pre->Next != NULL)
		{
			pre = pre->Next;
		}
		else
		{
			free(node);
			node = NULL;
			node = *plist;
		}
	}
	free(pre);
	pre = NULL;
}
void insert(Seqlist** plist, Seqtype x, Seqlist* pos)
{
	assert(*plist);
	if (pos == *plist)
	{
		pushfront(plist,x);
	}
	else
	{
		Seqlist* node = newmalloc(x);
		Seqlist* pre = *plist;
		while (pre->Next != pos)
		{
			pre = pre->Next;
		}
		pre->Next = node;
		node->Next = pos;
	}
}
void erase(Seqlist** plist, Seqlist* pos)
{
	assert(*plist);
	if (*plist == pos)
	{
		popfront(plist);
	}
	else
	{
		Seqlist* pre = *plist;
		while (pre->Next != pos)
		{
			pre = pre->Next;
		}
		pre->Next = pos->Next;
		free(pos);
		pos = NULL;
	}
}