AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

单向链表——C语言实现

2023-06-14 76
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 单向链表——C语言实现

1.链表的概念

在上篇文章，我们已经学习了顺序表，不知大家有没有发现顺序表在一定程度上是存在缺陷的，比如说：


空间不够了的时候需要扩容，扩容需要付出代价（特别是异地扩空间）

为了避免频繁扩容，我们满了基本都是扩2倍，可能会导致一定的空间浪费

顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入删除数据就需要挪动数据，效率不高

针对顺序表的缺陷，就有了链表来存储数据


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

链表的定义：


这里的data就是要存放的数据

2.单向链表接口的实现

下面是要介绍的常用到的链表接口函数以及实现方法：

//打印
void SListPrint(SLTNode* phead);
//创建新节点
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//头删
void SListPopBack(SLTNode** pphead);
//尾删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除
void SListErase(SLTNode** pphead, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);


2.1动态申请一个节点

由于我们每次给链表插入数据时，都需要动态开辟空间来申请节点，所以我们把这个过程封装成一个函数，方便后续操作。


动态申请一个节点的步骤是先向计算机内存申请一块空间，这里我们将申请的空间用指针变量newnode来存储，然后将newnode中的data赋值，因为这是新开辟的节点，所以暂时将newnode中的next指向空。


注意：为了提高程序的可靠性，我们在动态内存申请后记得检查是否申请失败了，如果申请失败了输出提示信息，并退出程序。


SLTNode* BuyListNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)//如果动态内存申请失败就退出程序
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

2.2单链表打印

打印链表就是一个遍历链表的过程，我们首先定义一个指针(cur)指向链表的头节点，然后输出该节点的值，然后将指针指向下一个节点（cur=cur->next),依次进行，直到cur为空指针时停止

void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;//将cur指向下一个节点
  }
  printf("NULL\n");
}


2.3单链表尾插

尾插，就是先找到链表中最后一个节点，然后将数据插入到最后。

但是，我们要先判断链表是否为空，如果链表为空，我们直接直接将链表的头指针赋予要插入的数据。

由于尾插要改变链表，所以传参要用二级指针，包括下面的尾插，尾删，头删等都要用二级指针传参


void SListPushBack(SLTNode** pphead, SLTDateType x)
{
  SLTNode* newnode = BuyListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}


2.4单链表头插

头插是比较简单的一种操作，只需要申请新节点，将新节点的next指向链表的头，再让新节点成为链表的头即可。

void SListPushFront(SLTNode** pphead, SLTDateType x)
{
  SLTNode* newnode = BuyListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

2.5单链表尾删

尾删：每次找到链表的最后一个节点和倒数第二个节点，然后释放最后一个节点所占的看空间并将最后一个节点置空，同时将倒数第二个节点的next指向NULL；如果链表只剩下一个节点，直接释放并置空该节点（这一步需要单独考虑）


注意：为了避免链表为空但有调用尾删的情况，我们需要断言一下，当传过来的链表是空链表的时候，程序就会报错



void SListPopBack(SLTNode** pphead)
{
  //保证链表不是空链表
  assert(*pphead != NULL);
  if ((*pphead)->next == NULL)
  {
    //当链表中只有一个节点
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    SLTNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    prev->next = NULL;
    free(tail);
    tail = NULL;
  }
}

2.6单链表头删

头删是将第一个节点释放然后指向第二个节点，在此之前需要定义一个指针next来保存第二个节点的地址。

void SListPopFront(SLTNode** pphead)
{
  //保证链表不是空链表
  assert(*pphead != NULL);
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}

2.7在pos位置插入x

在pos位置插入x分为两种情况，一种是在pos前位置插入x ，另一种是在pos后位置插入x，下面将分别为大家介绍：'

2.7.1在pos位置前插入x

在pos位置前插入x,只需要找到pos的前一个位置，我们把pos的前一个位置命名为posPrev，然后创建一个新节点newnode，将posPrev的下一个节点指向newnode，newnode的下一个节点指向pos即可，如下图：


void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead != NULL);
  assert(pos != NULL);
  SLTNode* newnode = BuyListNode(x);
  if (*pphead == pos)
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
  else
  {
    //找到pos的前一个位置
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
  }
}


2.7.2在pos位置后插入x

在pos位置后插入x比在pos位置前插入x要简单，不需要遍历链表即可完成

void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
    assert(pos != NULL);
    SLTNode* newnode = BuyListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}


2.8删除pos位置值

删除pos位置值也需要先找到pos的前一个节点，因此也要考虑pos是链表的头节点的情况

void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(*pphead != NULL);
  assert(pos != NULL);
  if (*pphead == pos)
  {
    *pphead = pos->next;
    free(pos);
  }
  else
  {
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = pos->next;
    free(pos);
  }
}

2.9 查找x的地址

查找x的地址，如果查找到了x，则返回该节点的地址，否则返回空指针。这个步骤也要遍历链表。

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* tail = phead;
  if (tail->data == x)
  {
    return tail;
  }
  while (tail ->data != x)
  {
    tail = tail->next;
    if (tail->data == x)
    {
      return tail;
    }
  }
  return NULL;
}


2.10销毁链表

销毁链表需要将所有节点所占的内存全部释放，再将链表的头置为空即可。

void SListDestroy(SLTNode** pphead)
{
  assert(*pphead != NULL);
  SLTNode* cur = *pphead;
  while (cur != NULL)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

3.完整代码

SList.h文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;//存放下一个链表的地址
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//创建新节点
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//头删
void SListPopBack(SLTNode** pphead);
//尾删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除
void SListErase(SLTNode** pphead, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pphead);


SList.c文件：

#include"SList.h"
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;//将cur指向下一个节点
  }
  printf("NULL\n");
}
SLTNode* BuyListNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)//如果动态内存申请失败就退出程序
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
  SLTNode* newnode = BuyListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
  SLTNode* newnode = BuyListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
  //保证链表不是空链表
  assert(*pphead != NULL);
  if ((*pphead)->next == NULL)
  {
    //当链表中只有一个节点
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    SLTNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    prev->next = NULL;
    free(tail);
    tail = NULL;
  }
}
void SListPopFront(SLTNode** pphead)
{
  //保证链表不是空链表
  assert(*pphead != NULL);
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* tail = phead;
  if (tail->data == x)
  {
    return tail;
  }
  while (tail ->data != x)
  {
    tail = tail->next;
    if (tail->data == x)
    {
      return tail;
    }
  }
  return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead != NULL);
  assert(pos != NULL);
  SLTNode* newnode = BuyListNode(x);
  if (*pphead == pos)
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
  else
  {
    //找到pos的前一个位置
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
  }
}
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pos != NULL);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(*pphead != NULL);
  assert(pos != NULL);
  if (*pphead == pos)
  {
    *pphead = pos->next;
    free(pos);
  }
  else
  {
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = pos->next;
    free(pos);
  }
}
void SListDestroy(SLTNode** pphead)
{
  assert(*pphead != NULL);
  SLTNode* cur = *pphead;
  while (cur != NULL)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}


总结：这篇文章主要写的是单向链表，后续将继续带领大家学习双向链表。如果我写的有什么的不好之处，请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~😘

文章标签：
C语言
存储
关键词：
链表c语言
单向链表
单向链表C语言
单向C语言
夏微凉
目录
相关文章
ephemerals__
|
18天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
45 4
c的前世今生
|
1月前
|
存储 缓存 C语言
C语言：链表和数组有什么区别
C语言中，链表和数组是两种常用的数据结构。数组是一种线性结构，元素在内存中连续存储，通过下标访问，适合随机访问且大小固定的情况。链表由一系列不连续的节点组成，每个节点存储数据和指向下一个节点的指针，适用于频繁插入和删除操作的场景，链表的大小可以动态变化。
c的前世今生
23 2
石小浪♪
|
1月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装，包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
石小浪♪
26 0
石小浪♪
|
1月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装，包括节点的创建、链表的初始化、数据的插入和删除，以及链表的打印等功能。
石小浪♪
16 1
石小浪♪
|
1月前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码，包括创建链表、插入、删除和打印等基本操作。
石小浪♪
22 1
ephemerals__
|
18天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
38 0
石小浪♪
|
1月前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法，包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除，以及链表的打印等功能。文章通过具体的代码示例，展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除，以及如何清空和销毁链表。
石小浪♪
31 0
单链表之无头链表(C语言版)
是店小二呀
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
45 1
java冯坚持
|
1月前
|
算法 Java
数据结构与算法学习六：单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例，详细讲解了约瑟夫环问题的解决方案，并提供了Java代码实现。
java冯坚持
20 0
石小浪♪
|
1月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表，并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现，以及一个示例程序来演示这些操作。
石小浪♪
24 0