1. 链表的引入

❤️ 由于顺序表存在以下缺陷：

中间/头部的插入删除，时间复杂度为O(N)

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

为了解决以上问题，使得头部的插入删除的效率更高、空间不被浪费，我们引入了链表这一数据结构。

2. 链表的概念及结构

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

现实的数据结构中：这些箭头实际上是不存在的为了让我们更容易理解链表，在这里形象的引入了结点和结点之间用箭头所连接。

💕 注意：

从上图可看出，链式结构在逻辑上是连续的，但在物理上不一定连续。

现实中的结点一般都是从堆上申请出来的。

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

🧡 链表的分类：

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

1. 单向或者双向：

2. 带头或者不带头：

3. 循环或者非循环：

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

无头单向非循环链表：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

带头双向循环链表：

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3. 链表的实现

这里我们是以无头单向非循环链表为例，来实现并测试其各个接口函数，这里我们还是分为三个文件来实现这个链表。

SList.h :

头文件的包含、各个接口函数的声明和结构体类型的定义。

SList.c :

所有接口函数的实现。

Test.c :

测试各个接口函数的功能。

SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode {
   
   
    SLTDataType data;//数据域
    struct SListNode* next;//指针域
}SLTNode;

//开辟一个新的节点
SLTNode* BuySLTNode(SLTDataType x);

//打印链表
void SLTPrint(SLTNode* phead);

//链表尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);

//链表尾删
void SLTPopBack(SLTNode** pphead);

//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//链表头删
void SLTPopFront(SLTNode** pphead);

//查找并返回指定结点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos节点之后插入数据
void STLInsertAfter(SLTNode* pos, SLTDataType x);

//在pos节点之前插入数据
void STLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos节点之后的结点
void STLEraseAfter(SLTNode* pos);

//删除pos节点
void STLEarse(SLTNode** pphead, SLTNode* pos);

//销毁单链表
void SLTDestroy(SLTNode** pphead);

SList.c

❤️ 开辟一个新节点

SLTNode* BuySLTNode(SLTDataType x)
{
   
   
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (!newnode) {
   
   
        perror("malloc::");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

🧡 打印链表

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

💝 销毁单链表

void SLTDestroy(SLTNode** pphead)
{
   
   
    assert(pphead);
    SLTNode* cur = *pphead;
    SLTNode* nextnode = *pphead;
    while (cur)
    {
   
   
        nextnode = cur->next;
        free(cur);
        cur = nextnode;
    }
    *pphead = NULL;//头节点一定要置为空，防止对已销毁的链表进行非法操作
}

💘 链表的尾插尾删

//链表尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
   
   
    SLTNode* cur = NULL;
    SLTNode* prev = NULL;
    if (*pphead == NULL)
    {
   
   
        *pphead = BuySLTNode(x);
    }
    else
    {
   
   
        cur = *pphead;
        while (cur->next)
        {
   
   
            cur = cur->next;
        }
        cur->next = BuySLTNode(x);
    }
}
//链表尾删
void SLTPopBack(SLTNode** pphead)
{
   
   
    assert(pphead);
    SLTNode* cur = *pphead;
    SLTNode* prev = NULL;
    if ((*pphead)->next==NULL)
    {
   
   
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
   
   
        while (cur->next)
        {
   
   
            prev = cur;
            cur = cur->next;
        }
        free(cur);
        prev->next = NULL;
    }
}

💖 链表的头插头删

//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
   
   
    SLTNode* cur = BuySLTNode(x);
    if (!*pphead)
    {
   
   
        *pphead = cur;
    }
    else
    {
   
   
        cur->next = *pphead;
        *pphead = cur;
    }
}
//链表头删
void SLTPopFront(SLTNode** pphead)
{
   
   
    assert(pphead);
    SLTNode* cur = *pphead;
    *pphead = cur->next;
    free(cur);
}

💗 查找并返回指定节点

//查找并返回指定节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
   
   
    SLTNode* cur = phead;
    while (cur)
    {
   
   
        if (cur->data == x)
        {
   
   
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

💓 在pos节点之后插入节点

//在pos节点之后插入节点
void STLInsertAfter(SLTNode* pos, SLTDataType x)
{
   
   
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

💞 在pos节点之前插入节点

//在pos节点之前插入节点
void STLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
   
   
    assert(pos);
    if (pos == *pphead)
    {
   
   
        SLTPushFront(pphead, x);
        return;
    }
    //找到指定节点的前一个结点
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
   
   
        prev = prev->next;
    }
    //插入
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos;
    prev->next = newnode;
}

💕 删除pos节点之后的一个节点

//删除pos节点之后的一个节点
void STLEraseAfter(SLTNode* pos)
{
   
   
    if (pos->next == NULL)
        return;
    SLTNode* tmp = pos->next;
    pos->next = tmp->next;
    free(tmp);
}

❣️ 删除pos节点

//删除pos节点
void STLEarse(SLTNode** pphead, SLTNode* pos)
{
   
   
    assert(pos);
    assert(*pphead);
    if (pos == *pphead)
    {
   
   
        SLTPopFront(pphead);
        return;
    }
    SLTNode* prev = *pphead;
    while (prev->next!=pos)
    {
   
   
        prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SLIst.h"

void SLTNodeTest1()//链表的尾插尾删
{
   
   
    SLTNode* sl = NULL;
    SLTPushBack(&sl, 1);
    SLTPushBack(&sl, 2);
    SLTPushBack(&sl, 3);
    SLTPushBack(&sl, 4);
    SLTPrint(sl);
    SLTPopBack(&sl);
    SLTPopBack(&sl);
    SLTPopBack(&sl);
    SLTPopBack(&sl);
    SLTPopBack(&sl);
    SLTPrint(sl);

}

void SLTNodeTest2()//链表的头插头删
{
   
   
    SLTNode* sl = NULL;
    SLTPushFront(&sl, 1);
    SLTPushFront(&sl, 2);
    SLTPushFront(&sl, 3);
    SLTPushFront(&sl, 4);
    SLTPushFront(&sl, 5);

    SLTPrint(sl);
    SLTPopFront(&sl);
    SLTPopFront(&sl);
    SLTPopFront(&sl);
    SLTPopFront(&sl);
    SLTPopFront(&sl);
    SLTPrint(sl);
}

void SLTNodeTest3()//链表的指定结点之后、指定结点之前插入数据
{
   
   
    SLTNode* sl = NULL;
    SLTPushBack(&sl, 1);
    SLTPushBack(&sl, 2);
    SLTPushBack(&sl, 3);
    SLTPushBack(&sl, 4);
    SLTPushBack(&sl, 5);
    SLTNode* p = SLTFind(sl , 2);
    STLInsertAfter(p, 200);//指定节点之后插入节点
    SLTPrint(sl);
    p = SLTFind(sl, 5);
    STLInsert(&sl, p, 500);//指定节点之前插入节点
    SLTPrint(sl);
    p = SLTFind(sl, 1);
    STLInsert(&sl, p, 100);
    SLTPrint(sl);
}

void SLTNodeTest4()//删除指定结点之前的节点或者删除此结点
{
   
   
    SLTNode* sl = NULL;
    SLTPushBack(&sl, 1);
    SLTPushBack(&sl, 2);
    SLTPushBack(&sl, 3);
    SLTPushBack(&sl, 4);
    SLTPushBack(&sl, 5);
    SLTPrint(sl);
    SLTNode* p = SLTFind(sl, 2);
    STLEraseAfter(p);//删除指定结点之前结点
    SLTPrint(sl);
    p = SLTFind(sl, 4);
    STLEraseAfter(p);
    SLTPrint(sl);
    p = SLTFind(sl, 4);
    STLEarse(&sl, p);//删除指定节点
    SLTPrint(sl);
    p = SLTFind(sl, 1);
    STLEarse(&sl, p);//删除指定节点
    SLTPrint(sl);
}
void SLTNodeTest5()//单链表的销毁
{
   
   
    SLTNode* sl = NULL;
    SLTPushBack(&sl, 1);
    SLTPushBack(&sl, 2);
    SLTPushBack(&sl, 3);
    SLTPushBack(&sl, 4);
    SLTPushBack(&sl, 5);
    SLTPrint(sl);
    SLTDestroy(&sl);
    SLTPrint(sl);
}
int main()
{
   
   
    SLTNodeTest5();
    return 0;
}

4. 总结

本篇博客主要介绍了链表这种数据结构，并进行了单链表的增删查改的实现，让我们对链表这一数据结构有了一个初步的认识，后面还会介绍其他链表的实现，希望大家能够多多支持!

【数据结构】单链表

1. 链表的引入

2. 链表的概念及结构

3. 链表的实现

SList.h

SList.c

test.c

4. 总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】单链表

1. 链表的引入

2. 链表的概念及结构

3. 链表的实现

SList.h

SList.c

test.c

4. 总结

热门文章

最新文章

相关课程

相关电子书