数据结构-双链表-详解

本文主要是介绍数据结构-双链表-详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构-双链表-详解

1.前言
2.结构
- 2.1双向
- 2.2带头
- 2.3循环
3.实现
- 3.1结构体
- 3.2初始化与删除
- - 初始化
  - 删除
- 3.3插入
- - 尾插
  - 头插
- 3.4删除
- - 尾删
  - 头删
- 3.4查找
- 3.5pos位置的插入删除

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