链表的创建：头插法与尾插法详解（数据结构）

C++ 链表的创建：头插法与尾插法详解

链表（Linked List）是一种重要的数据结构，适用于插入和删除操作频繁的场景。本文介绍 两种常见的链表构建方法：

• 尾插法（Append / Tail Insertion）：适合顺序存储，插入顺序与输入顺序一致。
• 头插法（Prepend / Head Insertion）：适合逆序存储，输入的元素会被倒序存入链表。

本文提供详细的代码实现、解析以及常见错误分析，帮助初学者理解链表的构建方式。

一、链表的基本结构

在 C++ 语言中，我们通常使用结构体（struct）定义链表节点：

#include <iostream>

typedef struct Node {
    int data;      // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node, *LinkList;

• data：存储节点数据。
• next：存储指向下一个节点的指针。
• LinkList 是 Node* 的别名，表示指向链表头部的指针。

二、尾插法（顺序存储）

尾插法 是 按照输入顺序 依次插入新节点，适用于按 自然顺序 存储数据。
核心思路：

1. 创建头节点 作为链表的起点。
2. 维护一个尾指针 r，用于记录链表末尾，以便快速添加新节点。
3. 每次创建一个新节点，将其链接到尾指针 r，然后更新 r 指向新节点。

✅ 尾插法代码实现

#include <iostream>
#include <cstdlib>  // malloc 需要包含此头文件

typedef struct Node {
    int data;
    struct Node* next;
} Node, *LinkList;

// 初始化链表（带头结点）
void Init(LinkList &L) {
    L = (Node*)malloc(sizeof(Node));
    L->next = NULL;
}

// 尾插法插入元素
void InsertTail(LinkList &L, int e) {
    Node* r = L; // 记录链表尾部
    Node* s;
    
    while (e != -1) {  // 以 -1 作为输入结束标志
        s = (Node*)malloc(sizeof(Node));
        s->data = e;
        s->next = NULL;
        
        r->next = s; // 连接新结点
        r = s; // 更新尾指针
        
        std::cin >> e; // 读取下一个数据
    }
}

// 打印链表
void PrintL(LinkList &L) {
    Node* p = L->next; // 跳过头结点
    if (!p) {
        std::cout << "Empty List\n";
        return;
    }
    while (p) {
        std::cout << p->data << " -> ";
        p = p->next;
    }
    std::cout << "NULL\n";
}

// 释放链表
void FreeList(LinkList &L) {
    Node* p = L;
    while (p) {
        Node* temp = p;
        p = p->next;
        free(temp);
    }
    L = NULL;
}

int main() {
    LinkList L;
    Init(L);

    int e;
    std::cin >> e;
    InsertTail(L, e);

    PrintL(L);
    FreeList(L);
    return 0;
}

📌 示例输入

1 2 3 4 -1

📌 示例输出

1 -> 2 -> 3 -> 4 -> NULL

三、头插法（逆序存储）

头插法 是 逆序存储输入数据，新节点总是插入到链表头部，适用于从后往前访问数据的场景。
核心思路：

1. 创建头节点 作为链表的起点。
2. 每次创建一个新节点，让其 next 指向头节点 L 的 next，然后 L->next 指向新节点。
3. 这样每次新插入的节点都位于链表头部，最终形成逆序链表。

✅ 头插法代码实现

#include <iostream>
#include <cstdlib>

typedef struct Node {
    int data;
    struct Node* next;
} Node, *LinkList;

// 初始化链表（带头结点）
Node* InitL(LinkList &L) {
    L = (Node*)malloc(sizeof(Node));
    L->next = NULL;
    return L;
}

// 头插法插入元素
void InsertNext(LinkList &L, int e) {
    while (e != 9999) {  // 以 9999 作为输入结束标志
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = e;
        p->next = L->next;  // 让新节点指向头结点的下一个节点
        L->next = p;        // 头结点指向新插入的节点
        
        std::cin >> e; // 读取下一个数据
    }
}

// 打印链表
void PrintL(LinkList &L) {
    Node* p = L->next;
    if (!p) {
        std::cout << "Empty List\n";
        return;
    }
    while (p) {
        std::cout << p->data << " -> ";
        p = p->next;
    }
    std::cout << "NULL\n";
}

// 释放链表
void FreeList(LinkList &L) {
    Node* p = L;
    while (p) {
        Node* temp = p;
        p = p->next;
        free(temp);
    }
    L = NULL;
}

int main() {
    LinkList L;
    InitL(L);

    int e;
    std::cin >> e;
    InsertNext(L, e);

    PrintL(L);
    FreeList(L);
    return 0;
}

📌 示例输入

1 2 3 4 5 6 9999

📌 示例输出

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> NULL

四、尾插法 vs. 头插法

🔹 总结

1. 尾插法：适合 顺序存储，需要维护 r 指针，但顺序符合直觉。
2. 头插法：适合 逆序存储，插入操作更简单，但最终数据顺序颠倒。
3. 二者的选择 取决于数据使用的需求，如：
   • 队列（FIFO） 适合尾插法。
   • 栈（LIFO） 适合头插法。

如果你是初学者，建议多尝试不同方法，以便深入理解链表的操作方式！ 🎯