C語言雙向鏈表完整操作集：帶頭尾哨兵節點的非循環設計

設計優勢

• 統一邊界：空表 head->next == tail，插入/刪除無需特判首尾。
• 雙向遍歷：正序/逆序打印、從尾部高效刪除。
• O(1) 定位首尾：頭尾哨兵直接給出首尾有效節點。

節點與列表結構

typedef struct Node {
    int element;
    struct Node *prior, *next;
} Node;

typedef struct {
    Node *head, *tail;
} DList;

核心操作實現

初始化

void List_Init(DList *L) {
    L->head = malloc(sizeof(Node));
    L->tail = malloc(sizeof(Node));
    L->head->prior = NULL;
    L->tail->next = NULL;
    L->head->next = L->tail;
    L->tail->prior = L->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;
    }
}

正序/逆序打印

void List_PrintForward(const DList *L) {
    for (Node *p = L->head->next; p != L->tail; p = p->next)
        printf("%d ", p->element);
    puts("");
}
void List_PrintReverse(const DList *L) {
    for (Node *p = L->tail->prior; p != L->head; p = p->prior)
        printf("%d ", p->element);
    puts("");
}

清空（保留頭尾節點）

void List_Clear(DList *L) {
    Node *p = L->head->next;
    while (p != L->tail) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
    L->head->next = L->tail;
    L->tail->prior = L->head;
}

長度、判空、按位置/值查找、修改

int List_Length(const DList *L) {
    int len = 0;
    for (Node *p = L->head->next; p != L->tail; p = p->next) ++len;
    return len;
}
bool List_IsEmpty(const DList *L) { return L->head->next == L->tail; }

int List_Get(const DList *L, int pos) {  // 1-based
    int i = 1;
    for (Node *p = L->head->next; p != L->tail; p = p->next, ++i)
        if (i == pos) return p->element;
    return -1;
}

int* List_FindAddr(DList *L, int val) {
    for (Node *p = L->head->next; p != L->tail; p = p->next)
        if (p->element == val) return &p->element;
    return NULL;
}

bool List_Modify(DList *L, int pos, int val) {
    int i = 1;
    for (Node *p = L->head->next; p != L->tail; p = p->next, ++i)
        if (i == pos) { p->element = val; return true; }
    return false;
}

頭插/尾插/任意位置插入

void List_PushFront(DList *L, int val) {
    Node *n = malloc(sizeof(Node));
    n->element = val; n->prior = n->next = NULL;
    n->next = L->head->next;
    L->head->next->prior = n;
    L->head->next = n;
    n->prior = L->head;
}

void List_PushBack(DList *L, int val) {
    Node *n = malloc(sizeof(Node));
    n->element = val; n->prior = n->next = NULL;
    n->prior = L->tail->prior;
    L->tail->prior->next = n;
    n->next = L->tail;
    L->tail->prior = n;
}

/* pos=0 表示頭節點後（第一個有效位置） */
bool List_Insert(DList *L, int pos, int val) {
    Node *p = L->head;
    for (int i = 0; i < pos && p != L->tail; ++i) p = p->next;
    if (p == L->tail) return false;
    Node *n = malloc(sizeof(Node));
    n->element = val; n->prior = n->next = NULL;
    n->next = p->next;
    p->next->prior = n;
    p->next = n;
    n->prior = p;
    return true;
}

按位置/值刪除

bool List_ErasePos(DList *L, int pos) {
    Node *p = L->head->next;
    for (int i = 1; p != L->tail; p = p->next, ++i)
        if (i == pos) {
            p->prior->next = p->next;
            p->next->prior = p->prior;
            free(p);
            return true;
        }
    return false;
}

bool List_EraseVal(DList *L, int val) {
    for (Node *p = L->head->next; p != L->tail; p = p->next)
        if (p->element == val) {
            p->prior->next = p->next;
            p->next->prior = p->prior;
            free(p);
            return true;
        }
    return false;
}

測試主程式

int main(void) {
    DList L; List_Init(&L);
    List_CreateTail(&L);          // 輸入: 1 2 3 4 5 0
    List_PrintForward(&L);        // 1 2 3 4 5
    List_PrintReverse(&L);        // 5 4 3 2 1
    printf("len=%d\n", List_Length(&L));
    List_Modify(&L, 2, 111);
    List_PrintForward(&L);        // 1 111 3 4 5
    List_PushFront(&L, 100);
    List_PrintForward(&L);        // 100 1 111 3 4 5
    List_PushBack(&L, 900);
    List_PrintForward(&L);        // 100 1 111 3 4 5 900
    List_Clear(&L);
    List_PrintForward(&L);        // (空)
    free(L.head); free(L.tail);
    return 0;
}