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

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. 头插法

方法	适用场景	特点	代码复杂度
尾插法	顺序存储 数据	- 适用于队列、链表等结构。 - 插入顺序与输入顺序一致。 - 插入操作需要维护尾指针 r。	适中
头插法	逆序存储 数据	- 适用于栈、回溯等结构。 - 输入数据被倒序存储。 - 插入操作比尾插法简单，始终修改 L->next。	更简单

🔹 总结

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

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