😀作者：江不平
📖博客：江不平的博客
📕学如逆水行舟，不进则退
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❀本人水平有限，如果发现有错误的地方希望可以告诉我，共同进步👍

🏐1.链表是什么

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

链表有很多结构，单向或者双向，带头或者无头，循环或者非循环，各种情况组合起来共有8种链表结构，当然常用的还是两种。

1. 无头单项不循环链表
   就是我们常说的单链表，结构简单，一般不会单独用来存数据。实际中常常作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 双向循环链表
   结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

🏐2.单链表

根据链表的概念，我们可以创建这样的一个结构体，为了方便我们使用typedef进行类型重定义

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//通过指针进行连接
}SLTNode;

为了跟顺序表是一样方便查看效果，先写一个Print函数

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//遍历打印
	while (cur!=NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;//通过指针进行连接
	}
}

🏀增

增加数据就是进行插入，不管是怎么插入我们都需要开辟一个新的结点，然后存放数据进行连接插入，既然这样，我们再写一个创建新结点的函数

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);//进行常规检查，要求不为NULL
	newnode->data = x;//创建新结点后要初始化
	newnode->next = NULL;
	return newnode;
}

跟顺序表类似，我们先看表头插入

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;//更改表头
}

表头插入比较简单，建立一个新结点后，让新结点的next存储表头地址，更换新的表头即可
表尾插入

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

任意位置插入
任意位置插入，这时侯就会想到有两种情况，在指定位置之前插入和在指定位置之后插入，我们一个一个看，先看Pos前

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

	// 头插
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		//找插入位置的前一个位置
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

指定位置之后插入

oid SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	//第一种写法
	// pos newnode next三者间的连接顺序要好好考虑
	/*SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;*/

	// 不在乎链接顺序,先把数据存起来
	SLTNode* newnode = BuySListNode(x);
	SLTNode* next = pos->next;
	
	pos->next = newnode;
	newnode->next = next;
}

我们可以看到在指定位置之后插入比之前插入要简单

🏀删

头删

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

尾删

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	// 1、只有一个节点
	// 2、多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;*/
		//我们要学习上面这种将数据存起来的方式，可以让我们的代码更简洁，我第一次写写成了下面这种
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}	
}

任意位置删除
找指定位置前一个结点

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;

		free(pos);
		pos = NULL;//这里置不置空都可，但这是个好习惯，建议加上
	}
}

找指定位置后一个结点

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
		return;
	//下面这里也是，把数据再存起来，方便使用而且简洁
	SLTNode* del = pos->next;
	//pos->next = pos->next->next;
	pos->next = del->next;

	free(del);
	del = NULL;
}

很多地方都给出了不止一种写法，具体看代码注释

🏀查

查找是我们接口组合的重要部分，具体实现如下

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}
	return NULL;
}

🏀改

改的话就比较简单了，直接进行修改即可，这里就不写了

🏐3.带头双向循环链表

• 双向链表其实是单链表的改进。

• 当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
• 在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

定义之后别忘了初始化链表

LTNode* ListInit()
{
    LTNode* phead = BuyNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

🏀增

同样的为了查看各接口的效果，先写一个Print函数，很容易可以想到与单链表的打印基本一样，没有不同，因为指向前置结点的指针在这里派不上用场

void ListPrint(LTNode* phead)
{
	assert(phead);

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

废话不多说，直接来看
表头插入

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	LTNode* nextnode = phead->next;

	newnode->next = nextnode;
	newnode->prev = phead;
	phead->next = newnode;
	nextnode->prev = newnode;
	
	//ListInsert(phead, x);//当我们写完任意位置插入后，就可以直接调用啦
}

表尾插入

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
    LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

	//ListInsert(phead, x);//当我们写完任意位置插入后，就可以直接调用啦

}

任意位置插入

// 在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);

	// prve newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

🏀删

表头删除

void ListPopBack(LTNode* phead)
{
	assert(phead);
    assert(phead != phead->next);//没有数据肯定不能删除，所以要进行判断，会不会是空链表
	//assert(!ListEmpty(phead));这里两种判断空链表方法都可以
	LTNode* next = phead->next;
	free(tail);
	next->prev = phead;
	phead->next = next;
}

表尾删除

void ListPopBack(LTNode* phead)
{
	assert(phead);
    assert(phead != phead->next);//没有数据肯定不能删除，所以要进行判断，会不会是空链表
	//assert(!ListEmpty(phead));这里两种判断空链表方法都可以
	LTNode* tail = phead->next;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
}

任意位置删除

//  删除pos位置的节点
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
}

有了任意位置的插入删除，我们就可以在链表头部和尾部插入删除的时候直接调用啦

因为我们经常遇到判断该链表是否为空链表的情况，我们干脆写一个判空函数Empty

bool ListEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

不过要记住调用该函数时，需要把该函数的定义放在前面，不然会报错

🏀查

ListNode* ListFind(ListNode* plist, LTDataType x)；

与单链表一样即可，指向前置结点的指针在这个地方没起到什么作用

🏀改

与单链表一样，直接修改即可

🏐4. 链表的销毁和数据元素的统计

单链表和双向循环链表的销毁和数据元素的统计基本一致，只是命名上和判断条件的不同，指向前置结点的指针在这个地方也没起到什么作用
链表的销毁

//单链表
void SLTDestory(SLTNode* plist)
{
	assert(plist);
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
}
//双向循环链表
void ListDestory(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)//双向循环链表没有指向NULL的指针
	{
		free(cur);
		cur = cur->next;
	}
	free(phead);
}

数据元素的统计

单链表
int size(SLTNode* phead)
{
	assert(phead);
	int size = 0;
    SLTNode* cur = phead;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
双向循环链表
int size(LTNode* phead)
{
	assert(phead);
	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

🏐5.一些小点

1. 可以看到单链表进行插入和删除的时候，找指定位置前一个结点的做法显得麻烦了许多，时间复杂度为O(n),所以实现的时候实际上一般都找后一个结点,时间复杂度为O(1)。
2. 可以看到双向循环链表在进行删除的时候，提前将pos前后位置的数据进行了存储，这样我们在free的时候就不用考虑顺序了，不容易出错，不然的话就要连接完之后再进行free。
3. 链表因为它的物理地址不连续的特点，使得它的缓存利用率并不高，虽然它在任意删除插入数据很方便，使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
4. 看过上一篇文章的伙伴就知道顺序表和链表是相辅相成的，二者各有优缺点，在我们实际应用时根据特点选择合适的结构就好。

这就是线性表第二关链表的相关内容了，看到这里觉得还不错的兄弟点赞关注一下吧😀