C語言實例之雙向鏈表增刪改查
一、雙向鏈表介紹
雙向鏈表（Doubly Linked List）是一種常見的數據結構，在單鏈表的基礎上增加了向前遍歷的功能。與單向鏈表不同，雙向鏈表的每個節(jié)點除了包含指向下一個節(jié)點的指針外，還包含指向前一個節(jié)點的指針。
作用和原理：
（1）插入和刪除操作：由于雙向鏈表中每個節(jié)點都有指向前一個節(jié)點的指針，所以在雙向鏈表中進行插入或刪除操作時，相對于單向鏈表更加高效。可以通過修改前后節(jié)點的指針來完成插入和刪除，而無需遍歷鏈表。
（2）雙向遍歷：雙向鏈表支持從頭部到尾部以及從尾部到頭部的雙向遍歷。這在某些場景下非常有用，例如需要反向查找、刪除最后一個節(jié)點等。
（3）增加了靈活性：由于每個節(jié)點都具有指向前一個節(jié)點和后一個節(jié)點的指針，雙向鏈表在某些特定場景下更靈活。例如，需要在鏈表中間插入或刪除節(jié)點，或者需要修改前一個節(jié)點的信息。
雙向鏈表的原理很簡單。每個節(jié)點由數據域和兩個指針組成，其中一個指針指向前一個節(jié)點，一個指針指向后一個節(jié)點。頭節(jié)點指向鏈表的第一個節(jié)點，尾節(jié)點指向鏈表的最后一個節(jié)點。通過調整節(jié)點之間的指針，可以在雙向鏈表中執(zhí)行插入、刪除和遍歷等操作。
使用場景：
（1）編輯器中的撤銷和重做功能：雙向鏈表可以用于實現撤銷和重做功能，每次編輯操作都將其結果存儲為一個節(jié)點，并使用指針鏈接起來。通過雙向鏈表，可以方便地在撤銷和重做之間進行切換。
（2）瀏覽器的導航歷史：瀏覽器的導航歷史可以使用雙向鏈表來保存已訪問的頁面，每個頁面作為一個節(jié)點，并使用指針鏈接起來，以便進行前進和后退操作。
（3）實現LRU緩存替換算法：LRU緩存中，最近最少使用的數據被淘汰，可以使用雙向鏈表來維護緩存中的數據，最近訪問的數據位于鏈表的頭部，最久未訪問的數據位于鏈表的尾部。
（4）實現雙向隊列：雙向鏈表可以用于實現雙向隊列（Dequeue），支持在隊列的兩端進行插入和刪除操作。
雙向鏈表提供了更多的靈活性和功能，特別是當需要在雙向遍歷、頻繁的插入和刪除操作等場景下使用。在許多常見的數據結構和算法中都有廣泛的應用。
二、代碼實現
以下是使用C語言實現的完整雙向鏈表代碼，包含了鏈表的創(chuàng)建、增加、刪除、修改、排序和插入等功能。代碼中封裝了一套完整的子函數，以方便使用。
#include <stdio.h>
#include <stdlib.h>
?
// 雙向鏈表節(jié)點結構
typedef struct Node {
? ?int data; ? ? ? ? ? ? ?// 數據域
? ?struct Node* prev; ? ? // 指向前一個節(jié)點的指針
? ?struct Node* next; ? ? // 指向后一個節(jié)點的指針
} Node;
?
// 創(chuàng)建新節(jié)點
Node* createNode(int data) {
? ?Node* newNode = (Node*)malloc(sizeof(Node));
? ?if (newNode == NULL) {
? ? ? ?printf("Failed to allocate memory for new node\n");
? ? ? ?return NULL;
? }
? ?newNode->data = data;
? ?newNode->prev = NULL;
? ?newNode->next = NULL;
? ?return newNode;
}
?
// 在鏈表末尾添加節(jié)點
void append(Node** head, int data) {
? ?Node* newNode = createNode(data);
? ?if (newNode == NULL) {
? ? ? ?return;
? }
? ?if (*head == NULL) {
? ? ? ?*head = newNode;
? } else {
? ? ? ?Node* current = *head;
? ? ? ?while (current->next != NULL) { ? ?// 找到鏈表末尾
? ? ? ? ? ?current = current->next;
? ? ? }
? ? ? ?current->next = newNode;
? ? ? ?newNode->prev = current;
? }
}
?
// 在鏈表頭部添加節(jié)點
void prepend(Node** head, int data) {
? ?Node* newNode = createNode(data);
? ?if (newNode == NULL) {
? ? ? ?return;
? }
? ?if (*head == NULL) {
? ? ? ?*head = newNode;
? } else {
? ? ? ?newNode->next = *head;
? ? ? (*head)->prev = newNode;
? ? ? ?*head = newNode;
? }
}
?
// 在指定位置插入節(jié)點
void insert(Node** head, int data, int position) {
? ?if (position < 0) {
? ? ? ?printf("Invalid position\n");
? ? ? ?return;
? }
? ?if (position == 0) {
? ? ? ?prepend(head, data);
? ? ? ?return;
? }
? ?Node* newNode = createNode(data);
? ?if (newNode == NULL) {
? ? ? ?return;
? }
? ?Node* current = *head;
? ?int count = 0;
? ?while (count < (position - 1) && current != NULL) { ? ?// 找到插入位置前一個節(jié)點
? ? ? ?current = current->next;
? ? ? ?count++;
? }
? ?if (current == NULL) {
? ? ? ?printf("Invalid position\n");
? ? ? ?free(newNode);
? ? ? ?return;
? }
? ?newNode->next = current->next;
? ?newNode->prev = current;
? ?if (current->next != NULL) {
? ? ? ?current->next->prev = newNode;
? }
? ?current->next = newNode;
}
?
// 刪除指定位置的節(jié)點
void removeAt(Node** head, int position) {
? ?if (*head == NULL) {
? ? ? ?printf("List is empty\n");
? ? ? ?return;
? }
? ?if (position < 0) {
? ? ? ?printf("Invalid position\n");
? ? ? ?return;
? }
? ?Node* current = *head;
? ?int count = 0;
? ?if (position == 0) {
? ? ? ?*head = current->next;
? ? ? ?if (*head != NULL) {
? ? ? ? ? (*head)->prev = NULL;
? ? ? }
? ? ? ?free(current);
? ? ? ?return;
? }
? ?while (count < position && current != NULL) { ? ?// 找到要刪除的節(jié)點
? ? ? ?current = current->next;
? ? ? ?count++;
? }
? ?if (current == NULL) {
? ? ? ?printf("Invalid position\n");
? ? ? ?return;
? }
? ?current->prev->next = current->next;
? ?if (current->next != NULL) {
? ? ? ?current->next->prev = current->prev;
? }
? ?free(current);
}
?
// 修改指定位置的節(jié)點值
void modify(Node* head, int position, int data) {
? ?Node* current = head;
? ?int count = 0;
? ?while (count < position && current != NULL) { ? ?// 找到要修改的節(jié)點
? ? ? ?current = current->next;
? ? ? ?count++;
? }
? ?if (current == NULL) {
? ? ? ?printf("Invalid position\n");
? ? ? ?return;
? }
? ?current->data = data;
}
?
// 對鏈表進行排序
void sort(Node** head) {
? ?if (*head == NULL) {
? ? ? ?printf("List is empty\n");
? ? ? ?return;
? }
? ?Node* current = *head;
? ?Node* temp = NULL;
? ?int swapped;
? ?do {
? ? ? ?swapped = 0;
? ? ? ?current = *head;
? ? ? ?while (current->next != NULL) {
? ? ? ? ? ?if (current->data > current->next->data) {
? ? ? ? ? ? ? ?int tmp = current->data;
? ? ? ? ? ? ? ?current->data = current->next->data;
? ? ? ? ? ? ? ?current->next->data = tmp;
? ? ? ? ? ? ? ?swapped = 1;
? ? ? ? ? }
? ? ? ? ? ?current = current->next;
? ? ? }
? ? ? ?temp = current;
? } while (swapped);
}
?
// 打印鏈表
void printList(Node* head) {
? ?if (head == NULL) {
? ? ? ?printf("List is empty\n");
? ? ? ?return;
? }
? ?Node* current = head;
? ?while (current != NULL) {
? ? ? ?printf("%d ", current->data);
? ? ? ?current = current->next;
? }
? ?printf("\n");
}
?
// 釋放鏈表內存
void freeList(Node** head) {
? ?if (*head == NULL) {
? ? ? ?return;
? }
? ?Node* current = *head;
? ?Node* next = NULL;
? ?while (current != NULL) {
? ? ? ?next = current->next;
? ? ? ?free(current);
? ? ? ?current = next;
? }
? ?*head = NULL;
}
?
int main() {
? ?Node* head = NULL;
? ?append(&head, 5);
? ?append(&head, 3);
? ?prepend(&head, 9);
? ?insert(&head, 7, 1);
? ?removeAt(&head, 2);
? ?modify(head, 0, 2);
? ?sort(&head);
? ?printList(head);
? ?freeList(&head);
? ?return 0;
}代碼里實現了創(chuàng)建雙向鏈表、在鏈表末尾添加節(jié)點、在鏈表頭部添加節(jié)點、在指定位置插入節(jié)點、刪除指定位置的節(jié)點、修改指定位置的節(jié)點值、對鏈表進行排序、打印鏈表及釋放鏈表內存等功能。
三、思路講解
代碼里定義了一個雙向鏈表節(jié)點結構，包含數據域（data）、指向前一個節(jié)點的指針（prev）和指向后一個節(jié)點的指針（next）。
typedef struct Node {
? ?int data;
? ?struct Node* prev;
? ?struct Node* next;
} Node;（1）createNode函數用于創(chuàng)建新節(jié)點。分配內存以存儲節(jié)點，并檢查內存分配是否成功。設置節(jié)點的數據域為傳入的數據，并將前一個節(jié)點和后一個節(jié)點的指針都設置為NULL。最后，返回新創(chuàng)建的節(jié)點的指針。
（2）append函數用于在鏈表末尾添加節(jié)點。首先調用createNode函數創(chuàng)建一個新節(jié)點。如果頭節(jié)點為空，則將新節(jié)點設置為頭節(jié)點。否則，遍歷鏈表直到找到最后一個節(jié)點，將新節(jié)點連接到最后一個節(jié)點的下一個位置，并設置新節(jié)點的prev指針指向最后一個節(jié)點。
（3）prepend函數用于在鏈表頭部添加節(jié)點。首先，調用createNode函數創(chuàng)建一個新節(jié)點。如果頭節(jié)點為空，則將新節(jié)點設置為頭節(jié)點。否則，將新節(jié)點的next指針指向當前的頭節(jié)點，將當前頭節(jié)點的prev指針指向新節(jié)點，然后將新節(jié)點設置為頭節(jié)點。
（4）insert函數用于在指定位置插入節(jié)點。首先，檢查插入位置是否合法。如果插入位置為0，則調用prepend函數在鏈表頭部插入節(jié)點。否則，調用createNode函數創(chuàng)建一個新節(jié)點，然后遍歷鏈表直到找到插入位置前一個節(jié)點，將新節(jié)點插入到這兩個節(jié)點之間，即將新節(jié)點的next指針指向前一個節(jié)點的next指針所指向的節(jié)點，將新節(jié)點的prev指針指向前一個節(jié)點，然后更新新節(jié)點兩側節(jié)點的指針。
（5）removeAt函數用于刪除指定位置的節(jié)點。首先，檢查鏈表是否為空。如果鏈表為空，則輸出相應的提示信息。如果要刪除的位置為0，即刪除頭節(jié)點，需要特殊處理，即將頭節(jié)點的下一個節(jié)點設置為新的頭節(jié)點，并將新的頭節(jié)點的prev指針設置為NULL。否則，遍歷鏈表直到找到要刪除的節(jié)點，將要刪除節(jié)點的前一個節(jié)點的next指針指向要刪除節(jié)點的下一個節(jié)點，然后更新兩側節(jié)點的指針。
（6）modify函數用于修改指定位置的節(jié)點值。首先，遍歷鏈表直到找到要修改的節(jié)點，然后將該節(jié)點的數據域設置為傳入的新數據。
（7）sort函數用于對鏈表進行排序。首先，檢查鏈表是否為空。如果鏈表為空，則輸出相應的提示信息。使用冒泡排序算法，重復遍歷鏈表并比較相鄰節(jié)點的值，如果前一個節(jié)點的值大于后一個節(jié)點的值，則交換它們的值。重復此過程，直到鏈表沒有發(fā)生交換為止。
（8）printList函數用于打印鏈表中的所有節(jié)點的值。首先，檢查鏈表是否為空。如果鏈表為空，則輸出相應的提示信息。遍歷鏈表的每個節(jié)點，并輸出節(jié)點中存儲的數據。
（9）freeList函數用于釋放鏈表的內存。首先，檢查鏈表是否為空。如果鏈表為空，則直接返回。遍歷鏈表的每個節(jié)點，使用free函數釋放節(jié)點的內存，并將節(jié)點指針設為NULL，最后將頭節(jié)點指針設為NULL。
以上就是C語言實例之雙向鏈表增刪改查的詳細內容，更多關于C語言雙向鏈表的資料請關注腳本之家其它相關文章！
相關文章
所謂雙緩沖機制，是指在繪制控件時，首先將要繪制的內容繪制在一個圖片中，再將圖片一次性地繪制到控件上。本文主要為大家介紹了Qt中的雙緩沖機制與實例應用，希望對大家有所幫助2023-03-03
本篇文章主要介紹使用C#winform編寫滲透測試工具，實現SQL注入的功能。使用python編寫SQL注入腳本，基于get顯錯注入的方式進行數據庫的識別、獲取表名、獲取字段名，最終獲取用戶名和密碼；使用C#winform編寫windows客戶端軟件調用.py腳本，實現用戶名和密碼的獲取2021-08-08
這篇文章主要介紹了C++雙向循環(huán)列表,實例分析了C++雙向循環(huán)列表的創(chuàng)建、輸出、添加、刪除、移動的相關操作技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
常見的瓦片地圖有矩形、菱形、正六邊形幾種。此文章主要討論菱形瓦片，也就是大家常說的2.5D，斜45度瓦片地圖。比如《紅警2》、《帝國時代2》都是采用這種技術2022-09-09
這篇文章主要介紹了C++ move()函數案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++調用C#的DLL實現方法,很有實用價值,需要的朋友可以參考下2014-07-07
這篇文章主要介紹了C++vector自定義大小方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
在內核開發(fā)模式下，初始化字符串也需要調用專用的初始化函數，如下分別初始化ANSI和UNCODE字符串，本文我們就來看看代碼是如何實現的2022-09-09
這篇文章主要介紹了使用emacs編寫C語言教程,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要通過兩個簡單的示例為大家詳細介紹一下C語言中深度優(yōu)先搜索(DFS)算法，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2023-02-02