本篇博客只讲：无头单向非循环链表

💨链表的概念及结构

✔概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

✔结构

✔结构的实现

typedefintSLTDataType;
typedefstructSListNode{
SLTDataTypedata;
structSListNode*next;
}SLTNode;

👇解释

🚩首先我将int类型重命名为SLDataType。虽然看起来名字长了麻烦，但是为了代码的可维护性。比如每一次你存数据都要写一次int，但如果你下次想存字符类型，那你是不是要把所有的int改成char？如果这么写，你只需要把typedef int SLTDataType;里的int改为char就行。

🚩因为是链表，我们看结构图有数据域和指针域，我就定义了一个结构体。数据域就是data，指针域必须是结构体指针，因为你下次链接那个数据肯定和这次一样，还是包括一个数据一个指向下一个节点的指针。

🚩struct前加typedef是为了重命名，重新命名的名字写在分号前，这里我重命名为SLTNode。不然每次写SListNode都要带上struct关键字。

🎈next是指针域，存的是下一个节点的地址。

🎈关于结构

逻辑结构：想象出来的

物理结构：实实在在地在内存中如何存储表示他们之间关系的

💨一些接口的实现

💨尾插

voidSListPushBack(SLTNode**pphead,SLTDataTypex) //尾插{
SLTNode*newnode= (SLTNode*)malloc(sizeof(SLTNode));
newnode->data=x;
newnode->next=NULL;
if(*pphead==NULL)
    {
*pphead=newnode;
    }
else    {
SLTNode*tail=*pphead;
while(tail->next!=NULL)
        {
tail=tail->next;
        }
tail->next=newnode;
    }
}

👇解析

🎈为什么要用到结构体二级指针？

🚩因为在主函数中，我们要定义一个结构体指针plist，只有定义了这个指针，我们才能调用结构体里面的两个成员变量。但当我们尾插的时候，一定要把指针的地址传过去，不然传的是形参而非实参。所以要用二级指针接收指针的地址。

①（）里面我定义了一个二级指针，和一个int类型的x，就是表示你插入的数据。你会怀疑你这不是写的SLTDataType吗？ 别忘记看上面结构的实现里，我把int重命名为SLTDataType。

②下面就是定义一个结构体指针newnode，后面是动态内存开辟的内容，以免造成浪费，用多少内存就造多少内存。

③让此指针指向的链表，数据域为x（即插入的数据），指针域为空。

④让二级指针判断是否传过来的结构体指针plist为空，因为你刚开始定义的plist要让他为空，如果为空则把刚开辟的newnode给plist。

⑤如果不为空。就把plist的地址（因为*pphead解引用就代表plist的地址）给新定义的尾指针tail，这样每次在链表尾部插入一个数据的时候，先让他判断尾指针的下一个指向的链表是否为空，不为空则继续判断再下一个链表是否为空。如果下一个为空，就把开辟的newnode给下一个尾指针指向的下一个链表。

💨简化动态内存开辟

如果写接口发现动态内存开辟使用频繁，可以使用函数来简化程序。

具体如下

SLTNode*BuySListNode(SLTDataTypex)
{
SLTNode*newnode= (SLTNode*)malloc(sizeof(SLTNode));
newnode->data=x;
newnode->next=NULL;
returnnewnode;
}

那么上面的代码就可以改为

SLTNode*newnode=BuySListNode(x);

接下来的接口都会这样写动态内存开辟。

💨打印链表

voidSListPrint(SLTNode*phead)  //打印链表{
SLTNode*cur=phead;
while(cur!=NULL)
    {
printf("%d->",cur->data);
cur=cur->next;
    }
printf("NULL\n");
}

🎈在插入等操作完成之后，就直接把指针传过来打印就行，不需要传指针的地址（&plist），因为我们不需要改变原来链表的数值。只是简单的打印。

💨头插

voidSListPushFront(SLTNode**pphead,SLTDataTypex) //头插{
SLTNode*newnode=BuySListNode(x);
newnode->next=*pphead;
*pphead=newnode;
}

这里使用二级指针和尾插同理。

🚩把头指针（plist）的地址给新开辟的结构体指针newnode的指针域，代表头指针已经成为下一个指向的链表的地址。

🚩再把新开辟的newnode地址赋给原来的头指针，自然而然我们插入的数据就是从头开始插入的。

💨头删

voidSListPopFront(SLTNode**pphead)  //头删{
SLTNode*next= (*pphead)->next;  //*和=优先级一样，要用()free(*pphead);
*pphead=next;
}

🚩删掉链表中第一个元素，就表示第一个为空了。

所以我们要把头指针的指针域，也就是下一个节点的地址（即原链表中第二个元素地址）赋值给一个结构体指针next。

🚩然后再释放掉头指针的地址（因为我们删的是头元素嘛，所以释放头指针）。

🚩再把原来第二个节点的地址给头指针。现在他就是第一个元素了，不再是第二个了。

💨尾删

voidSListPopBack(SLTNode**pphead)  //尾删{
//如果链表为空，直接returnif(*pphead==NULL)
    {
return;
    }
elseif((*pphead)->next==NULL)  //只有一个节点    {
free(*pphead);
*pphead=NULL;
    }
else    {
SLTNode*prve=NULL;
SLTNode*tail=*pphead;
while (tail->next!=NULL)
        {
prve=tail;
tail=tail->next;
        }
free(tail);
prve->next=NULL;
    }
}

尾删的时候就要考虑一下，是否为空链表的情况，以及只有一个结点的情况。

🚩先定义两个结构体指针，tail判断下一个结点是否为空，而prve就作为tail的前一个指针。

🚩如果tail的指针域tail->next不为空（即下一个结点不为空）。则把tail赋值给prve，自己进入下一个结点。

🚩只有当tail的指针域为空了，就代表这个结点是最后一个结点，那就释放tail，然后prve的指针域指向空，这样prve现在指向的结点就是链表的最后一个结点了。

🍳详细点说就是，比如链表总共三个结点，tail指向第三个结点，那么prve就指向第二个节点，你删掉第三个结点，那原来的第二个结点自然称为链表的最后一个结点。

如果我们想在某个位置前插入一个数据，那么我们需要先找到那个数据才能进行插入。

💨查找某个元素

SLTNode*SListFind(SLTNode*phead,SLTDataTypex) //查找{
SLTNode*cur=phead;
while (cur)
    {
if(cur->data==x)
        {
returncur;
        }
cur=cur->next;
    }
returnNULL;
}

🚩参数就是，在添加完链表之后，把链表头指针以形参的形式传过来，因为不改变链表元素数值，所以传值而不是传址，用一级指针接收。再把要查找的元素数值传过来。

🚩while循环表达的意思就是如果数据域等于我们要找的数值，就返回指针的地址。找不到就继续往下找，直到找到或者找完整个链表都没找到。

💨在某个位置插入

1.voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDataTypex) //在pos前插入x{
if (pos==*pphead)
    {
SListPushFront(pphead, x);
    }
else    {
SLTNode*newnode=BuySListNode(x);
SLTNode*prev=*pphead;
while (prev->next!=pos)
        {
prev=prev->next;
        }
prev->next=newnode;
newnode->next=pos;
    }
}

🚩要考虑到一种情况，如果要在第一个结点之前插入，不就成头插了吗，直接调用头插函数。

✨pos哪来的？ pos是插入的位置，在主函数中要写上以下内容

SLTNode*pos=SListFind(plist,3);
if(pos)
    {
SListInsert(&plist,pos,30);
    }

比如你在3前面插入一个30，那么你就先找到3，上面查找函数不是返回了cur的地址了吗？地址就给了pos，然后调用插入函数，比较然后插入即可。

💨删除某个位置的值

1.voidSListErase(SLTNode**pphead,SLTNode*pos) //删除pos位置的值{
if(pos==*pphead) //删除的是头结点    {
SListPopFront(pphead);
    }
else    {
SLTNode*prve=*pphead;
while (prve->next!=pos)
        {
prve=prve->next;
        }
prve->next=pos->next;
free(pos);
    }
}
//如果删除的是头结点，直接调用头删函数。//如果不想用二级指针的话，可以使用带头单链表，不需要改变传过来的指针。