欢迎来到 Claffic 的博客 💞💞💞

前言：

往期给大家介绍了单链表， 单链表在 OJ 中出现频率较高，但实际使用的不多；而双链表是存储数据常用的表，它的全名是 带头双向循环链表 ，虽然结构复杂，但不一定复杂，甚至会比单链表容易实现。

Part1: 双向链表结构

所谓双向循环链表，就是相比单链表来说，一个节点中多了一个 结构体指针 ， 指向前一个结点 罢了。

我是图示 

Part2: 相关功能实现

1.开工准备 

1.1创建新结点

一个结点包含 要储存的元素 ， 前一个结点的指针 和 下一个结点的指针 。

代码实现： 

// 创建新结点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

1.2创建头节点

一个重要的问题是头结点中的两个指针指向哪里，指向空吗？

其实不是，这样就没有双向链表的特点了，

为了能准确体现双向链表的特点，要 先把头节点的两个指针都指向自己 ，这样就形成了闭环。

代码实现：

//创建头节点
ListNode* LTInit()
{ListNode* pHead = BuyListNode(-1);pHead->next = pHead;pHead->prev = pHead;return pHead;
}

2.相关功能实现 

2.1链表打印

与单链表打印逻辑相近

代码实现： 

// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("<=>pHead<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

2.2尾部插入

与单链表相比，双向链表尾插不需要查找尾部，直接将头节点的前一个记录为尾即可。

剩下的就是修改四个指针。

代码实现：

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* tail = pHead->prev;ListNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = pHead;pHead->prev = newnode;//ListInsert(pHead, x);
}

2.3尾部删除

先记录，再修改指针，最后释放置空。

代码实现： 

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);ListNode* tail = pHead->prev;ListNode* tailprev = tail->prev;pHead->prev = tailprev;tailprev->next = pHead;free(tail);tail = NULL;
}

2.4头部插入

代码实现： 

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* first = pHead->next;ListNode* newnode = BuyListNode(x);pHead->next = newnode;newnode->prev = pHead;newnode->next = first;first->prev = newnode;
}

2.5头部删除

代码实现：

// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);ListNode* first = pHead->next;ListNode* firstnext = first->next;pHead->next = firstnext;firstnext->prev = pHead;free(first);first = NULL;
}

2.6查找位置

这个也与单链表的位置查找相近

代码实现：

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead;while (cur && cur->data != x){cur = cur->next;}return cur;
}

2.7在pos前插入

代码实现：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posprev = pos->prev;posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

2.8删除pos位置的结点

代码实现： 

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posprev = pos->prev;ListNode* posnext = pos->next;posprev->next = posnext;posnext = posprev;free(pos);pos = NULL;
}

2.9销毁链表

代码实现：

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posprev = pos->prev;ListNode* posnext = pos->next;posprev->next = posnext;posnext = posprev;free(pos);pos = NULL;
}

代码已上传至 我的gitee

拿走不谢~

总结：

在学习完单链表后再进行双链表的实现可谓是水到渠成，所以有些地方就没做详细解释，这也告诉我们复杂的东西不一定难实现。 

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗