单链表

 
 

 

1.链表

 

1.1链表的概念和结构

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

 ​
     现实中            数据结构中
 

 

 

1.2链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构（2*2*2）：

1. 单向或者双向

   

2. 带头或者不带头（哨兵位的头结点）

   

3. 循环或者非循环

   

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势。

 

2.单链表的模拟实现

SList.h中

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDateType;//单链表结点结构
typedef struct SLTNode
{SLTDateType data;struct SLTNode* next;
}SLTNode;//单链表打印
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);
//结点前插入
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDateType x);
//删除该结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//结点后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
//删除该结点的后继
void SLTEraseAfter(SLTNode* pos);
//单链表的销毁
void SLTDestroy(SLTNode** pphead);//free完所有结点，将phead置空

 

SList.c中

💡ps：单链表是使用一个SLTNode*的指针plist（头指针）来维护的。

⚠注意1：

• 由于要通过函数接口来实现单链表的增删查改(修改单链表)，就要进行址传递，传入&plist

• 对于不需要修改单链表的接口，直接传入plist即可

 

⚠注意2：

• 由于单链表的初始化比较简单，我们在测试文件中(test.c)中，直接SLTNode* plist = NULL即可

• 单链表的销毁并不是简单地对头指针进行free，而是要对每个结点进行free

 

2.1单链表的打印

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

💡ps：由于一个结点存着下一个结点的地址，所以我们可以通过cur = cur->next的方式，来找下一个结点，遍历下去。

 

2.2单链表的尾插

SLTNode* BuyNewnode(SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");return NULL;}else{newnode->data = x;newnode->next = NULL;}return newnode;
}//链表的插入操作是不需要对phead进行判空的（因为空链表，phead就是NULL）
//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);//防止使用者传参时，传的plist而不是&plist特殊情况，如果是空链表，找不到尾结点，所以直接将newnode作为phead//1.构造新结点SLTNode* newnode = BuyNewnode(x);//特殊情况：空链表if (*pphead == NULL){*pphead = newnode;return;}else//一般情况：非空链表{//2.找到尾结点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//3.嫁接tail->next = newnode;}}

💡ps：对于单链表的尾部操作，需要先找到尾结点。时间复杂度：O(N)。

而且对于空链表的情况无法找到尾结点，需要特殊处理。

 

2.3单链表的头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyNewnode(x);newnode->next = *pphead;*pphead = newnode;SLTInsert(pphead, *pphead, x);
}

💡ps：头部操作只需要注意连接关系即可，时间复杂度为：O(1)

 

2.4单链表的尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//删除操作，链表不可为空//特殊情况，如果链表只有一个结点是找不到前驱的，要进行特殊处理SLTNode* tail = *pphead;if (tail->next == NULL)//1个结点的情况{free(tail);*pphead = NULL;}else//多个结点的情况{SLTNode* prev = NULL;//1.找到尾结点和尾结点的前驱while (tail->next != NULL){prev = tail;//每次去下一个，用prev记录下来tail = tail->next;}//2.删除尾结点，进行嫁接和NULLfree(tail);tail = NULL;prev->next = NULL;}}

💡ps：找尾，时间复杂度为O(N)

由于尾删需要找尾结点的前驱，而只有一个结点的链表无法找到尾结点前驱，需要进行特殊处理。

 

2.5单链表的头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);
}

💡ps：时间复杂度为O(N)

 

2.6单链表的查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}

 

2.7单链表的中间插入(在结点前插入)

//结点前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyNewnode(x);//特殊情况//头插if (pos == *pphead){SLTPushFront(pphead, x);}SLTNode* prev = *pphead;//1.找pos的前驱while (prev->next != pos){prev = prev->next;}//2.嫁接prev->next = newnode;newnode->next = pos;
}

💡ps：由于需要找结点pos的前驱，时间复杂度O(N)

当pos为首结点时，无法找到pos的前驱需要进行特殊处理（头插操作）

 

2.8单链表的中间删除(删除该结点)

//删除该结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//特殊情况//头删if (*pphead == pos){SLTPopFront(pphead);}SLTNode* prev = *pphead;//1.找前驱while (prev->next != pos){prev = prev->next;}//2.嫁接prev->next = pos->next;free(pos);
}

💡ps：由于需要找结点pos的前驱，时间复杂度O(N)

当pos为首结点时，无法找到pos的前驱需要进行特殊处理（头删操作）

 

2.9单链表的中间插入(在结点后插入)

//结点后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode = BuyNewnode(x);newnode->next = pos->next;pos->next = newnode;
}

 

2.10单链表的中间删除(删除该结点的后继)

//删除该结点的后继
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);//不能尾删SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;
}

 

2.11单链表的销毁

void SLTDestroy(SLTNode** pphead)//free完所有结点，将phead置空
{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

 

3.单链表的优缺点

优点：
1. 头部操作，效率很高，时间复杂度为O(1)
2. 结点之间不是连续存储的，在进行插入操作时，无法考虑增容。

 

缺点：
1. 不支持随机访问，即使知道是第几个结点，也要进行遍历才能找到该结点。
2. 尾部操作要找结点，效率低下(如果使用一个直接来指向尾结点，也可实现O(1)的效率)
 
💡ps：对于空链表进行尾部操作时，需要进行特殊处理，这个时候我们可以构造一个哨兵位的头结点，使问题简化。

 

4. 链表的经典OJ题目训练

1. 删除链表中等于给定值 val 的所有结点。 OJ链接

2. 反转一个单链表。 OJ链接

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接

4. 输入一个链表，输出该链表中倒数第k个结点。 OJ链接

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接

7. 链表的回文结构。OJ链接

8. 输入两个链表，找出它们的第一个公共结点。OJ链接

9. 给定一个链表，判断链表中是否有环。 OJ链接

10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL OJ链接

11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。

    要求返回这个链表的深度拷贝。OJ链接

12. 其他 。ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，以后大家自己下去以后 Leetcode OJ链接 + 牛客 OJ链接