【初阶数据结构与算法】第三篇：单链表

⭐️本篇博客我要给大家分享一下单链表。希望对大家有所帮助。
⭐️ 博主码云gitee链接：码云主页

前言

​

🌏一、链表

🍯1链表的概念及结构

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

🍯2链表的分类

🍤链表在逻辑上是连续的，但是在物理上不是连续的。

🍤现实中节点是从堆上申请的

🍯3链表自定义

SListNode* slist = NULL;
    SListNode* n1 = malloc(sizeof(SListNode));
    SListNode* n2 = malloc(sizeof(SListNode));
    SListNode* n3 = malloc(sizeof(SListNode));
    n1->data = 1;
    n2->data = 2;
    n3->data = 3;
    n1->next = n2;
    n2->next = n3;
    n3->next = NULL;
    slist = n1;

🍯4链表的实现

🍍单个节点的定义

🍤实现单个链表结构体

typedef int SLDataType;
typedef struct SListNode
{
    SLDataType data;//存储的数据
    struct SListNode* next;//下一个数据的地址
}SListNode;

🍤故使用typedef，后续若是需要修改，改动typedef就足够了

🍍链表的接口

//打印链表
void SListPrint(SListNode* phead);
//销毁链表
void SListDestory(SListNode** pphead);
//尾插
void SListPushBack(SListNode** pphead, SLDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SLDataType x);
//头删
void SListPopFront(SListNode** pphead);
//查找
SListNode* SListFind(SListNode* phead, SLDataType x);
//任意位置后插入
void SListInsertAfter(SListNode* pos, SLDataType x);
//任意位置后删除
void SListEraseAfter(SListNode* pos);

🍍单链表的打印

🍤不用断言phead，如果是空，就打印空

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

🍍单链表的尾插

🍤原来链表指向的是NULL，我们要让这个指向发生改变，指向这个新开辟的节点，节点应该是在堆上开辟的，因为形参是实参的一份临时拷贝，所以传参来改变指针的指向只能通过二级指针来改变，一级指针是不行的。传一级指针不会head的指向,关键是我们是是否需要改变Slist的值。

void SListPushBack(SListNode** pphead, SLDataType x)
{
    SListNode* newNode = BuySListNode(x);
    assert(pphead);
    //1.链表为空
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    //2.链表不为空
    else
    {
        SListNode* cur = *pphead;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = newNode;
    }
}

🍤错误：cur存放的是newNode的的值，函数结束的时候销毁函数，没有指向最后一个元素的next指向新插入的节点，不因该是用一个空指针指向next

SListNode* cur = *pphead;
        while (cur != NULL)
        {
            cur = cur->next;
        }
        cur->next = newNode;

🍤这里我把申请节点封装成了一个函数

SListNode* BuySListNode(SLDataType x)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

🍍单链表的头插

🍤头插比较简单，无论是链表为空还是不为空都不用单独考虑，只要考虑到传

二级指针

就可以很好的实现了。

void SListPushFront(SListNode** pphead, SLDataType x)
{
    //第一步,创建新节点
    SListNode* newNode = BuySListNode(x);
    //第二步,新结点链接原来的头结点
    newNode->next = *pphead;
    //第三步,phead指针指向新节点
    *pphead = newNode;
}

🍍单链表的尾删

🍤分三种情况判断，没有节点，一个节点，多个节点

void SListPopBack(SListNode** pphead)
{
    //分三种情况
    //1.没有节点
    //2.只有一个节点
    //3.两个及两个以上的节点
    //assert(*pphead);//暴力解决
    if (*pphead == NULL)
    {
        return;//温柔解决
    }
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);//释放指针指向空间
        *pphead = NULL;
    }
    else
    {
        SListNode* prev = NULL;//前一个节点
        SListNode* cur = *pphead;//当前节点
        while (cur->next != NULL)
        {
            prev = cur;
            cur = cur->next;
        }
        free(cur);
        cur = NULL;
        prev->next = NULL;
    }
}

🍍单链表的头删

🍤链表为空，链表不为空，两种情况讨论

void SListPopFront(SListNode** pphead)
{
    if (*pphead == NULL)
    {
        //让程序能继续
        return;
    }
    else
    {
        SListNode* firstNode = *pphead;
        //多结点，第一步,保留第二个结点地址
        *pphead = (*pphead)->next;
        //第二步,释放第一个结点
        free(firstNode);
        //第三步,连接第二个
        firstNode = NULL;
    }
}

🍍单链表的查找

🍤过给出的节点地址来查找，并返回该节点的地址，找不到就返回

NULL

SListNode* SListFind(SListNode* phead, SLDataType x)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

** 🍍单链表的在pos位置之后插入**

🍤找到目标结点之前结点

🍤创建新结点

🍤新结点链接目标结点

🍤原目标结点之前的结点链接新结点

🍤一下是两种写法，更推荐第一种，不用考虑顺序问题

void InsertAfter_Linked_list(Linked_list* pos, Linked_list_data x) {
    assert(pos);
    //指向pos的下一个位置
    Linked_list* next = pos->next;
    Linked_list* newnode = Application_Linked_list(x);
    //将pos指向newnode
    pos->next = newnode;
    //将newndoe指向next
    newnode->next = next;
}

void InsertAfter_Linked_list(Linked_list* pos, Linked_list_data x) {
    assert(pos);
    //申请一个新空间
    Linked_list* newnode = Application_Linked_list(x);
    //将pos的下一个节点地址存在newnode中(注意顺序不能调换)
    newnode->next = pos->next;
    //将pos指向newndoe
    pos->next = newnode;
}

** 🍍单链表的在pos位置之前插入**

void Insert_Linked_list(Linked_list** pphead, Linked_list* pos, Linked_list_data x) {
    assert(pphead);
    assert(pos);
    //pos是第一个节点
    //pos不是第一个节点
    if (*pphead == pos) {
        PushFront_Linked_list(pphead, x);
    }
    else {
        Linked_list* pre = *pphead;
        while (pre->next != pos) {
            pre = pre->next;
        }
        //创建一个新结构体
        Linked_list* newnode = Application_Linked_list(x);
        //将pre指向newnode
        pre->next = newnode;
        //将newnode指向pos
        newnode->next = pos;
    }
}

🍤更加推崇在pos位置之后插入，因为在pos位置之前插入要考虑是否为空

** 🍍单链表的在pos位置删除**

void Erase_Linked_list(Linked_list** pphead, Linked_list* pos) {
    assert(pos);
    assert(pphead);
    //判断是不是头删
    if (*pphead == pos) {
        PopFront_Linked_list(pphead);
    }
    else {
        Linked_list* cur = *pphead;
        while (cur->next != pos) {
            cur = cur->next;
        }
        //将pos指向要删除的结构体的下一个
        cur->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

** ** 🍍单链表的在pos位置之后删除

void EraseAfter_Linked_list(Linked_list* pos) {
    assert(pos);
    Linked_list* next = pos->next;
    if (next != NULL) {
        pos->next = next->next;
        free(next);
        next = NULL;
    }
}

🍤更推荐在pos位置之后删除，这样时间复杂度是O(n)，在pos位置删除时间复杂度是O(n)

🍍单链表的销毁

void Destroy_Linked_list(Linked_list** pphead) {
    assert(pphead);
    Linked_list* cur = *pphead;
    while (cur != NULL) {
        //保存cur的下一个
        Linked_list* next = cur->next;
        free(cur);
        cur = next;
    }
    //哨兵滞空
    *pphead = NULL;
}

总结

🍤适合头插头删.尾部或者中间某个位置插入删除不适合。
🍤双向链表比单链表更适合存储数据
🍤单链表学习的意义:

    1、单链表会作为复杂数据结构的子结构(图的邻接表、哈希桶)
     2、单链表会出很多经典的练习题