双向链表（8.2）

双向链表（8.2）"/>

双向链表（8.2）

我们实际中最常用的两种链表结构：

1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结 构的子结构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。 2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

双向循环链表的实现：

1.开辟节点

// 创建节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(-1);}//给节点的数据赋值node->data = x;node->next = NULL;node->prev = NULL;return node;
}

2.初始化

初始化需要改变头指针，我们可以先择传二级指针，或者函数返回新的头节点。

//双向链表初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);//前后与自己链接phead->next = phead;phead->prev = phead;return phead;
}

3.尾插

双向循环链表的特点是头节点的 prev 指向尾，尾节点的 next 指向头，我们只需要改变这些指针的指向，而单链表的尾插要先找尾节点，操作上相比单向链表就简单了许多。

申请一个节点 newnode，将它与尾节点和头节点链接起来，让尾节点的 next 指向newnode， newnode 的 prev 指向尾节点，newnode 的 next 指向头节点，头节点的 prev 指向 newnode

//双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//找尾LTNode* tail = phead->prev;//申请新的节点LTNode* newnode = BuyLTNode(x);//链接tail->next = newnode;newnode->prev = tail;newnode->next = phead; phead->prev = newnode;
}

4.打印

双向链表的打印与单向链表的打印在结束条件上不同，因为双向链表在访问完尾节点之后又会循环到头节点，因此我们应该从头节点的下一个节点开始遍历，并使遍历到头节点时就结束。

// 双向链表打印
void LTPrint(LTNode* phead)
{assert(phead);//从头节点的下一个节点开始遍历LTNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

5.尾删

找到尾节点和尾节点的上一个节点，将尾节点释放掉，将尾节点的上一个节点与头节点链接起来。

// 双向链表尾删
void LTPopBack(LTNode* phead)
{//链表不能为空assert(phead);//链表不能只剩一个节点assert(phead->next != NULL);//找尾LTNode* del = phead->prev;//新的尾节点LTNode* tail = del->prev;free(del);tail->next = phead;phead->prev = tail;
}

6.头插

头节点带哨兵位，因此不改变头节点，而是将新节点插入到头节点后面。

注意链接的顺序，先链接新节点和后一个节点，再链接新节点和头节点，如果颠倒这个顺序，将导致后头节点与后一个节点的链接被覆盖，就找不到后一个节点了。

7.头删

// 双向链表头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != NULL);LTNode* first = phead->next;LTNode* second = phead->next->next;free(first);phead->next = second;second->prev = phead;
}

8.统计链表的节点个数

遍历一遍，原理同打印相同

//统计链表节点个数
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}

9.在pos的前面插入

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{LTNode* newnode = BuyLTNode(x);LTNode* posPrev = pos->prev;//链接posPrev和newnodeposPrev->next = newnode;newnode->prev = posPrev;//链接newnode和posnewnode->next = pos;pos->prev = newnode;
}

我们很容易发现，在phead->next之前插入就是头插，在头节点之前插入就是尾插，因此我们可以在头插和尾插函数中进行对这个函数的复用，能够节省大量时间，因此双向循环链表的核心代码就是在 pos节点之前插入。

10.删除pos位置的节点

保存一前一后的节点，释放掉pos节点，然后将前后相连。

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

与在pos前插入同理，也可以函数复用：

删除 phead->next 就是头删

删除 phead->prev 就是尾删

完整代码：

头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//预定义数据类型
typedef int LTDataType;
//定义双向链表
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;
// 创建节点
LTNode* BuyLTNode(LTDataType x);// 双向链表打印
void LTPrint(LTNode* phead);
//双向链表初始化
LTNode* LTInit();双向链表销毁
//void LTDestory(LTNode* phead);
// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 双向链表尾删
void LTPopBack(LTNode* phead);
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);
// 双向链表头删
void LTPopFront(LTNode* phead);
//统计链表节点个数
int LTSize(LTNode* phead);
// 双向链表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

测试文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);//LTPushFront(plist, 10);LTPushBack(plist, 10);LTPrint(plist);
}
void TestList2()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPopBack(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);
}
void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPushFront(plist, 10);LTPushFront(plist, 20);LTPushFront(plist, 30);LTPushFront(plist, 40);LTPrint(plist);
}
void TestList4()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);
}
int main()
{//TestList1();//TestList2();//TestList3();TestList4();return 0;
}

实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
// 创建节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(-1);}//给节点的数据赋值node->data = x;node->next = NULL;node->prev = NULL;return node;
}
//双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);找尾//LTNode* tail = phead->prev;申请新的节点//LTNode* newnode = BuyLTNode(x);链接//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead; //phead->prev = newnode;//在头节点之前插入就是尾插LTInsert(phead, x);
}
//双向链表初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);//前后与自己链接phead->next = phead;phead->prev = phead;return phead;
}
// 双向链表打印
void LTPrint(LTNode* phead)
{assert(phead);//从头节点的下一个节点开始遍历LTNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}
// 双向链表尾删
void LTPopBack(LTNode* phead)
{//链表不能为空assert(phead);//链表不能只剩一个节点assert(phead->next != NULL);找尾//LTNode* del = phead->prev;新的尾节点//LTNode* tail = del->prev;//free(del);//tail->next = phead;//phead->prev = tail;//删除phead->prev就是尾删LTErase(phead->prev);
}
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{/*LTNode* newnode= BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;newnode->prev = phead;phead->next = newnode;*///在phead->next之前插入就是头插LTInsert(phead->next, x);
}
// 双向链表头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != NULL);/*LTNode* first = phead->next;LTNode* second = phead->next->next;free(first);phead->next = second;second->prev = phead;*///在phead->next位置删除就是头删LTErase(phead->next);
}
//统计链表节点个数
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{LTNode* newnode = BuyLTNode(x);LTNode* posPrev = pos->prev;//链接posPrev和newnodeposPrev->next = newnode;newnode->prev = posPrev;//链接newnode和posnewnode->next = pos;pos->prev = newnode;
}// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}
// 双向链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}//没找到return NULL;
}