【落羽的落羽 数据结构篇】双向链表

一、链表的分类

链表的分类实际上要从这三个方向分析：是否带头、单向还是双向、是否循环。

“带头”指链表是否有“头节点”，并不指链表的第一个节点，而是一个不存储有效数据的“哨兵位”，作用仅仅是表明链表的起始点。上次讲的单链表中我们说的“首节点”，只是链表的第一个存储数据的节点，并不是头节点，这个单链表是没有头结点的。

单链表是单向链表，也存在双向链表，也就是这种链表的节点有两个指针成员，一个指向下一个节点、一个指向上一个节点。

循环就很好理解了，节点的指针成员循环指向。

所以，理论上我们能把链表分为2×2×2=8种：带头单向不循环链表、不带头双向不循环链表、带头双向循环链表……
上次我们学习的“单链表”，全称应该就是“不带头单向不循环链表”。而我们这次要学习的“双向链表”，全称是“带头双向循环链表”。这两种链表也是最常用的两种。

二、双向链表

1. 结构

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

这是双向链表的每一个节点的结构。next指针指向下一个节点，prev指针指向上一个节点。
值得注意的是，单链表为空时，链表一个节点都没有；双向链表为空时，它仍有一个哨兵位，如果连哨兵位都没有的话，这不是双向链表而是单链表。同时，这个哨兵位的next指针和prev指针都是指向自己的。

2. 申请一个新节点

LTNode* BuyNode(LTDataType x)
{  
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

测试：

3. 尾部插入数据

这里的“尾部”，是头结点的prev指针指向的位置

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	newnode->next = phead; //新尾结点的next指向头结点
	newnode->prev = phead->prev; //新尾结点的prev指向原尾结点
	phead->prev->next = newnode; //原尾结点的next指向新尾结点
	phead->prev = newnode; //头结点的prev指向新尾结点
}

测试：

4. 头部插入数据

“头部”是头结点的next指向的位置

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

测试：

5. 尾部删除数据

void LTPopBack(LTNode* phead)
{
	assert(phead != phead->next); //保证原链表不为空，否则无数据可删
	LTNode* del = phead->prev; //要删除的节点设置成del
	del->prev->next = phead; //del的前一个节点的next指向头结点
	phead->prev = del->prev; //头结点的prev指向del的前一个节点
	free(del);
	del = NULL;
}

测试：

6. 头部删除数据

void LTPopFront(LTNode* phead)
{
	assert(phead != phead->next);
	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

测试：

7. 在指定位置之后插入数据

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

测试：

8. 删除指定位置节点

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

测试：

9. 销毁链表

void LTDestory(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

测试：

本篇完，感谢阅读