如何用C语言写双向链表

如何用C语言写双向链表

双向链表是一种灵活的数据结构，在C语言中尤其适用于需要频繁插入和删除操作的场景。本文将详细介绍双向链表的基本结构、初始化方法、节点插入与删除操作，以及遍历方式，并提供完整的代码示例。

一、双向链表的基本结构

双向链表的基本结构包括节点和链表本身。每个节点包含三个主要部分：数据、指向下一个节点的指针和指向前一个节点的指针。

// 定义节点结构
typedef struct Node {
    int data;              // 数据部分
    struct Node* next;     // 指向下一个节点的指针
    struct Node* prev;     // 指向前一个节点的指针
} Node;

// 定义双向链表结构
typedef struct {
    Node* head;            // 指向链表的头节点
    Node* tail;            // 指向链表的尾节点
} DoublyLinkedList;

二、初始化双向链表

初始化双向链表时，需要将链表的头节点和尾节点指针设置为NULL。

// 初始化双向链表
void initList(DoublyLinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
}

三、插入节点

在双向链表中插入节点可以在头部、尾部或指定位置插入。这里以头部和尾部插入为例。

1、头部插入节点

头部插入节点时，需要更新新节点的next指针和现有头节点的prev指针。

// 头部插入节点
void insertAtHead(DoublyLinkedList* list, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = list->head;
    newNode->prev = NULL;
    if (list->head != NULL) {
        list->head->prev = newNode;
    } else {
        list->tail = newNode;
    }
    list->head = newNode;
}

2、尾部插入节点

尾部插入节点时，需要更新新节点的prev指针和现有尾节点的next指针。

// 尾部插入节点
void insertAtTail(DoublyLinkedList* list, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = list->tail;
    if (list->tail != NULL) {
        list->tail->next = newNode;
    } else {
        list->head = newNode;
    }
    list->tail = newNode;
}

四、删除节点

在双向链表中删除节点时，需要考虑更新前后节点的指针。

1、删除头节点

删除头节点时，需要更新新头节点的prev指针。

// 删除头节点
void deleteAtHead(DoublyLinkedList* list) {
    if (list->head == NULL) {
        return;
    }
    Node* temp = list->head;
    list->head = list->head->next;
    if (list->head != NULL) {
        list->head->prev = NULL;
    } else {
        list->tail = NULL;
    }
    free(temp);
}

2、删除尾节点

删除尾节点时，需要更新新尾节点的next指针。

// 删除尾节点
void deleteAtTail(DoublyLinkedList* list) {
    if (list->tail == NULL) {
        return;
    }
    Node* temp = list->tail;
    list->tail = list->tail->prev;
    if (list->tail != NULL) {
        list->tail->next = NULL;
    } else {
        list->head = NULL;
    }
    free(temp);
}

五、遍历双向链表

遍历双向链表可以从头到尾或从尾到头遍历。

1、从头到尾遍历

// 从头到尾遍历
void traverseFromHead(DoublyLinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

2、从尾到头遍历

// 从尾到头遍历
void traverseFromTail(DoublyLinkedList* list) {
    Node* current = list->tail;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

六、总结

通过上述代码示例，我们实现了双向链表的基本操作，包括初始化、插入节点、删除节点和遍历。双向链表相比单向链表的优势在于可以双向遍历和更高效地进行插入和删除操作，特别是在需要频繁操作的场景中，如实现LRU缓存、处理文本编辑器的撤销和重做操作等。

在实际应用中，我们可以根据具体需求扩展双向链表的功能，如在指定位置插入和删除节点、查找节点、逆序链表等。同时，在进行内存操作时，要注意防止内存泄漏，确保每个分配的节点都能被正确释放。