上一篇我们写了无头单向非循环链表, 我们了解了, 链表有8中结构, 但是最常见的就是这两种, 在很多笔试题中都是单向链表, 但是
在实际工作中用双向链表又更多一点, 因为双向链表比单链表效率更高, 双链表结构复杂, 但是使用代码实现以后会发现结构会带来
很多优势，实现反而简单了
其实写了单链表之后再看双链表其实非常简单, 只不过就是多了一个指针域而已, 再没有什么特别难的地方. 我们就直接上代码吧
DList.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef struct Node { int value; struct Node* _next; struct Node* _prev; }Node; typedef struct DList { Node* _head; }DList; //初始化 void DListInit(DList* dl); //创建一个结点 Node* BuyNode(int val); //销毁 void DListDestory(DList* dl); //头插 void DListPushFront1(DList* dl, int x); void DListPushFront2(DList* dl, int x); //头删 void DListPopFront(DList* dl); //尾插 void DListPushBack1(DList* dl, int x); void DListPushBack2(DList* dl, int x); //尾删 void DListPopBack(DList* dl); //查找 Node* DListFind(DList* dl, int x); //随机插入 void DListInsert(Node* pos, int x); //随机删除 void DListErase(Node* pos); //移除值为val的所有元素 void DListRemove(DList* dl, int x); //打印 void DListPrint(DList* dl);Realize.c
#include "DList.h" //初始化 void DListInit(DList* dl) { dl->_head = BuyNode(-1); assert(dl); dl->_head->_next = dl->_head; dl->_head->_prev = dl->_head; } //申请一个结点 Node* BuyNode(int val) { Node* newNode = (Node*)malloc(sizeof(Node)); assert(newNode); newNode->value = val; newNode->_next = NULL; newNode->_prev = NULL; return newNode; } //销毁 void DListDestory(DList* dl) { assert(dl); Node* cur = dl->_head->_next; Node* next = cur->_next; for (; cur != dl->_head; cur = next, next = next->_next) { free(cur); } free(dl->_head); dl->_head = NULL; } //头插(1) O(1) void DListPushFront1(DList* dl, int x) { assert(dl); Node* pnode = BuyNode(x); Node* next = dl->_head->_next; assert(dl); pnode->_next = next; next->_prev = pnode; dl->_head->_next = pnode; pnode->_prev = dl->_head; } //头插(2) void DListPushFront2(DList* dl, int x) { DListInsert(dl->_head->_next, x); } //头删 void DListPopFront(DList* dl) { Node* next = dl->_head->_next; if (next == dl->_head) return ; dl->_head->_next = next->_next; next->_next->_prev = dl->_head; free(next); next = NULL; } //尾插(1) void DListPushBack1(DList* dl, int x) { assert(dl); Node* pnode = BuyNode(x); Node* prev = dl->_head->_prev; prev->_next = pnode; pnode->_prev = prev; pnode->_next = dl->_head; dl->_head->_prev = pnode; } //尾插(2) void DListPushBack2(DList* dl, int x) { DListInsert(dl->_head, x); } //尾删 void DListPopBack(DList* dl) { assert(dl); Node* prev = dl->_head->_prev; if (prev = dl->_head) return; prev->_prev->_next = dl->_head; dl->_head->_prev = prev->_prev; free(prev); prev = NULL; } //随机插入 void DListInsert(Node* pos, int x) { assert(pos); Node* pnode = BuyNode(x); Node* prev = pos->_prev; prev->_next = pnode; pnode->_prev = prev; pnode->_next = pos; pos->_prev = pnode; } //随机删除 void DListErase(Node* pos) { assert(pos); Node* prev = pos->_prev; Node* next = pos->_next; prev->_next = next; next->_prev = prev; free(pos); pos = NULL; } //移除指定value的所有元素 void DListRemove(DList* dl, int x) { assert(dl); Node* cur = dl->_head->_next; Node* prev = dl->_head; for (; cur != dl->_head; cur = prev->_next) { if (cur->value == x) DListErase(cur); else prev = cur; } } //查找 Node* DListFind(DList* dl, int x) { assert(dl); Node* cur = dl->_head->_next; while (cur != dl->_head) { if (cur->value == x) { printf("%d is exist!!!\n", x); return cur; } cur = cur->_next; } printf("%d is not exits!!!\n", x); return NULL; } //打印 void DListPrint(DList* dl) { assert(dl); Node* cur = dl->_head->_next; while (cur != dl->_head) { if (cur->_next == dl->_head) { printf("%d\n", cur->value); return; } printf("%d <=> ", cur->value); cur = cur->_next; } printf("\n"); }Test.c
#include "DList.h" void test() { DList dl; DListInit(&dl); DListPushFront1(&dl, 3); DListPushFront2(&dl, 2); DListPushFront1(&dl, 1); DListPushBack1(&dl, 4); DListPushBack2(&dl, 5); DListPushBack1(&dl, 6); DListErase(DListFind(&dl, 6)); Node* pos = DListFind(&dl, 3); DListInsert(pos, 3); DListRemove(&dl, 3); DListPrint(&dl); DListDestory(&dl); } int main() { test(); return 0; }
