目录

序章、链表的分类

一、节点的定义

二、初始化一个链表

三、对链表进行头插

创建一个新结点

 我们要在这两个结点间插入新结点，用如下的方式：

 四、对链表进行尾插

五、对链表头删

判断链表是否为空

 头删函数

六、对链表进行尾删

七、对链表进行查找

八、链表某个位置前插入

九、删除某个链表

十、销毁链表

---

很多同学觉得单向链表已经够用了，平时写题目也都是单链表。但是我在这里要提醒的恰恰相反，单链表的实用性以及普遍程度在真正需要链表的时候是远不如双向链表的。

这篇文章将讲述的是关于双向链表的知识点，在这篇文章里面学到的函数、命名习惯可能与流通中的书籍有点区别，但是是根据往后要学习的数据库书写的，对于日后的学习以及使用很有帮助。

序章、链表的分类

链表可分为一下几种

3. 循环或者非循环

1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结

构的子结构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。

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

一、节点的定义

我们这里学习的是最复杂最实用的链表，带头双向循环链表

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

双向链表顾名思义，每个节点都有两个指针，分别指向前面和后面。

二、初始化一个链表

当我们差滚见一个链表的时候，会需要这个函数帮我们创建一个头结点，我们在函数外面接受这个头结点的地址就可以直接使用了，这里用到了一个很巧妙的结构，在后面会有妙用。

LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
	return guard;
}

 这个结构可以帮助我们在很多时候不用单独写出一段代码应对某个情况。

三、对链表进行头插

对链表都差我们需要先创建一个节点

创建一个新结点

LTNode* BuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

 我们要在这两个结点间插入新结点，用如下的方式：

定义一个first再分别改动指针。

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* first = phead->next;
 
	phead->next = newnode;
	newnode->prev = phead;
 
	newnode->next = first;
	first->prev = newnode;
 
}

考虑一个问题，当链表为空指针的时候，也就是如下的结构，需不需要单独列出来一种情况。

就会变成一下的样子：

并没有不满足我们链表的情况，所以我们不需要单独列出情况，尾插也是同理。

 四、对链表进行尾插

多亏了双向的这个结构，尾插和头插一样的简洁了。相比于单向链表，简单太多了。

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;
 
}

五、对链表头删

判断链表是否为空

当链表为空的时候，我们是不可以删除的。 

所以我们需要一个函数判断链表是否为空

bool ListEmpty(LTNode* phead)
{
	assert(phead);
	//if (phead->next == phead)
	//	return true;
	//return false;下面这种写法更简洁
	return phead->next==phead;
 
}

 头删函数

也不复杂，用两个指针理清楚关系就行。

void ListPopFrint(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = first->next;
 
	phead->next = second;
	second->prev = phead;
 
	free(first);
	first = NULL;
}

六、对链表进行尾删

与上面的思路一致

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* prev = phead->prev;
	LTNode* tail = prev->prev;
 
	phead->prev = tail;
	tail->next = phead;
 
	free(prev);
	prev = NULL;
}

七、对链表进行查找

思路也不复杂。

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur!=phead)//当cur再次到达头结点才是终结
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

当链表为空的时候，cur是无法进入循环的，直接返回NULL。

八、链表某个位置前插入

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
 
	prev->next = newnode;
	newnode->prev = prev;
 
	newnode->next = pos;
	pos->prev = newnode;
}

九、删除某个链表

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
 
	prev->next = next;
	next->prev = prev;
	free(pos);
}

十、销毁链表

void ListDestory(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
 
	free(phead);
 
}