数据结构(十)——头插法和尾插法建立单链表

😀前言
在数据结构中，单链表是一种常见的数据结构，它由一个头节点和若干个数据节点组成。创建单链表的过程可以通过头插法或尾插法来实现。头插法是将新节点插入到链表的头部，而尾插法是将新节点插入到链表的尾部。本文将介绍头插法和尾插法建立单链表的具体实现方法。

🏠个人主页：尘觉主页

💕欢迎大家：这里是CSDN，我总结知识的地方，欢迎来到我的博客，感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦😊

数据结构(十)——头插法和尾插法建立单链表

创建链表(头插法)O(n)

创建单链表的过程就是动态生成链表的过程，即从空表的初始状态起依次建立各元素结点，并逐个插入链表

• 单链表(Single Linked List)
• 单链表由头节点(不存放数据只存放下个节点的地址)和n个节点组成，
• 每个节点分为两个域：数据域和指针域(存放下个节点的地址)
• 第n个节点的指针域为NULL

void CreatLL_H(LinkList L, int n)
    //用此方法创建的链表，遍历的顺序和创建的顺序相反
    {
        printf("Please input %d numbers:", n);
        for (int i = 0; i < n; i++) {
            LinkList p = (LinkList)malloc(sizeof(LNode));
            int data;
            scanf(" %d", &data); //%d前面的空格代表清除制表符回车等符号
            p->data = data;
            p->next = L->next;
            L->next = p;
    }
}

创建链表(尾插法)O(n)

void CreatLL_R(LinkList L, int n) {
        printf("Please input %d numbers:", n);
        LinkList ptail;
        ptail = L;
        for (int i = 0; i < n; i++) {
            LinkList pnew;
            pnew = (LinkList)malloc(sizeof(LNode));
            int data;
            scanf(" %d", &data);
            pnew->data = data;
            pnew->next = NULL;
            ptail->next = pnew;
            ptail = pnew;
    }
}

总结插入和删除操作算法的不同

while (p){
	p = p->next;
}//最终p的值为NULL
	while(p->next){
	p = p->next;
}//最终p的值为最后一个节点的地址
//---------------------插入----------------------
//如果插入操作的position不合法，即position > n+1(n为链表长度)，那么p一定会指向NULL，此时按照退出条件!p可以返回ERROR
if (!p || i>position-1) return ERROR;
//但是如果采用:
while(p->next)
//则最终会指向链表最后一个节点，即使position不合法，那么也会在最后一个节点后方插入新节点
//所以使用:
while(p)
---------------------删除----------------------
//如果删除操作的positoin不合法，即position>链表长度，p会指向，最后一个节点的地址(position ==n+1时)或是NULL(position > n+1)，那么下面的代码会出错
LinkList pfree = p->next;
//如果p指向最后一个节点，此时pfree指向NULL。如果p指向NULL，此时pfree指向非法空间(不受主程序控制)，从而导致下面代码报错
*e = pfree->data;
//所以需要增加一个判断条件
if (i>position-1 || !p || !p->next) return ERROR;
//必须保证 !p 要在 !p->next的左边，即position > n+1 的情况
//这是因为如果 !p->next 在 !p 的左边，如果p指向NULL，那么NULL->next会报错

😄总结

通过头插法和尾插法可以有效地创建单链表。头插法的创建过程是从链表的头部开始，逐个插入新节点，最终得到的链表的顺序与插入顺序相反。而尾插法的创建过程是从链表的尾部开始，逐个插入新节点，最终得到的链表的顺序与插入顺序相同。两种方法都可以在O(n)的时间复杂度内完成链表的创建。在插入和删除操作时，需要注意判断位置是否合法，以避免出现错误。头插法和尾插法在不同的应用场景中有不同的优势，可以根据具体需求选择合适的方法来创建单链表。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持