首页单链表前插与后插

单链表前插与后插

时间: 2025-05-24 11:39:24 浏览: 15

### 单链表前插法与后插法实现详解 #### 前插法实现前插法是指将新节点插入到链表的头部。这种方法通常用于构建逆序排列的链表。以下是基于 C 语言的前插法代码实现： ```c void CreateList_Front(LinkList &L, int n) { L = (LinkList)malloc(sizeof(struct LNode)); // 创建头结点 L->next = NULL; // 初始化为空链表 for (int i = 0; i < n; ++i) { // 循环创建 n 个节点 LinkList p = (LinkList)malloc(sizeof(struct LNode)); // 新建节点 scanf("%d", &(p->data)); // 输入数据 p->next = L->next; // 将新建节点插入到头结点之后 L->next = p; // 更新头结点的指针 } } ``` 此方法的核心逻辑是每次都将新节点插入到链表的第一个有效节点之前[^3]。 --- #### 后插法实现后插法则是将新节点追加到链表的尾部。这种方式适用于顺序排列的数据序列。以下是基于 C 语言的后插法代码实现： ```c void CreateList_Rear(LinkList &L, int n) { L = (LinkList)malloc(sizeof(struct LNode)); // 创建头结点 L->next = NULL; // 初始化为空链表 LinkList tail = L; // 定义尾指针，初始指向头结点 for (int i = 0; i < n; ++i) { // 循环创建 n 个节点 LinkList p = (LinkList)malloc(sizeof(struct LNode)); // 新建节点 scanf("%d", &(p->data)); // 输入数据 p->next = NULL; // 设置新节点的 next 指向空 tail->next = p; // 当前尾节点的 next 指向新节点 tail = p; // 移动尾指针至新节点 } } ``` 在此方法中，`tail` 是一个辅助指针，始终指向当前链表的最后一个节点，从而能够快速定位并更新链表的尾部[^3]。 --- ### 性能比较 - **时间复杂度** - 前插法的时间复杂度为 \(O(n)\)，因为每插入一个节点仅需调整少量指针。 - 后插法同样具有 \(O(n)\

阅读全文