引言

在计算机科学的数据结构领域中，双链表作为一种重要的线性数据结构，因其高效的插入和删除操作而备受关注。尤其在考研算法的备考过程中，掌握双链表的插入与删除操作不仅是基础要求，更是提升解题能力的关键。本文将围绕“双链表的插入操作”和“双链表的删除操作”两大核心主题，进行深入剖析和详细讲解，旨在帮助读者构建坚实的知识体系，为考研之路奠定坚实基础。

一、双链表基础回顾

1.1 双链表定义

双链表，全称双向链表，是一种特殊的链表结构。与单链表不同，双链表中的每个节点不仅包含指向下一个节点的指针（next），还包含指向前一个节点的指针（prev）。这种结构使得双链表在遍历、插入和删除操作上具有更高的灵活性。

1.2 双链表节点结构

一个典型的双链表节点结构可以表示为：

typedef struct DNode {
    int data;               // 数据域
    struct DNode *prev;     // 指向前驱节点的指针
    struct DNode *next;     // 指向后继节点的指针
} DNode;

二、双链表的插入操作

2.1 插入操作概述

双链表的插入操作主要包括在指定位置插入新节点。根据插入位置的不同，可以分为头插法、尾插法和中间插入法。每种方法都有其特定的应用场景和实现细节。

2.2 头插法

头插法是将新节点插入到双链表的头部，成为新的头节点。具体步骤如下：

创建新节点并初始化其数据域和指针域。
将新节点的next指针指向原头节点。
若原头节点不为空，则将其prev指针指向新节点。
更新头指针，使其指向新节点。

代码示例：

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

2.3 尾插法

尾插法是将新节点插入到双链表的尾部，成为新的尾节点。具体步骤如下：

创建新节点并初始化其数据域和指针域。
遍历双链表，找到尾节点。
将尾节点的next指针指向新节点。
将新节点的prev指针指向尾节点。
更新尾指针（若需要），使其指向新节点。

代码示例（假设已有尾指针tail）：

void insertAtTail(DNode **head, DNode **tail, int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = *tail;
    if (*tail != NULL) {
        (*tail)->next = newNode;
    } else {
        *head = newNode; // 若链表为空，则头尾指针均指向新节点
    }
    *tail = newNode;
}

2.4 中间插入法

中间插入法是在双链表的指定位置插入新节点。这通常需要先遍历到指定位置的前一个节点，然后进行插入操作。

代码示例（在位置pos插入）：

void insertAtPosition(DNode **head, int pos, int data) {
    if (pos < 0) return;
    DNode *current = *head;
    int count = 0;
    // 遍历到pos-1位置
    while (current != NULL && count < pos - 1) {
        current = current->next;
        count++;
    }
    if (current == NULL) return; // 位置超出链表长度
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = current->next;
    newNode->prev = current;
    if (current->next != NULL) {
        current->next->prev = newNode;
    }
    current->next = newNode;
}

三、双链表的删除操作

3.1 删除操作概述

双链表的删除操作主要包括删除指定位置的节点。根据删除位置的不同，可以分为头删除法、尾删除法和中间删除法。每种方法都需要仔细处理指针的更新，以避免内存泄漏和链表断裂。

3.2 头删除法

头删除法是删除双链表的头节点。具体步骤如下：

检查链表是否为空。
保存原头节点的指针（若需要释放内存）。
更新头指针，使其指向原头节点的下一个节点。
若新头节点不为空，则将其prev指针置为NULL。
释放原头节点的内存。

代码示例：

void deleteAtHead(DNode **head) {
    if (*head == NULL) return;
    DNode *temp = *head;
    *head = (*head)->next;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
}

3.3 尾删除法

尾删除法是删除双链表的尾节点。这通常需要遍历到尾节点的前一个节点，然后进行删除操作。