对于上一篇文中说到的顺序表，我们不难发现，它本身有很多限制

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

为了解决这些问题，我们给出了新的数据结构——链表。 

目录

二、线性表的链式结构——链表

1.链表的分类

2.链表的实现

（1）单链表的接口实现

（2）带头双向循环链表的接口实现

二、线性表的链式结构——链表

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

1.链表的分类

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

1.单向或者双向

 2.带头或者不带头

3.循环或者非循环 

虽然有这么多种链表，但是最常用的只有两种：

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

2.链表的实现

（1）单链表的接口实现

1.存储结构

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

2.初始化与销毁

由于链表的结构是由连接起来的节点组成的，所以我们并不需要对其进行初始化。

链表的每一个节点都是单独malloc出来的，因此我们要销毁这些节点，只能遍历链表，依次释放。将链表释放完毕以后，最好将指向链表头节点的指针置空，防止野指针。

void SListDestroy(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur)//遍历并销毁
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;
}

3.插入数据

插入数据也可以分为头插、尾插、在任意位置前插入，在任意位置后插入。但是不管是在哪里插入，都是需要动态申请一个节点的，然后根据插入位置不同链接不同，所以我们把申请节点封装成一个函数

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

 将需要的数据放入节点内部，然后执行插入操作的时候只需要将新节点链接上链表即可

• 头插

头插就是让新节点做头，新节点的next指向链表原来的头。

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

• 尾插

在单链表的最后一个节点后面插入一个新节点，我们需要遍历找到单链表的尾结点，然后将新节点链接上去

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)//判断是否为第一个节点
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)//找尾结点
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

• 在任意位置之前插入

要在pos位置之前插入数据，我们需要找到pos位置之前的节点指针prev，然后在prev的位置之后插入新节点，原理与尾插相同。但是当传入的pos位置为头节点的时候，需要把情况单独拿出来说，传入头节点本质上就是头插，因此直接调动头插函数即可。

void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(pos);
	if (pos == *pplist)
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)//找pos的前一个节点
		{
			prev = prev->next;
			assert(prev);//暴力检查pos传错了的情况
		}

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

• 在任意位置之后插入

由于已经传入一个位置pos，并且在pos后面链接，所以原理与尾插相同。

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

4.删除数据

• 头删

头删数据需要改变头节点，所以定义一个del指针存放需要删除的节点，然后改变头节，最后释放del指向的节点。

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* del = *pplist;
	*pplist = (*pplist)->next;
	free(del);
	del = NULL;
}

• 尾删

对于一个正常的单链表，删除尾节点，首先需要找到尾，找到尾节点并记录前一个结点，将尾节点释放，然后将尾节点的前一个节点置空，但是对于只有一个元素的节点的情况，需要单独考虑，将该节点的指针指向的next置空，然后释放该节点即可。

void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next != NULL)//找到尾结点的前一个结点
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

• 在任意位置删除

首先判断要删除的是否为头节点，如果是，直接调用头删函数，如果不是，那么就遍历链表，找到pos指针的前一个节点prev，然后将prev和pos的下一个节点链接起来，然后删除prev即可。

void SListEraseAfter(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	if (pos == *pplist)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* tmp = prev->next;
		prev->next = prev->next->next;
		free(tmp);
		tmp = NULL;
	}
}

5.打印链表

定义cur指针遍历链表，逐个访问数据，这里为了更加形象，在每个数据之后加上了->符号。

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

6.查找数据 

遍历链表，逐个与需要查找到数据对比，如果与我们需要查找到数据相同，就返回该节点地址，否则返回NULL

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

（2）带头双向循环链表的接口实现

1.存储结构

双向链表和单列表的区别就是双向链表多一个指向前一个节点的指针prev，结构如下图：

typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

2.初始化与销毁

• 初始化

带头链表的初始化就是新建一个哨兵位头节点，后面对链表进行操作的时候直接传头节点即可，此时链表内没有元素，所有哨兵位的prev指向自己，next也指向自己。

ListNode* ListCreate()
{
	ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
	if (guard == NULL)
	{
		perror("BuyListNode");
		exit(-1);
	}
	guard->_next = guard;
	guard->_prev = guard;
	return guard;
}

• 销毁

由于增加节点的时候是一个一个的malloc的所有销毁的时候也是一个一个的释放，那么定义一个cur指针，遍历链表，依次free，最后free掉哨兵位。

void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	ListNode* next = NULL;
	while (cur != pHead)
	{
		next = cur->_next;
		free(cur);
		cur = next;
	}
	free(pHead);
    pHead = NULL;
}

3.插入数据

每一次插入数据都需要创建新节点，因此封装一个BuyListNode函数，用于创建新节点

ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("BuyListNode");
		exit(-1);
	}
	newnode->_next = NULL;
	newnode->_prev = NULL;
	newnode->_data = x;
	return newnode;
}

• 头插

创建新节点，链接在guard的下一个节点位置。将nownode的prev指向guard。

void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	newnode->_next = pHead->_next;
	pHead->_next->_prev = newnode;

	pHead->_next = newnode;
	newnode->_prev = pHead;

}

• 尾插

在单链表里，进行尾插的时候，需要先找到尾，但是对于双向链表，他的guard节点指向的prev就是尾节点，就可以省略了找尾节点的过程，然后将newnode节点链接上即可

void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = pHead->_prev;
	tail->_next = newnode;
	newnode->_prev = tail;

	pHead->_prev = newnode;
	newnode->_next = pHead;
}

• pos位置之前插入

在pos位置之前插入就需要在用用prev记录pos的前一个节点，然后创建一个新节点，并链接在链表上即可。

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->_prev;
	ListNode* newnode = BuyListNode(x);
	prev->_next = newnode;
	newnode->_prev = prev;

	newnode->_next = pos;
	pos->_prev = newnode;
}

4.删除数据

在删除节点的时候，要保证删除的不能是哨兵位节点，所以这里封装一个判空函数判断链表里是否只有一个头节点，返回bool值。

bool ListEmpty(ListNode* pHead)
{
	assert(pHead);
	return pHead->_next == pHead;
}

• 头删

首先要判断传入的指针是否有效，链表是否为空，头删删除的是哨兵位的下一节点，那么我们定义一个del保存guard的next节点，然后将del节点取下来，将其他guard与del的下一节点链接起来，然后释放del节点。

void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));
	ListNode* del = pHead->_next;

	pHead->_next = del->_next;
	del->_next = pHead;

	free(del);
	del = NULL;
}

• 尾删

首先判断指针有效性，然后判空。尾删本质上删除的是guard的前一个节点，所以我们先定义一个tail保存尾节点，然后取下来tail节点，将其他的节点链接起来，然后释放tail节点。

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));
	ListNode* tail = pHead->_prev;

	tail->_prev->_next = pHead;
	pHead->_prev = tail->_prev;
	free(tail);
	tail = NULL;
}

• 删除pos位置的节点

删除该节点，直接将pos位置的节点的前一个节点和后一个节点链接起来，然后释放pos位置即可。

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->_prev->_next = pos->_next;
	pos->_next->_prev = pos->_prev;
	free(pos);
	pos = NULL;
}

5.查找数据

遍历链表，并与需要查找的数据对比，匹配之后返回该节点地址，否则返回空指针。

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		if (cur->_data == x)
			return cur;
		cur = cur->_next;
	}
	return NULL;
}

6.打印数据

遍历链表，依次打印数据，这里为了更加形象，在每个数据后面加上'<=>'符号。

void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	printf("guard<=>");
	while (cur != pHead)
	{
		printf("%d<=>", cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}