[数据结构与算法](数据结构) 链表

（数据结构）链表

在学习完上一篇顺序表之后，欢迎来到另一种线性表——链表。

🐧一、单链表

作为最简单的链表结构，我们通过它来打开链表的大门。

1. 介绍

   链表，在结构上类似于链条，是通过指针将每一个节点连接起来，呈线性结构。
   

2. 由上图，可以设计出它的结构体SListNode

   typedef int SLTDateType;//需要存储的数据类型
   typedef struct SListNode
   {
   	SLTDateType data;		//数据
   	struct SListNode* next;	//指针
   }SListNode;
   

   用int作为存储类型来进行演示。

3. 特点

   *每一个节点都是单独从堆中申请出来的，因此它们的空间可能不连续。

   *对于链表的节点的访问都是通过头指针pList进行的，用->next向后进行移动。

4. 使用
   对于数据结构的使用，无疑就是常见的增删查改

🦉4.1创建节点

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)//申请空间失败
	{
		perror(BuySListNode);
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

很多函数可能都会用到创建节点，不妨将它单独写成一个BuySListNode()

🦆4.2打印链表

// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}

cur从头结点开始，先显示data，再想下一个结点移动，直至到最后一个结点的data输出，cur移动到NULL退出。

🦔4.3 尾插

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);//传入参数非空
	if (*pplist == NULL)//头节点
	{
		*pplist = BuySListNode(x);
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = BuySListNode(x);
	}	
}

尾插思路很好理解，先找到链表最好的一个节点，即tail->next == NULL的节点，然后将新节点连接到它的后面。

但是还有一个问题要考虑，当插入的是第一个结点，此时调用SListPushBack()的函数中，变量SListNode* pList的值还为空，

如果想要改变pList的值，即让它指向头节点，我们知道如果传地址的话，可以修改该变量的值。

代码中pplist是pList的地址，通过对地址的解引用操作，*pplist = BuySListNode(x);，来更改pList所在地址的空间中的内容，把NULL改为头节点的地址。

当然，这里还有另一种思路，写成SListNode* SListPushBack(...),在运行时记录头节点，结束时返回，此时调用函数的操作为SListNode* pList = SListPushBack(...)。

🐘4.4 尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{

	assert(pplist);//传入非空
	assert(*pplist);//传入链表非空
	SListNode* tail = *pplist;
	if (tail->next == NULL)
	{
		free(tail);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

尾删的思路，同尾插类似，先找到尾，然后进行删除，对于只剩一个节点的尾删，也需要更改pList的内容，防止野指针的错误。其他情况也需要将新尾结点（原倒数第二个结点）的next置空。用prev记录上一个的结点，prev->next = NULL;。

🐿?4.5 头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);//传入非空
	SListNode* next = *pplist;//记录原来的头结点
	*pplist = BuySListNode(x);

	(*pplist)->next = next;
}

🦬4.6 头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* next = *pplist;//记录原来的头结点
    free(*pplist);
	*pplist = next;
}

头插和头删的思路都是删除头结点后，再把原第二个结点改成头结点。

5. 建议

   其实在进行单链表操作的时候，可以在演草纸上画出类似1.的草图，操作的思路都是很简单的的，需要注意

   • 指向头结点的指针pList的更改
   • 链表尾的next要=NULL

🐸二、带头双向循环链表

上例中的单链表，结构简单，但是进行一些操作还是不太方便，甚至感觉还没顺序表实用。其实单链表一般不会单独使用来存数据，而是做为其他数据结构的子结构。

本节的带头双向循环链表，是最复杂的链表结构了，因此也比较完善，一般单独的存储数据。

1. 介绍
   
   带头(head)：head并不存储数据，而是为了保证指向该链表的指针不用更改了（类似于上例中的pList)，因为不会对head结点进行操作。

   双向循环：一个结点有两个指针，一个指向它的前一个结点，另一个指向它的后一个结点。并构成循环结构（无NULL）。

2. 它的结构体设计如下

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

3. 实现
   虽然它的结构看起来好复制，但是请继续向下看，你会发现它的操作非常简单的。

🐹3.1 创建节点

// 创建节点
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

🐰3.2 初始化

因为有头结点，使用开始的时需要先创建头结点

// 初始化
LTNode* ListInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;//循环
	phead->prev = phead;

	return phead;
}

🐻3.3打印

与单链表不同，它没有NULL来判断结束。

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

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

cur从存储数据的结点开始，输出data，然后向下一个结点移动，直到循环到head结点时退出。

🐻???3.4 插入

在pos位置前插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;
}

🐨3.5删除

删除pos位置的节点

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

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

插入和删除的操作都很简单，用pos,next,prev分别指向要修改的结点，然后进行操作就哦了。什么的next->什么，什么的prev->什么，没有先后要求，只要写完整就哦了。

🐼3.6其他

//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}
//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	ListErase(phead->prev);
}
//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->next);
}

🦊总结

对于链表的操作，简述了一下插入，删除的操作。还有查找函数可以自己实现嘛，就不贴代码了，本篇已经太冗长了。

链表的思路很简单，如果在代码实现过程中出现了错误，不妨画个简图，帮助理解，或者发现有什么步骤少了。

🦀🦀观看。

待续~~

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖