单链表初阶
1.链表的概念
在了解链表之前我们都或多或少的了解过顺序表，但是仔细想想，顺序表在进行增删的时候经常设计到数据的移动，就导致了运算速率底下，有没有一种结构，可以存储数据，并且增删时不用调用很多数据，兼容这些优点的就是链表。
链表和他的名字一样，像一条链子一样
和这个图一样，很多个数据之间存在某种关系，把链表的头比作火车头，链表的每个节点是火车的每个车厢，车厢内存储数据。
由于链表是一种抽象的概念，这里画出一个图来方便大家理解
2.节点
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”
plist是链表，指向的是第一个节点，然后第一个节点存储他的数据和第二个节点的地址，这样就可以通过上一个节点来找到第二个节点。
3.链表的性质
1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续 2、结点⼀般是从堆上申请的 3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码： 假设当前保存的结点为整型：
struct SListNode
{
int data; //结点数据
struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。 当我
们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。
4.链表的打印
打印链表，可以通过一个while循环，以指针指向空指针结束，其中打印一次，就让pcur=pcur->next，这样就可以实现链表的遍历了。
5.链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
assert(pphead&&*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
}
else
{
SLTNode* phead = *pphead;
SLTNode* prev = NULL;
while (phead->next)
{
prev = phead;
phead = phead->next;
}
free(phead);
phead = NULL;
prev->next = NULL;
}
}6.链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* tmp = SLTBuyNode(x);
SLTNode* ptail = *pphead;
if (*pphead == NULL)
{
*pphead = tmp;
}
else
{
while (ptail->next)
{
ptail=ptail->next;
}
ptail->next = tmp;
}
}7.链表的头删
void SLTPopFront(SLTNode** pphead)
{
SLTNode* phead = (*pphead)->next;
free(*pphead);
*pphead = phead;
}8.链表的尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead&&*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
}
else
{
SLTNode* phead = *pphead;
SLTNode* prev = NULL;
while (phead->next)
{
prev = phead;
phead = phead->next;
}
free(phead);
phead = NULL;
prev->next = NULL;
}
}9.小结
在链表的头删头插尾删尾插中使用了大量的二级指针，为了修改指针指向空间的地址，所以要对指针的地址来进行修改。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
