双向链表的基本概念

双向链表是一种线性数据结构，每个节点包含两个指针：一个指向前驱节点（prev），一个指向后继节点（next）。与单向链表相比，双向链表支持双向遍历，但需要更多的内存存储指针。

定义链表节点结构

使用 typedef 定义节点结构体，包含数据域和前后指针：

typedef struct Node {
    int data;           // 数据域
    struct Node* prev;  // 前驱指针
    struct Node* next;  // 后继指针
} Node;

创建头节点

双向链表通常需要一个头节点作为起始点。头节点的 prev 和 next 初始化为 NULL：

Node* createHead() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->prev = NULL;
    head->next = NULL;
    return head;
}

插入节点操作

根据插入位置不同，分为头插法、尾插法和中间插入。

头插法：新节点插入到头节点之后。

void insertAtHead(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head->next;
    newNode->prev = head;
    if (head->next != NULL) {
        head->next->prev = newNode;
    }
    head->next = newNode;
}

尾插法：新节点插入到链表末尾。

void insertAtTail(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

删除节点操作

通过遍历找到目标节点，调整前后节点的指针关系后释放内存。

void deleteNode(Node* head, int data) {
    Node* current = head->next;
    while (current != NULL) {
        if (current->data == data) {
            current->prev->next = current->next;
            if (current->next != NULL) {
                current->next->prev = current->prev;
            }
            free(current);
            return;
        }
        current = current->next;
    }
}

遍历链表

支持正向和反向遍历，验证链表完整性。

正向遍历：

void traverseForward(Node* head) {
    Node* current = head->next;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

反向遍历：

void traverseBackward(Node* head) {
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    while (current != head) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

内存释放

释放所有节点内存，避免内存泄漏。

void freeList(Node* head) {
    Node* current = head->next;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(head);
}

完整代码示例

结合上述操作，以下是一个完整的双向链表实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

Node* createHead() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->prev = NULL;
    head->next = NULL;
    return head;
}

void insertAtHead(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head->next;
    newNode->prev = head;
    if (head->next != NULL) {
        head->next->prev = newNode;
    }
    head->next = newNode;
}

void insertAtTail(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

void deleteNode(Node* head, int data) {
    Node* current = head->next;
    while (current != NULL) {
        if (current->data == data) {
            current->prev->next = current->next;
            if (current->next != NULL) {
                current->next->prev = current->prev;
            }
            free(current);
            return;
        }
        current = current->next;
    }
}

void traverseForward(Node* head) {
    Node* current = head->next;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void traverseBackward(Node* head) {
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    while (current != head) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

void freeList(Node* head) {
    Node* current = head->next;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(head);
}

int main() {
    Node* head = createHead();
    insertAtHead(head, 1);
    insertAtTail(head, 2);
    insertAtHead(head, 3);
    traverseForward(head);  // 输出: 3 1 2
    traverseBackward(head); // 输出: 2 1 3
    deleteNode(head, 1);
    traverseForward(head);  // 输出: 3 2
    freeList(head);
    return 0;
}

常见问题与调试技巧

1. 指针越界：确保在操作 prev 和 next 前检查是否为 NULL。
2. 内存泄漏：每次 malloc 后需在适当位置 free。
3. 边界条件：处理头尾节点时需单独验证逻辑是否正确。

通过以上步骤，可实现一个功能完整的双向链表，并逐步扩展更复杂的功能（如排序、查找等）。