【數據結構】--- 雙向鏈表的增刪查改

前言：

? ? ? 經過了幾個月的漫長歲月，回頭時年邁的小編發現，數據結構的內容還沒有寫博客，于是小編趕緊停下手頭的活動，補上博客以洗清身上的罪孽

? ? ? ??前言：

? ? ? ? ? ? ? ? ? ?概念：

? ? ? ? ?雙鏈表的初始化

? ? ? ? ?雙鏈表的判空

? ? ? ? ?雙鏈表的打印

? ? ? ? ??雙鏈表的頭插

? ? ? ? ??雙鏈表的尾插

? ? ? ? ? ?雙鏈表頭刪

? ? ? ? ?雙鏈表的尾刪

? ? ? ? ??雙鏈表的查找

? ? ? ? ?雙鏈表在pos位置前進行插入

? ? ? ??雙鏈表刪除pos位置

? ? ? ? ?雙鏈表的銷毀

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??檢查：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?完整代碼：

????????????????????????????????????????dlist.h

??????????????????????????????????????????????????????dlist.c

?????????????????????????????????????????????????????????????test.c? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

總結：

概念：

? ? ? 雙向鏈表的英文是?Doubly Linked List。雙向鏈表是一種鏈表數據結構，其中每個節點包含三個部分：前驅指針、數據域和后繼指針。前驅指針指向前一個節點，后繼指針指向下一個節點。

雙向鏈表的節點結構

雙向鏈表的節點結構包括三個部分：

前驅指針域 (_prev)：用于存放指向上一個節點的指針。
數據域 (_data)：用于存儲節點的數據元素。
后繼指針域 (_next)：用于存放指向下一個節點的指針。

typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;

雙鏈表的基本操作

? ? ???雙鏈表是一種數據結構，它的每個節點除了存儲數據外，還有兩個指針，分別指向前一個節點和后一個節點。這種結構使得雙鏈表在進行插入和刪除操作時更為高效，因為可以直接訪問任何節點的前驅和后繼節點。

雙鏈表的初始化

? ? ? 在開始對我們的雙鏈表進行增刪查改前，我們先要對鏈表進行初始化，和單鏈表差不多，需要一個創建新節點的函數，不同的是新節點多了一個前驅，也需要置空

? ? ? 然后創建鏈表的頭節點，頭節點的值我們取-1，當頭節點創建成功的時候，我們將其前驅和后繼指向自己

//創建新節點
ListNode* BuySListNode(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;
}
// 創建返回鏈表的頭結點.
ListNode* ListCreate() {ListNode*head= BuySListNode(-1);if (head != NULL) {head->_prev = head;head->_next = head;}return head;
}

雙鏈表的判空

bool ListEmptyLTNode(ListNode* phead)
{assert(phead);/*鏈表返回只剩頭節點(鏈表已經被刪空)為真否則為假*/return phead->_next == phead;
}

雙鏈表的打印

遍歷鏈表

// 雙向鏈表打印
void ListPrint(ListNode* pHead) {assert(pHead);ListNode* start = pHead->_next;while (start!=pHead) {printf("%d<=>", start->_data);start = start->_next;}printf("\n");
}

雙鏈表的頭插

? ? ? ?創建一個新節點，保存頭節點的后繼，令其為ne，讓新節點的下一個指向ne，ne的前驅指向新節點，新節點的前驅指向頭節點，頭節點的后繼指向新節點

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* newnode = BuySListNode(x);ListNode* ne = pHead->_next;newnode->_next = ne;ne->_prev = newnode;newnode->_prev = pHead;pHead->_next = newnode;
}

雙鏈表的尾插

// 在鏈表尾部插入新節點
void ListPushBack(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* newnode = BuySListNode(x);  // 創建新節點// 調整指針將新節點接入鏈表尾部ListNode* pre = pHead->_prev;  // 原尾節點pre->_next = newnode;          // 原尾節點的next指向新節點newnode->_prev = pre;          // 新節點的prev指向原尾節點newnode->_next = pHead;        // 新節點的next指向頭節點pHead->_prev = newnode;        // 頭節點的prev指向新尾節點
}

雙鏈表頭刪

先看看鏈表是否為空，空鏈表不能進行尾刪

? ? ? 然后保存頭節點的后繼的后繼，讓頭節點的后繼指向頭節點的后繼的后繼，頭節點的后繼的后繼的前驅指向頭節點

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead) {assert(pHead);if (!ListEmptyLTNode(pHead)) {ListNode* check = pHead->_next->_next;ListNode* tmp = pHead->_next;pHead->_next = check;check->_prev = pHead;free(tmp);}
}

雙鏈表的尾刪

先看看鏈表是否為空，空鏈表不能進行尾刪

? ? ? 然后保存頭節點的前驅的前驅，讓頭節點的前驅指向頭節點的前驅的前驅，頭節點的前驅的前驅的后繼指向頭節點

// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead) {assert(pHead);if (!ListEmptyLTNode(pHead)) {ListNode* tmp = pHead->_prev;ListNode* pre = pHead->_prev->_prev;pre->_next = pHead;pHead->_prev = pre;free(tmp);}}

雙鏈表的查找

遍歷鏈表

// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* start = pHead->_next;while (start != pHead) {if (start->_data == x)return start;start = start->_next;}return NULL;
}

雙鏈表在pos位置前進行插入

? ? ? ?先判斷pos是否有效，創建一個新節點，然后將pos位置的前驅保存下來，讓新節點的前驅指向pos的前驅新節點的后繼指向pos，pos的前驅指向新節點，pos前驅的后繼指向新節點

// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode* newnode = BuySListNode(x);ListNode* pre = pos->_prev;newnode->_next = pos;pos->_prev = newnode;pre->_next = newnode;newnode->_prev = pre;
}

雙鏈表刪除pos位置

? ? ? ?先判斷pos是否有效，然后將pos位置的前驅和后繼保存下來，讓pos的前驅的后繼指向pos的后繼，pos后繼的前驅指向pos的前驅

// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos) {assert(pos);ListNode* ne = pos->_next;ListNode* pre = pos->_prev;ne->_prev = pre;pre->_next = ne;free(pos);
}

雙鏈表的銷毀

? ? ?先斷言頭節點有效，然后再創建一個start指針指向頭節點的后繼，當該指針不等于頭節點時，不斷遍歷，先保存start指針的后繼，然后釋放掉start指針所指向的內存，再將原來保存的后繼重新給到start指針，最后再釋放頭節點，需在外層置空指針，防止野指針問題。

// 雙向鏈表銷毀
void ListDestory(ListNode* pHead) {assert(pHead);ListNode* start = pHead->_next;while (start != pHead) {ListNode* ne = start->_next;free(start);start = ne;}free(pHead);//pHead = NULL;
}

檢查：

?

#include "dlist.h"int main() {ListNode* head = ListCreate(); // 創建鏈表頭節點// 尾插入測試ListPushBack(head, 1);ListPushBack(head, 2);ListPushBack(head, 3);printf("鏈表內容（尾插入后）：");ListPrint(head);// 頭插入測試ListPushFront(head, 0);printf("鏈表內容（頭插入后）：");ListPrint(head);// 查找測試ListNode* found = ListFind(head, 2);if (found) {printf("找到節點：%d\n", found->_data);}else {printf("未找到節點\n");}// 刪除頭節點測試ListPopFront(head);printf("鏈表內容（頭刪后）：");ListPrint(head);// 刪除尾節點測試ListPopBack(head);printf("鏈表內容（尾刪后）：");ListPrint(head);// 在指定位置插入測試ListInsert(head->_next, 4); // 在第二個節點后插入printf("鏈表內容（插入4后）：");ListPrint(head);// 刪除指定節點測試ListErase(head->_next); // 刪除第二個節點printf("鏈表內容（刪除第二個節點后）：");ListPrint(head);// 銷毀鏈表ListDestory(head);// printf("鏈表內容（銷毀后）：");// ListPrint(head); // 應該輸出空鏈表的狀態
head=NULL;return 0;
}

完整代碼：

dlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 帶頭+雙向+循環鏈表增刪查改實現
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;ListNode* BuySListNode(LTDataType x);
// 創建返回鏈表的頭結點.
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);
bool ListEmptyLTNode(ListNode* phead);

dlist.c

#include "dlist.h"ListNode* BuySListNode(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;
}
// 創建返回鏈表的頭結點.
ListNode* ListCreate() {ListNode*head= BuySListNode(-1);if (head != NULL) {head->_prev = head;head->_next = head;}return head;
}
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead) {assert(pHead);ListNode* start = pHead->_next;while (start != pHead) {ListNode* ne = start->_next;free(start);start = ne;}free(pHead);//pHead = NULL;
}
bool ListEmptyLTNode(ListNode* phead)
{assert(phead);/*鏈表返回只剩頭節點(鏈表已經被刪空)為真否則為假*/return phead->_next == phead;
}
// 雙向鏈表打印
void ListPrint(ListNode* pHead) {assert(pHead);ListNode* start = pHead->_next;while (start!=pHead) {printf("%d<=>", start->_data);start = start->_next;}printf("\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* newnode = BuySListNode(x);ListNode* pre = pHead->_prev;pre->_next = newnode;newnode->_prev = pre;newnode->_next = pHead;pHead->_prev = newnode;}
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead) {assert(pHead);if (!ListEmptyLTNode(pHead)) {ListNode* tmp = pHead->_prev;ListNode* pre = pHead->_prev->_prev;pre->_next = pHead;pHead->_prev = pre;free(tmp);}}
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* newnode = BuySListNode(x);ListNode* ne = pHead->_next;newnode->_next = ne;ne->_prev = newnode;newnode->_prev = pHead;pHead->_next = newnode;
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead) {assert(pHead);ListNode* check = pHead->_next->_next;ListNode* tmp = pHead->_next;pHead->_next = check;check->_prev = pHead;free(tmp);
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* start = pHead->_next;while (start != pHead) {if (start->_data == x)return start;start = start->_next;}return NULL;
}
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode* newnode = BuySListNode(x);ListNode* pre = pos->_prev;newnode->_next = pos;pos->_prev = newnode;pre->_next = newnode;newnode->_prev = pre;
}
// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos) {assert(pos);ListNode* ne = pos->_next;ListNode* pre = pos->_prev;ne->_prev = pre;pre->_next = ne;free(pos);
}

test.c

#include "dlist.h"int main() {ListNode* head = ListCreate(); // 創建鏈表頭節點// 尾插入測試ListPushBack(head, 1);ListPushBack(head, 2);ListPushBack(head, 3);printf("鏈表內容（尾插入后）：");ListPrint(head);// 頭插入測試ListPushFront(head, 0);printf("鏈表內容（頭插入后）：");ListPrint(head);// 查找測試ListNode* found = ListFind(head, 2);if (found) {printf("找到節點：%d\n", found->_data);}else {printf("未找到節點\n");}// 刪除頭節點測試ListPopFront(head);printf("鏈表內容（頭刪后）：");ListPrint(head);// 刪除尾節點測試ListPopBack(head);printf("鏈表內容（尾刪后）：");ListPrint(head);// 在指定位置插入測試ListInsert(head->_next, 4); // 在第二個節點后插入printf("鏈表內容（插入4后）：");ListPrint(head);// 刪除指定節點測試ListErase(head->_next); // 刪除第二個節點printf("鏈表內容（刪除第二個節點后）：");ListPrint(head);// 銷毀鏈表ListDestory(head);// printf("鏈表內容（銷毀后）：");// ListPrint(head); // 應該輸出空鏈表的狀態
head=NULL;return 0;
}