数据结构详解：双向、带头、循环链表
数据结构详解：双向、带头、循环链表
双链表是一种常见的数据结构，相比于单链表，它具有结构复杂但使用简单的特点。本文将详细介绍双向、带头、循环链表的结构特点和实现方法，并通过具体的代码示例帮助读者更好地理解双链表的实现原理。
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;
}
尾删
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);
}
希望本篇文章对你有所帮助！并激发你进一步探索数据结构和算法的兴趣！