双向链表的实现

带头+双向+循环链表

• 1. 项目头文件
• 2. 具体实现功能
• • 2.1 双向链表的初始化
  • 2.2 双向链表尾插
  • 2.3 双向链表头插
  • 2.4 双向链表尾删
  • 2.5 双向链表头删
  • 2.6 双向链表查找
  • 2.7 双向链表在pos的前面进行插入
  • 2.8 双向链表删除pos位置的节点
  • 2.9 双向链表打印
  • 2.10 双向链表销毁

我们上篇博客进行了单链表的实现，这次就实现一下双链表:

1. 项目头文件

#include#include#include#include// 带头+双向+循环链表增删查改实现typedef int LTDataType;typedef struct ListNode{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;}ListNode;// 创建返回链表的头结点.ListNode* ListCreate();// 双向链表销毁void ListDestory(ListNode* pHead);// 双向链表打印void ListPrint(ListNode* pHead);// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x);// 双向链表尾删void ListPopBack(ListNode* pHead);// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x);// 双向链表头删void ListPopFront(ListNode* pHead);// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x);// 双向链表在pos的前面进行插入void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点void ListErase(ListNode* pos);

2. 具体实现功能

2.1 双向链表的初始化

ListNode* ListCreate(){ListNode* phead = (ListNode*)malloc(sizeof(ListNode));if (phead == NULL){perror("malloc");return NULL;}phead->_data = -1;phead->_next = phead;phead->_prev = phead;return phead;}

创建一个哨兵位头结点，前后都指向自己，再返回链表的头结点。

2.2 双向链表尾插

ListNode* BuyNode(LTDataType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");return NULL;}newnode->_next = NULL;newnode->_prev = NULL;newnode->_data = x;return newnode;}// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x){assert(pHead);ListNode* newnode = BuyNode(x);ListNode* tail = pHead->_prev;newnode->_prev = tail;tail->_next = newnode;newnode->_next = pHead;pHead->_prev = newnode;}

和单链表一样，添加操作时都需要创建一个新的结点，但与单链表不同的是，此时不必再判断是否为空(因为有了哨兵位头结点)，并且尾插时找尾结点也不用依次遍历，直接找头结点的前驱。

2.3 双向链表头插

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

此时，也不用判断是否为空了(因为有了哨兵位头结点)。

2.4 双向链表尾删

bool LTEmpty(ListNode* pHead){return pHead->_next == pHead;}// 双向链表尾删void ListPopBack(ListNode* pHead){assert(pHead);assert(!LTEmpty(pHead));ListNode* tail = pHead->_prev;ListNode* tailPrev = tail->_prev;pHead->_prev = tailPrev;tailPrev->_next = pHead;free(tail);}

尾删时，直接断言哨兵位不能为空。

2.5 双向链表头删

// 双向链表头删void ListPopFront(ListNode* pHead){assert(pHead);assert(!LTEmpty(pHead));ListNode* first = pHead->_next;ListNode* second = first->_next;free(first);pHead->_next = second;second->_prev = pHead;}

头删也一样，直接断言哨兵位不能为空。

2.6 双向链表查找

ListNode* ListFind(ListNode* pHead, LTDataType x){assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_data == x){return cur;}cur = cur->_next;}return NULL;}

需要注意的是，开始是从哨兵位头结点后一个结点开始遍历的，结束的条件是当其和哨兵位头结点相同时，则循环结束。所以这整个链表的设计是非常之巧妙的，带有工学之美的。

2.7 双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* prev = pos->_prev;ListNode* newnode = BuyNode(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = pos;pos->_prev = newnode;}

在进行插入时，需要与查找函数相互配合。我们把查找到的结点返回给插入函数的pos。

2.8 双向链表删除pos位置的节点

// 双向链表删除pos位置的节点void ListErase(ListNode* pos){assert(pos);ListNode* posPrev = pos->_prev;ListNode* posNext = pos->_next;posPrev->_next = posNext;posNext->_prev = posPrev;free(pos);}

删除也是一样的，跟查找函数进行配合。

2.9 双向链表打印

void ListPrint(ListNode* pHead){assert(pHead);ListNode* cur = pHead->_next;printf("哨兵位");while (cur != pHead){printf("%d",cur->_data);cur = cur->_next;}printf("\n");}

2.10 双向链表销毁

// 双向链表销毁void ListDestory(ListNode* pHead){ListNode* cur = pHead->_next;while (cur != pHead){ListNode* next = cur->_next;free(cur);cur = next;}free(pHead);}

打印和销毁也非常简单，就不细说了。总体而言，带头+双向+循环链表的实现比单链表简单多了。

代码参考: https://gitee.com/yujin518/test_c/tree/master/test_3_17