第1节：链表（续）

第1节：链表（续）

1.2 双向链表

双向链表是一种链表，每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。相比单链表，双向链表的优势在于可以在常数时间内向前或向后遍历节点，这在需要频繁插入、删除节点时非常有用。

双向链表的实现

双向链表节点的定义：

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

// 定义双向链表节点
struct Node {
    int data; // 数据域
    struct Node* next; // 指向下一个节点的指针
    struct Node* prev; // 指向前一个节点的指针
};

函数：创建新节点

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

函数：在链表末尾插入节点

// 在双向链表末尾插入节点
void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (!newNode) return;

    if (*head == NULL) {
        *head = newNode; // 如果链表为空，新节点作为头节点
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next; // 找到链表末尾节点
    }
    temp->next = newNode; // 将新节点添加到末尾
    newNode->prev = temp; // 新节点的前驱指向原末尾节点
}

函数：从链表中删除节点

// 从双向链表中删除节点
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;

    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    // 如果找不到要删除的节点
    if (temp == NULL) return;

    // 如果要删除的是头节点
    if (*head == temp) {
        *head = temp->next; // 更新头节点
    }

    // 更新前后节点的指针
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }

    free(temp); // 释放节点内存
}

函数：正向遍历链表

// 正向遍历双向链表
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

函数：反向遍历链表

// 反向遍历双向链表
void printListReverse(struct Node* head) {
    struct Node* temp = head;

    // 移动到链表的末尾
    while (temp != NULL && temp->next != NULL) {
        temp = temp->next;
    }

    // 反向遍历
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

完整示例：双向链表的使用

int main() {
    struct Node* head = NULL;

    insertNode(&head, 10);
    insertNode(&head, 20);
    insertNode(&head, 30);
    insertNode(&head, 40);

    printf("Forward traversal: ");
    printList(head);

    printf("Reverse traversal: ");
    printListReverse(head);

    deleteNode(&head, 20);
    printf("After deleting 20, forward traversal: ");
    printList(head);

    return 0;
}

编译和运行

gcc doubly_linked_list.c -o doubly_linked_list
./doubly_linked_list

1.3 循环链表

循环链表是一种特殊的链表，其中最后一个节点指向第一个节点，形成一个闭环。循环链表可以是单向的或双向的。相比普通链表，循环链表可以更方便地处理循环数据结构或避免空链表的特殊情况。

单向循环链表的实现

循环链表节点的定义：

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

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

函数：创建新节点

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

函数：在循环链表中插入节点

void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (!newNode) return;

    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head; // 首节点指向自己
        return;
    }

    struct Node* temp = *head;
    while (temp->next != *head) { // 找到最后一个节点
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->next = *head; // 新节点指向头节点
}

函数：删除节点

void deleteNode(struct Node** head, int key) {
    if (*head == NULL) return;

    struct Node *temp = *head, *prev = NULL;

    // 如果头节点就是要删除的节点
    if (temp->data == key) {
        while (temp->next != *head) { // 找到最后一个节点
            temp = temp->next;
        }
        if (*head == (*head)->next) { // 如果链表只有一个节点
            free(*head);
            *head = NULL;
        } else {
            temp->next = (*head)->next; // 更新最后一个节点的指针
            free(*head);
            *head = temp->next; // 更新头节点
        }
        return;
    }

    // 查找要删除的节点
    prev = *head;
    while (prev->next != *head && prev->next->data != key) {
        prev = prev->next;
    }

    if (prev->next->data == key) {
        struct Node* temp = prev->next;
        prev->next = temp->next;
        free(temp);
    }
}

函数：遍历循环链表

void printList(struct Node* head) {
    if (head == NULL) return;

    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("HEAD\n");
}

完整示例：循环链表的使用

int main() {
    struct Node* head = NULL;

    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);

    printf("Circular Linked List: ");
    printList(head);

    deleteNode(&head, 3);
    printf("After deleting 3: ");
    printList(head);

    return 0;
}

编译和运行

gcc circular_linked_list.c -o circular_linked_list
./circular_linked_list

练习题

1. 反转链表：实现一个函数来反转单链表和双向链表。
2. 查找中间节点：实现一个函数，找到单链表的中间节点。
3. 检测循环：编写一个程序检测单链表中是否存在循环。
4. 合并两个链表：编写一个函数合并两个已排序的链表，返回一个新的排序链表。
5. 排序链表：实现插入排序或归并排序来排序链表。

完成这些练习后，如果你对链表的各种操作有了深刻理解，我们可以继续学习其他数据结构，如栈和队列。