【数据结构】单链表

🔥博客主页：小王又困了

📚系列专栏：数据结构

🌟人之为学，不日近则日退

❤️感谢大家点赞👍收藏⭐评论✍️

一、什么是链表

1.1链表的概念及结构

1.2单链表的结构

二、链表的实现

📒2.1创建节点

📒2.2头插

📒2.3头删

📒2.4尾插

💭链表为空的插入

💭链表不为空

📒2.5尾删

📒2.6查找

📒2.7在pos位置之前插入

📒2.8在pos位置之后插入

📒2.9删除pos位置

🗒️前言

在上一期中我们学习了顺序表，但它却有缺点，例如头插或从中间插入效率低等，而链表可以有效的解决这些问题。那么就让我们走进链表的学习。

一、什么是链表

1.1链表的概念及结构

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

结构

注意：

1.链式结构在逻辑上是连续的，但在物理上不一定连续。

2.节点都是从堆上申请的。

3.从堆上申请空间，是按一定策略分配的，申请的空间可能连续，也可能不连续。

1.2单链表的结构

typedef int STLDataType;typedef struct STLNode
{STLDataType date;struct STLNode* next;   
}STLNode;

这种链表被称为无头+单向+非循环链表

二、链表的实现

📒2.1创建节点

我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。
STLNode* BuyListNode(STLDataType x)
{STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));if (newnode == NULL){perroe("malloc");exit(-1);}newnode->date = x;newnode->next = NULL;return newnode;
}

📒2.2头插

要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表phead的值，然后将newnode的地址存放在phead中，形成新的链表。无论一开始有没有节点，头插都是相同的。
//头插
void STLPushFront(STLNode** pphead, STLDataType x)
{STLNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}

📒2.3头删

头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pphead就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。
//头删
void STLPopFront(STLNode** pphead)
{assert(*pphead);STLNode* newnode = (*pphead)->next;free(*pphead);*pphead = newnode;
}

📒2.4尾插

我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。

💭链表为空的插入

当我们传递的是plist的值，屏幕上并没有打印出我们想要的结果。这是为什么呢？

形参是实参的一份临时拷贝，形参的改变不会影响实参，phead的改变不会影响plist。临时变量出作用域销毁，phead和newnode销毁，找不带开辟的节点，会造成内存泄漏。

正确做法是要将plist的地址传递过去，我们通过解引用就可以改变plist。plist中存放的是指针，我们传递指针的地址要用二级指针接收。

💭链表不为空

链表不为空时，我们要找到尾节点。这里我们要注意不能使用 tail!=NULL 判断。这样我们无法把链表连接起来。

//尾插
void STLPushBack(STLNode** pphead, STLDataType x)
{assert(pphead);STLNode* newnode = BuyListNode(x);if (NULL == *pphead){*pphead = newnode;}else{STLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

📒2.5尾删

在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。
//尾删
void STLPopBack(STLNode** pphead)
{assert(*pphead);//只剩一个if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//多个else{STLNode* prev = NULL;STLNode* tail = *pphead;while (tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}
}

📒2.6查找

循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。
//查找
STLNode* STLFind(STLNode* phead, STLDataType x)
{STLNode* cur = phead;while (cur != NULL){if (cur->date == x){return cur;}cur = cur->next;}return 0;
}

📒2.7在pos位置之前插入

在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。
void STLInsert(STLNode** pphead, STLNode* pos, STLDateType x)
{assert(pos);if(pos == *pphead){STLPushFront(pphead, x);}else{STLNode* prev = *pphead;while(prev->next != pos){prev = prev->next;}STLNode* newnode = BuySListNode(x);newnode->next = pos;prev->next = newnode;}}

📒2.8在pos位置之后插入

这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。
void STLInsertAfter(STLNode* pos, STLDateType x)
{    assert(pos);STLNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}

📒2.9删除pos位置

有可能删除的是头节点，所以要传递二级指针。

void STLErase(STLNode** pphead, STLNode* pos)
{assert(pos);if(pos == *pphead){STLPopFront(pphead, x);}else{STLNode* prev = *pphead;while(prev->next != pos){prev = prev->next;}prev->next = newnode;free(pos);}}