系列文章目录

前言

顺序表的问题及思考
问题：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：
如何解决以上问题呢？下面给出了链表的结构来看看

一、链表的概念及结构

1.链表的概念

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

2.链表的结构

链表包括数据域和指针域：

数据结构中：

二、链表的种类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向
2. 带头、不带头
3. 循环、非循环

4. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
5. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

三、链表的实现

1.自定义链表结点struct SListNode

代码如下：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;          //数据域
	struct SListNode* next;   //指针域
}SLTNode;

2.链表打印数据SListPrint

代码如下：

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

3.链表创建结点BuyListNode

代码如下：

SLTNode* BuyListNode(SLTDateType num)                     //创建一个结点
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	assert(node);
	node->data = num;
	node->next = NULL;
	return node;
}

4.链表尾部插入数据SListPushBack

代码如下：

void SListPushBack(SLTNode** pplist, SLTDateType num)     //尾部插入数据,会改变第一个结点，所以传二级指针
{
	assert(pplist);
	SLTNode* newnode = BuyListNode(num);                  //创建一个新结点
	if (*pplist == NULL)                                 //考虑当前一个结点都没有情况
	{
		*pplist = newnode;
	}
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next != NULL)  //遍历找到尾结点
		{
			tail = tail->next;
		}
		tail->next = newnode;  //把新结点的地址给前一个结点的指针
	}
}

5.链表头部插入数据SListPushFront

代码如下：

void SListPushFront(SLTNode** pplist, SLTDateType num)
{
	assert(pplist);
	SLTNode* newnode = BuyListNode(num);
	newnode->next = *pplist;
	*pplist = newnode;
}

6.链表尾部删除数据SListPopBack

代码如下：

void SListPopBack(SLTNode** pplist)
{
	//1.没有结点
	//2.1个结点
	//3.多个结点
	if (pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(pplist);
		*pplist = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

7.链表头部删除数据SListPopFront

代码如下：

void SListPopFront(SLTNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}

8.链表查找数据SListFindKey

代码如下：

SLTNode* SListFindKey(SLTNode* plist, SLTDateType num)
{
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == num)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

9.链表在pos位置之后插入数据SListInsertAfter

代码如下：

void SListInsertAfter(SLTNode* pos, SLTDateType num)
{
	assert(pos);
	SLTNode* newnode = BuyListNode(num);
	newnode->next = pos->next;
	pos->next = newnode;
}

10.链表在pos位置之前插入数据SListInsertBefore

代码如下：

void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDateType num)
{
	assert(pos&&pplist);	
	SLTNode* newnode = BuyListNode(num);
	if (pos == *pplist)
	{
		newnode->next = pos;
		*pplist = newnode;
	}
	SLTNode* prev = NULL;
	SLTNode* cur = pplist;
	while (cur != pos)
	{
		prev = cur;
		cur = cur->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}

11.链表在pos位置之后删除数据SListEarseAfter

代码如下：

void SListEarseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* cur = pos->next;
		pos->next = cur->next;
	}
}

总结

以上就是今天要讲的内容，本文仅仅简单介绍了链表的各种方法的实现，而链表提供了方法能使我们快速便捷地处理数据的函数和方法，我们务必掌握。另外，如果有需要源码的私信我即可。还有，，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。