数据结构-双链表-详解

1.前言

链表总共有八种：双向、单向；带头、不带头；循环、不循环。(8 = 2 * 2 * 2)

在前两篇博客中，我讲了单链表，具体来说，是 单向、不带头、不循环 的链表。
这种链表结构简单，使用复杂，常常是其他数据结构的子结构，在OJ题中会大量出现。
而常见的链表还有一个，就是今天要讲的 双向、带头、循环 的链表。
这种链表的特点是结构复杂，使用简单。如果有人让你二十分钟内搓出一个链表，那么它将是最优解。

2.结构

2.1双向

双向是什么？就是前一个结点能访问后一个结点，后一个结点也可以访问前一个结点。

相比于单向，双向可以倒着走了。
缺点也有，就是结构体中需要再创建一个指针变量，占用了更多的内存。

2.2带头

这个头不是指头指针，而是哨兵位的头结点，这种头结点不存储有效数据。
使用它的好处是插入时不用判断NULL的情况。
缺点是哨兵位的头结点有时候意义不大，单链表一般都不带头。

2.3循环

这个比较简单，就是指一个结点的next指向了前面的结点。
可以是这样：

也可以是这样：

甚至可以是这样：

今天讲的是头指尾的循环。

3.实现

3.1结构体

List.h:

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

只比单链表多了个指针。

3.2初始化与删除

初始化

这里需要创造一个哨兵位的头结点，且需符合 双向、带头、循环 的特点。

List.c:

ListNode* LTInit()
{
	ListNode* ListGuard;
	ListGuard = (ListNode*)malloc(sizeof(ListNode));
	if (!ListGuard)
	{
		perror("LTInit::malloc");
		return NULL;
	}
	ListGuard->prev = ListGuard;
	ListGuard->next = ListGuard;
	return ListGuard;
}

删除

List.c:

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

3.3插入

尾插

在单链表时，尾插需找尾，当链表为空时，还需传二级指针。
现在，不需要找尾，因为头结点的prev就是尾；不需传二级，且链表空不空方法一致，不用处理特殊情况。
思路：

这里需注意链接顺序，不然会丢失位置。
当然，如果创建临时变量，存储前后位置，那怎么弄都行。
代码挺简单的：
List.c:

void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* NewListNode = BuyListNode(x);
	NewListNode->prev = pHead->prev;
	NewListNode->next = pHead;
	pHead->prev->next = NewListNode;
	pHead->prev = NewListNode;
}

头插

方法和尾插差不多：
List.c:

void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* NewListNode = BuyListNode(x);
	NewListNode->next = pHead->next;
	NewListNode->prev = pHead;
	pHead->next->prev = NewListNode;
	pHead->next = NewListNode;
}

3.4删除

空链表当然不能删除，可以写个判空的函数：
List.c:

int ListEmpty(ListNode* pHead)
{
	assert(pHead);
	return pHead->next == pHead;
}

这里直接return条件判断的结果，大大简化代码。

尾删

List.c:

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));
	pHead->prev = pHead->prev->prev;
	free(pHead->prev->next);
	pHead->prev->next = pHead;
}

头删

List.c:

void ListPopFront2(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));
	ListErase(pHead->next);
}

3.4查找

List.c:

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	if (cur != pHead && cur->data != x)
	{
		cur = cur->next;
	}
	else return cur;
}

3.5pos位置的插入删除

思路大差不差，这里直接给代码。

List.c:

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* NewListNode = BuyListNode(x);
	NewListNode->next = pos;
	NewListNode->prev = pos->prev;
	pos->prev->next = NewListNode;
	pos->prev = NewListNode;
}
void ListErase(ListNode* pos)
{
	assert(pos);
	assert(!ListEmpty(pos));
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

现在有个值得注意的点了，即这两个函数完全可以代替头插尾插头删尾删，因此，又可以减少工作量了，只需写出这两个函数，然后就能开始套用：

void ListPushBack2(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead, x);
}
void ListPopBack2(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));
	ListErase(pHead->prev);
}
void ListPushFront2(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead->next,x);
}
void ListPopFront2(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));
	ListErase(pHead->next);
}

希望本篇文章对你有所帮助！并激发你进一步探索数据结构和算法的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！

相关文章：
数据结构-单链表-详解-1
数据结构-单链表-详解-2