目錄

1. 單鏈表
   1.1 無頭單鏈表
   1.2 有頭單鏈表
2. 單向循環鏈表
3. 雙鏈表
   3.1 雙鏈表
   3.2 雙向循環鏈表
4. 總結與對比

---

一、單鏈表

1. 無頭單鏈表（Headless Singly Linked List）

定義：鏈表無頭結點，直接由頭指針指向第一個數據節點。

特點：

• 插入/刪除第一個節點需特殊處理。
• 空鏈表時頭指針為NULL。

核心代碼

typedef struct LNode {int data;struct LNode *next;
} LNode, *LinkList;bool InitList(LinkList *L) {*L = NULL;return true;
}bool insert_head(LinkList *L, LNode *new) {if (new == NULL) return false;new->next = *L;*L = new;return true;
}

示例操作

int main() {LinkList list;InitList(&list);LNode *node = newnode(11);insert_head(&list, node); // 頭部插入// ... 其他操作return 0;
}

---

2. 有頭單鏈表（Singly Linked List with Header）

定義：鏈表包含頭結點，頭指針始終指向頭結點。

優點：

• 插入/刪除第一個節點與普通節點操作統一。
• 空鏈表時頭指針不為NULL，統一處理邏輯。

核心代碼

bool InitList(LinkList *L) {*L = (LNode*)malloc(sizeof(LNode));(*L)->next = NULL;return true;
}bool insert_head(LinkList L, LNode *new) {new->next = L->next;L->next = new;return true;
}bool insert_tail(LinkList L, LNode *new) {LNode *p = L;while (p->next != NULL) p = p->next;p->next = new;return true;
}

示例操作

int main() {LinkList list;InitList(&list);LNode *node = newnode(11);insert_head(list, node); // 頭部插入node = newnode(88);insert_tail(list, node); // 尾部插入// ... 其他操作return 0;
}

---

二、單向循環鏈表（Circular Linked List）

定義：鏈表最后一個節點的next指向頭結點，形成循環。

特點：

• 支持從任意節點開始遍歷整個鏈表。
• 刪除操作需注意頭結點的特殊處理。

核心代碼

bool InitList(DLinkList *L) {*L = (LNode*)malloc(sizeof(LNode));(*L)->next = *L;return true;
}bool insert_head(LinkList L, LNode *new) {new->next = L->next;L->next = new;return true;
}LNode* delete_tail(LinkList L) {LNode *p = L, *q = L->next;while (q->next != L) {p = q;q = q->next;}p->next = L;return q;
}

---

三、雙鏈表（Doubly Linked List）

1. 雙鏈表

定義：每個節點包含prev和next指針，支持雙向遍歷。

特點：

• 可高效實現插入/刪除操作（需同時維護前后指針）。
• 需額外存儲空間。

核心代碼

typedef struct DNode {int data;struct DNode *prev, *next;
} DNode, *DLinkList;bool insert_head(DLinkList L, DNode *new) {new->next = L->next;new->prev = L;if (L->next != NULL) L->next->prev = new;L->next = new;return true;
}DNode* delete(DLinkList L, DNode *node) {if (node == L) return NULL;node->prev->next = node->next;if (node->next != NULL) node->next->prev = node->prev;return node;
}

---

2. 雙向循環鏈表（Circular Doubly Linked List）

定義：雙鏈表最后一個節點的next指向頭結點，頭結點的prev指向尾節點。

特點：

• 支持高效雙向遍歷和循環操作。
• 操作需處理循環指針。

核心代碼

bool InitList(DLinkList *L) {*L = (DNode*)malloc(sizeof(DNode));(*L)->next = *L;(*L)->prev = *L;return true;
}bool insert_head(DLinkList L, DNode *new) {new->next = L->next;new->prev = L;L->next->prev = new;L->next = new;return true;
}DNode* delete_tail(DLinkList L) {DNode *p = L->prev;p->prev->next = L;L->prev = p->prev;return p;
}

---

四、總結與對比

結構類型	插入/刪除時間復雜度	優點	缺點
無頭單鏈表	O(n)	簡單	頭部操作需特殊處理
有頭單鏈表	O(1)（頭插）	操作統一	需額外頭結點空間
單向循環鏈表	O(1)（頭插）	支持循環遍歷	需處理循環指針
雙鏈表	O(1)（雙向操作）	支持雙向遍歷	空間占用更大
雙向循環鏈表	O(1)（雙向操作）	完全循環遍歷	實現復雜度最高

---

關鍵點總結

1. 頭結點的作用：統一操作邏輯，避免空指針問題。
2. 循環鏈表的優勢：遍歷無需判斷尾節點，適合需要循環遍歷的場景。
3. 雙鏈表的適用場景：需要頻繁雙向遍歷或快速刪除節點的場景（如瀏覽器歷史記錄）。