AB21-分别采用头插法和尾插法创建一个带头节点的双向链表

代码实现

尾插法

/**
 * 采用尾插法创建带头结点的双向链表
 * @return 指向双向链表头结点的指针
 */
DinkList create_tail() {
    // 1. 创建并初始化头结点
    DinkList L = (DinkList)malloc(sizeof(DNode));
    if (L == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    L->data = 0;        // 头结点数据域可设为默认值
    L->next = NULL;     // 头结点后继指针初始化为空
    L->prev = NULL;     // 头结点前驱指针初始化为空

    // r始终指向链表的尾结点，便于尾插操作
    DinkList r = L;

    // 读取数据
    int x;
    printf("请输入数据（输入9999结束）：");
    scanf("%d", &x);

    // 2. 循环创建结点，直到输入结束标志
    while (x != 9999) {
        // 创建新结点
        DinkList s = (DinkList)malloc(sizeof(DNode));
        if (s == NULL) {
            printf("内存分配失败\n");
            return L;  // 返回已创建的部分链表
        }

        // 设置新结点数据
        s->data = x;
        s->next = NULL;     // 新结点后继指针初始化为空

        // 3. 尾插操作：建立双向连接
        r->next = s;        // 尾结点指向新结点
        s->prev = r;        // 新结点指向前驱（原尾结点）
        r = s;              // 更新尾指针，指向新的尾结点

        // 读取下一个数据
        scanf("%d", &x);
    }

    return L;  // 返回链表头指针
}

头插法

/**
 * 采用头插法创建带头结点的双向链表
 * @return 指向双向链表头结点的指针
 */
DinkList create_head() {
    // 1. 创建并初始化头结点
    DinkList L = (DinkList)malloc(sizeof(DNode));
    if (L == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    L->data = 0;
    L->next = NULL;
    L->prev = NULL;

    // 读取数据
    int x;
    printf("请输入数据（输入9999结束）：");
    scanf("%d", &x);

    // 2. 循环创建结点，直到输入结束标志
    while (x != 9999) {
        // 创建新结点
        DinkList s = (DinkList)malloc(sizeof(DNode));
        if (s == NULL) {
            printf("内存分配失败\n");
            return L;
        }

        // 设置新结点数据
        s->data = x;

        // 3. 头插操作：建立双向连接
        s->next = L->next;          // 新结点指向原第一个结点
        if (L->next != NULL) {      // 如果原链表不为空
            L->next->prev = s;      // 原第一个结点的前驱指向新结点
        }
        L->next = s;                // 头结点指向新结点
        s->prev = L;                // 新结点指向前驱（头结点）

        // 读取下一个数据
        scanf("%d", &x);
    }

    return L;  // 返回链表头指针
}

算法执行流程图解

双向链表结构：

双向链表结点结构：
┌─────────┬─────────┬─────────┐
│  prev   │   data  │  next   │
└─────────┴─────────┴─────────┘
    ↑                   ↑
  指向前驱           指向后继

尾插法执行过程：

输入序列：1 2 3 9999

初始状态：L → [ ] ↔ NULL
          ↑
          r

输入1：   L → [ ] ↔ [1] ↔ NULL
          ↑       ↑
          头     r(尾)

输入2：   L → [ ] ↔ [1] ↔ [2] ↔ NULL
          ↑             ↑
          头           r(尾)

输入3：   L → [ ] ↔ [1] ↔ [2] ↔ [3] ↔ NULL
          ↑                   ↑
          头                 r(尾)

头插法执行过程：

输入序列：1 2 3 9999

初始状态：L → [ ] ↔ NULL

输入1：   L → [ ] ↔ [1] ↔ NULL
                ↑
               新插入

输入2：   L → [ ] ↔ [2] ↔ [1] ↔ NULL
                ↑     ↑
               新插入

输入3：   L → [ ] ↔ [3] ↔ [2] ↔ [1] ↔ NULL
                ↑     ↑     ↑
               新插入

双向连接建立过程图解

尾插法连接建立：

插入新结点s到尾结点r之后：

步骤1：r->next = s
L → [...] ↔ [r] → [s]    [s] ← NULL

步骤2：s->prev = r  
L → [...] ↔ [r] ↔ [s]    [s] ← NULL

步骤3：r = s
L → [...] ↔ [r/s] ↔ NULL

头插法连接建立：

插入新结点s到头结点L之后：

原状态：L → [ ] ↔ [A] ↔ [B] ↔ NULL

步骤1：s->next = L->next
[s] → [A]

步骤2：L->next->prev = s (如果存在)
[A] → [s]

步骤3：L->next = s
L → [s]

步骤4：s->prev = L
L ↔ [s]

最终：L → [ ] ↔ [s] ↔ [A] ↔ [B] ↔ NULL

复杂度分析

时间复杂度：O(n)

• 创建结点：n次malloc操作，每次O(1)，总计O(n)
• 连接操作：
• 尾插法：每次4次指针操作，总计O(n)
• 头插法：每次4次指针操作，总计O(n)
• 输入操作：n次scanf操作，总计O(n)
• 总体时间复杂度：O(n)

空间复杂度：O(n)

• 结点存储：n个结点，每个结点占用O(1)空间，总计O(n)
• 辅助变量：指针变量L、r、s等，O(1)
• 总体空间复杂度：O(n)

优化版本：添加错误处理和更清晰的逻辑

/**
 * 优化版本：添加错误处理和更清晰的逻辑
 */
DinkList create_tail_optimized() {
    DinkList L = (DinkList)malloc(sizeof(DNode));
    if (!L) return NULL;

    L->next = NULL;
    L->prev = NULL;
    DinkList r = L;
    int x;

    printf("请输入数据（输入-1结束）：");
    while (scanf("%d", &x) && x != -1) {
        DinkList s = (DinkList)malloc(sizeof(DNode));
        if (!s) {
            printf("内存分配失败\n");
            break;
        }

        s->data = x;
        s->next = NULL;
        s->prev = r;
        r->next = s;
        r = s;
    }

    return L;
}

优化版本：带计数功能的头插法

/**
 * 带计数功能的头插法
 */
DinkList create_head_with_count(int *count) {
    DinkList L = (DinkList)malloc(sizeof(DNode));
    if (!L) return NULL;

    L->next = NULL;
    L->prev = NULL;
    *count = 0;
    int x;

    printf("请输入数据（输入-1结束）：");
    while (scanf("%d", &x) && x != -1) {
        DinkList s = (DinkList)malloc(sizeof(DNode));
        if (!s) {
            printf("内存分配失败\n");
            break;
        }

        s->data = x;
        s->next = L->next;
        s->prev = L;
        if (L->next) {
            L->next->prev = s;
        }
        L->next = s;
        (*count)++;
    }

    return L;
}

双向链表与单向链表对比

特性	单向链表	双向链表
存储空间	每个结点1个指针	每个结点2个指针
插入操作	需要前驱结点	可直接操作
删除操作	需要前驱结点	可直接操作
遍历方向	只能向前	可前向/后向
实现复杂度	简单	复杂

算法特点

核心思想： - 尾插法：维护尾指针，每次在尾部添加新结点 - 头插法：每次在头部插入新结点，建立双向连接

关键技巧： 1. 双向连接：正确设置prev和next指针 2. 边界处理：处理空链表和第一个结点的特殊情况 3. 指针操作顺序：避免断链和野指针

注意点： - 每次插入都要同时维护前驱和后继指针 - 头插法需要特别注意原第一个结点的前驱指针更新 - 及时检查内存分配是否成功

优势： - 可以双向遍历 - 插入和删除操作更加灵活 - 某些算法实现更简单

这种双向链表的创建方法是数据结构中的基础操作，为后续的插入、删除等操作提供了良好的基础。