一、什么是双向链表？
大家有没有发现上一期的单链表结构在尾插和中间插入的时候会使用得非常的难受呢？中间插入需要额外定义一个指针保存插入位置的前一个位置的地址，尾插又需要从头开始一直找到最后才能找到尾部再插入，归根到底都是因为单链表不能往回找上一个结点，所以今天给大家分享一个结构设计得更好的链表：双向带头循环链表。双向链表，顾名思义就是既能往后找下一个结点，又能往前找上一个结点的链表，那么需要怎么设计这个结构呢？其实很简单，只需要在结点的结构体里面多加一个指向前一个结点的指针就行了。下面我们就来逐步地实现这个双向链表。
二、双向带头循环链表的增删查改
2.1 结构体的声明
typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }ListNode;
2.2 初始化链表
//用返回值的形式初始化链表 ListNode* ListInit() { ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); if (phead == NULL) { perror("malloc phead fail"); return NULL; } //phead是哨兵位头节点，不存储有效数据 //空链表里面也存在一个头节点，prev和next指针都指向自己 phead->next = phead; phead->prev = phead; phead->data = -1; return phead; }
2.3 申请新节点
ListNode* BuyListNode(LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); if (newNode == NULL) { perror("malloc newNode fail"); return NULL; } newNode->next = NULL; newNode->prev = NULL; newNode->data = x; return newNode; }
2.4 链表打印
void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; while (cur != pHead) { printf("<=>%d<=>", cur->data); cur = cur->next; } printf("\n"); }
2.5 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newNode = BuyListNode(x); if (newNode == NULL) { return; } ListNode* posPrev = pos->prev; newNode->next = pos; pos->prev = newNode; posPrev->next = newNode; newNode->prev = posPrev; }
2.6 双向链表删除pos位置的节点
void ListErase(ListNode* pHead,ListNode* pos) { assert(pos && pos != pHead); ListNode* posPrev = pos->prev; ListNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos = NULL; }
2.7 头插
void ListPushFront(ListNode* pHead, LTDataType x) { //pHead->next就是链表的头 ListInsert(pHead->next, x); }
2.8 头删
void ListPopFront(ListNode* pHead) { ListErase(pHead, pHead->next); }
2.9 尾插
void ListPushBack(ListNode* pHead, LTDataType x) { //pHead的前一个位置就是尾部，插入实在pos位置的前一个位置插入 ListInsert(pHead, x); }
2.10 尾删
void ListPopBack(ListNode* pHead) { ListErase(pHead, pHead->prev); }
2.11 查找
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.12 双向链表的销毁
void ListDestroy(ListNode** ppHead) { //销毁需要把哨兵位的头节点pHead也释放掉 //所以要传二级指针过来，也可以由调用该函数的人自己释放 assert(ppHead && *ppHead); ListNode* cur = (*ppHead)->next; while (cur != *ppHead) { ListNode* del = cur; cur = cur->next; free(del); del = NULL; } free(*ppHead); *ppHead = NULL; }
三、代码汇总
3.1 List.h
List.h
#pragma once //List.h #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }ListNode; // 创建返回链表的头结点. extern ListNode* ListInit(); // 双向链表销毁 extern void ListDestroy(ListNode** ppHead); //申请新结点 extern ListNode* BuyListNode(LTDataType x); // 双向链表打印 extern void ListPrint(ListNode* pHead); // 双向链表尾插 extern void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 extern void ListPopBack(ListNode* pHead); // 双向链表头插 extern void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 extern void ListPopFront(ListNode* pHead); // 双向链表查找 extern ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 extern void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 extern void ListErase(ListNode* pHead, ListNode* pos);
3.2 List.c
List.c
#define _CRT_SECURE_NO_WARNINGS 1 //List.c #include "List.h" ListNode* ListInit() { ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); if (phead == NULL) { perror("malloc phead fail"); return NULL; } phead->next = phead; phead->prev = phead; phead->data = -1; return phead; } void ListDestroy(ListNode** ppHead) { assert(ppHead && *ppHead); ListNode* cur = (*ppHead)->next; while (cur != *ppHead) { ListNode* del = cur; cur = cur->next; free(del); del = NULL; } free(*ppHead); *ppHead = NULL; } void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; while (cur != pHead) { printf("<=>%d<=>", cur->data); cur = cur->next; } printf("\n"); } ListNode* BuyListNode(LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); if (newNode == NULL) { perror("malloc newNode fail"); return NULL; } newNode->next = NULL; newNode->prev = NULL; newNode->data = x; return newNode; } void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newNode = BuyListNode(x); if (newNode == NULL) { return; } ListNode* posPrev = pos->prev; newNode->next = pos; pos->prev = newNode; posPrev->next = newNode; newNode->prev = posPrev; } void ListErase(ListNode* pHead,ListNode* pos) { assert(pos && pos != pHead); ListNode* posPrev = pos->prev; ListNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos = NULL; } void ListPushBack(ListNode* pHead, LTDataType x) { ListInsert(pHead, x); } void ListPushFront(ListNode* pHead, LTDataType x) { ListInsert(pHead->next, x); } void ListPopBack(ListNode* pHead) { ListErase(pHead, pHead->prev); } void ListPopFront(ListNode* pHead) { ListErase(pHead, pHead->next); } 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; }
3.3 test.c
test.c
#define _CRT_SECURE_NO_WARNINGS 1 //test.c #include "List.h" void test_PushBack(void) { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); ListNode* pos = ListFind(plist, 3); ListInsert(pos, 6); ListPrint(plist); pos = ListFind(plist, 1); ListErase(plist, pos); ListPrint(plist); ListDestroy(&plist); } void test_PushFront(void) { ListNode* plist = ListInit(); ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListDestroy(&plist); } int main() { test_PushBack(); //test_PushFront(); return 0; }
四、总结
双向链表这个数据结构设计得真的非常的好，无论你想对那个位置进行增删查改的任意操作，效率都比单链表高出一截，用起来非常的爽，就是那么nice，而且它的结构你看起来感觉它很复杂，其实看起来越复杂的东西学起来越省事，因为它的结构啥都有，太完美了，而且结构也就多了一个哨兵位的头节点和一个指向前一个元素的指针罢了，这不比单链表用得更爽？哈哈哈，各有各的好啦！你学会了吗？
