鏈表是計算機科學中一種基礎且重要的數據結構，它如同一條由珠子串成的項鏈，每個珠子（節點）都包含著數據和指向下一個珠子的線索。

與數組相比，鏈表在插入和刪除操作上更加靈活，無需預先分配固定大小的內存空間。

一、單鏈表：數據結構的入門之選

基本形態與特點

單鏈表是鏈表家族中最基礎的成員，它由一系列節點組成，每個節點包含兩部分：

數據域和指針域。

數據域存儲具體的數據，而指針域則指向下一個節點。

鏈表的起點由一個頭指針（head）指向，最后一個節點的指針域指向 NULL，表示鏈表的結束。

特點總結：

????????單向訪問：只能從頭節點開始，沿著指針方向依次訪問后續節點

????????插入和刪除操作效率高：O (1) 時間復雜度（前提是已知操作位置的前驅節點）

????????動態內存分配：無需預先分配固定大小的內存

????????隨機訪問效率低：訪問第 n 個節點需要 O (n) 時間

示例代碼：單鏈表的實現

#include <stdio.h>
#include <stdlib.h>// 定義單鏈表節點結構
typedef struct Node {int data;           // 數據域struct Node* next;  // 指針域，指向下一個節點
} Node;// 創建新節點
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("內存分配失敗\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}// 在鏈表尾部插入節點
void append(Node** head_ref, int data) {Node* newNode = createNode(data);if (*head_ref == NULL) {*head_ref = newNode;return;}Node* last = *head_ref;while (last->next != NULL) {last = last->next;}last->next = newNode;
}// 打印鏈表
void printList(Node* node) {while (node != NULL) {printf("%d -> ", node->data);node = node->next;}printf("NULL\n");
}// 釋放鏈表內存
void freeList(Node* head) {Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}int main() {Node* head = NULL;append(&head, 1);append(&head, 2);append(&head, 3);printf("單鏈表內容: ");printList(head);freeList(head);return 0;
}

單鏈表示意圖

頭指針 head↓┌───────┐    ┌───────┐    ┌───────┐│ 1 | ──┼──→ │ 2 | ──┼──→ │ 3 | NULL└───────┘    └───────┘    └───────┘

二、雙向鏈表：支持雙向導航的靈活結構

基本形態與特點

雙向鏈表在單鏈表的基礎上進行了擴展，每個節點除了包含數據域和指向下一個節點的指針外，還增加了一個指向前驅節點的指針。

這種結構使得雙向鏈表支持雙向遍歷，既可以從頭節點向后訪問，也可以從尾節點向前訪問。

特點總結：

????????????????雙向訪問：支持從頭節點和尾節點兩個方向進行遍歷

????????????????插入和刪除操作更加靈活：可以快速訪問前驅節點

????????????????每個節點占用更多內存：需要額外的指針域存儲前驅節點信息

????????????????操作復雜度增加：插入和刪除操作需要維護兩個指針

示例代碼：雙向鏈表的實現

#include <stdio.h>
#include <stdlib.h>// 定義雙向鏈表節點結構
typedef struct DNode {int data;               // 數據域struct DNode* prev;     // 指向前驅節點的指針struct DNode* next;     // 指向后繼節點的指針
} DNode;// 創建新節點
DNode* createDNode(int data) {DNode* newNode = (DNode*)malloc(sizeof(DNode));if (newNode == NULL) {printf("內存分配失敗\n");exit(1);}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 在鏈表尾部插入節點
void appendDNode(DNode** head_ref, int data) {DNode* newNode = createDNode(data);if (*head_ref == NULL) {*head_ref = newNode;return;}DNode* last = *head_ref;while (last->next != NULL) {last = last->next;}last->next = newNode;newNode->prev = last;
}// 打印雙向鏈表（正向）
void printForward(DNode* node) {while (node != NULL) {printf("%d <-> ", node->data);node = node->next;}printf("NULL\n");
}// 釋放雙向鏈表內存
void freeDList(DNode* head) {DNode* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}int main() {DNode* head = NULL;appendDNode(&head, 1);appendDNode(&head, 2);appendDNode(&head, 3);printf("雙向鏈表內容(正向): ");printForward(head);freeDList(head);return 0;
}

雙向鏈表示意圖

頭指針 head↓┌───────┐    ┌───────┐    ┌───────┐
NULL←─| 1 | ──┼──→| 2 | ──┼──→| 3 |─→NULL└───────┘    └───────┘    └───────┘

三、循環鏈表：首尾相連的封閉結構

基本形態與特點

循環鏈表是一種特殊的鏈表結構，它的最后一個節點的指針域不再指向 NULL，而是指向鏈表的頭節點，形成一個閉合的環。

循環鏈表可以是單循環鏈表（只使用一個方向的指針）或雙循環鏈表（使用雙向指針）。

特點總結：

????????????????首尾相連：可以從任意節點開始遍歷整個鏈表

????????????????沒有明顯的頭節點和尾節點：需要特別注意循環終止條件

? ? ? ? ? ? ? ? 適合實現環形緩沖區、輪詢調度等場景

????????????????插入和刪除操作需要考慮維護循環特性

示例代碼：單循環鏈表的實現

#include <stdio.h>
#include <stdlib.h>// 定義循環鏈表節點結構
typedef struct CNode {int data;struct CNode* next;
} CNode;// 創建新節點
CNode* createCNode(int data) {CNode* newNode = (CNode*)malloc(sizeof(CNode));if (newNode == NULL) {printf("內存分配失敗\n");exit(1);}newNode->data = data;newNode->next = newNode;  // 初始時指向自身return newNode;
}// 在鏈表尾部插入節點
void appendCNode(CNode** head_ref, int data) {CNode* newNode = createCNode(data);if (*head_ref == NULL) {*head_ref = newNode;return;}CNode* last = (*head_ref)->next;  // 找到尾節點while (last->next != *head_ref) {last = last->next;}last->next = newNode;newNode->next = *head_ref;
}// 打印循環鏈表
void printCList(CNode* head) {if (head == NULL) return;CNode* temp = head;do {printf("%d -> ", temp->data);temp = temp->next;} while (temp != head);printf("(回到頭節點)\n");
}// 釋放循環鏈表內存
void freeCList(CNode* head) {if (head == NULL) return;CNode* temp = head->next;while (temp != head) {CNode* next = temp->next;free(temp);temp = next;}free(head);
}int main() {CNode* head = NULL;appendCNode(&head, 1);appendCNode(&head, 2);appendCNode(&head, 3);printf("循環鏈表內容: ");printCList(head);freeCList(head);return 0;
}

單循環鏈表示意圖

   ┌───────┐    ┌───────┐    ┌───────┐│ 1 | ──┼──→ │ 2 | ──┼──→ │ 3 | ──┼──┐└───────┘    └───────┘    └───────┘  │↑                                  │└──────────────────────────────────┘

四、雙向循環鏈表：最靈活的鏈表結構

基本形態與特點

雙向循環鏈表結合了雙向鏈表和循環鏈表的特點，每個節點既包含指向前驅節點的指針，也包含指向后繼節點的指針，并且鏈表的首尾節點相連形成一個環。

這種結構提供了最大的靈活性，但也需要更多的內存和更復雜的操作。

特點總結：

雙向遍歷：可以從任意節點開始向前或向后遍歷首尾相連：

沒有明顯的頭節點和尾節點插入和刪除操作

需要維護四個指針（前驅和后繼節點的指針）

適合需要頻繁雙向遍歷和循環操作的場景

示例代碼：雙向循環鏈表的實現

#include <stdio.h>
#include <stdlib.h>// 定義雙向循環鏈表節點結構
typedef struct DCNode {int data;struct DCNode* prev;struct DCNode* next;
} DCNode;// 創建新節點
DCNode* createDCNode(int data) {DCNode* newNode = (DCNode*)malloc(sizeof(DCNode));if (newNode == NULL) {printf("內存分配失敗\n");exit(1);}newNode->data = data;newNode->prev = newNode;newNode->next = newNode;return newNode;
}// 在鏈表尾部插入節點
void appendDCNode(DCNode** head_ref, int data) {DCNode* newNode = createDCNode(data);if (*head_ref == NULL) {*head_ref = newNode;return;}DCNode* last = (*head_ref)->prev;  // 找到尾節點last->next = newNode;newNode->prev = last;newNode->next = *head_ref;(*head_ref)->prev = newNode;
}// 打印雙向循環鏈表（正向）
void printDCListForward(DCNode* head) {if (head == NULL) return;DCNode* temp = head;do {printf("%d <-> ", temp->data);temp = temp->next;} while (temp != head);printf("(回到頭節點)\n");
}// 釋放雙向循環鏈表內存
void freeDCList(DCNode* head) {if (head == NULL) return;DCNode* temp = head->next;while (temp != head) {DCNode* next = temp->next;free(temp);temp = next;}free(head);
}int main() {DCNode* head = NULL;appendDCNode(&head, 1);appendDCNode(&head, 2);appendDCNode(&head, 3);printf("雙向循環鏈表內容(正向): ");printDCListForward(head);freeDCList(head);return 0;
}

雙向循環鏈表示意圖

   ┌───────┐    ┌───────┐    ┌───────┐│ 1 | ──┼──→ │ 2 | ──┼──→ │ 3 | ──┼──┐└───────┘    └───────┘    └───────┘  │↑  ↑                                ││  └────────────────────────────────┘│                                     │└─────────────────────────────────────┘

五、鏈表與數組的對比

特性	鏈表	數組
內存分配	動態分配，無需預先指定大小	靜態分配，需要預先指定大小
插入 / 刪除效率	O (1)（已知位置）	O (n)（需要移動元素）
隨機訪問效率	O(n)	O(1)
內存利用率	可能有碎片（每個節點需要額外指針）	連續內存，無碎片
適用場景	頻繁插入刪除，數據量不確定	頻繁隨機訪問，數據量固定

總結

鏈表作為一種基礎的數據結構，在計算機科學中有著廣泛的應用。通過本文的介紹，我們了解了鏈表的四種主要類型：

????????單鏈表：最簡單的鏈表形式，支持單向遍歷

????????雙向鏈表：增加了前驅指針，支持雙向遍歷

????????循環鏈表：首尾相連，適合環形結構的應用

????????雙向循環鏈表：結合了雙向鏈表和循環鏈表的特點，提供最大的靈活性

每種鏈表結構都有其獨特的形態、特點和適用場景。

在實際編程中，我們可以根據具體需求選擇合適的鏈表類型。

鏈表的核心優勢在于動態內存分配和高效的插入刪除操作，這使得它在許多場景下比數組更加適用。