兩種建表策略對比
| 維度 | 頭插法 | 尾插法 |
|---|
| 輸入順序與鏈表順序 | 逆序 | 同序 |
| 是否需尾指針 | 不需要 | 需要（或遍歷到尾） |
| 適用場景 | 棧、逆序輸出、單向鏈表 | 隊列、保持輸入順序、雙向鏈表 |
| 代碼複雜度 | 略簡單 | 略複雜（維護 tail） |
頭插法實現（無頭節點）
Node* HeadInsertCreate(void) {
Node *head = NULL;
int x;
while (scanf("%d", &x) == 1 && x > 0) {
Node *n = malloc(sizeof(Node));
n->element = x; n->prior = n->next = NULL;
n->next = head;
if (head) head->prior = n;
head = n;
}
return head; // 返回首節點
}
尾插法實現（無頭節點）
Node* TailInsertCreate(void) {
Node *head = NULL, *tail = NULL;
int x;
while (scanf("%d", &x) == 1 && x > 0) {
Node *n = malloc(sizeof(Node));
n->element = x; n->prior = n->next = NULL;
if (!head) {
head = tail = n;
} else {
tail->next = n;
n->prior = tail;
tail = n;
}
}
return head;
}
帶頭尾哨兵的尾插法（推薦生產用）
void List_CreateTail(DList *L) {
Node *p = L->head;
int x;
while (scanf("%d", &x) == 1 && x > 0) {
Node *n = malloc(sizeof(Node));
n->element = x; n->prior = n->next = NULL;
p->next = n; n->prior = p;
n->next = L->tail; L->tail->prior = n;
p = n;
}
}
選擇建議
- 教學/算法題：按題目要求選擇，頭插法常用於「逆序輸出」或「單鏈表就地逆置」。
- 工程庫：統一使用帶頭尾哨兵的尾插法，順序直觀、操作統一、無邊界特判。
- 若必須無哨兵：尾插法維護
tail 指針，頭插法僅維護 head。
