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

数据结构之单链表详解（C语言手撕）

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


一.链表的概念及结构

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

从图片中可以看出，链表的每个节点都是一个结构体，该结构体中有一个存储数据的变量和一个指向下一节点的结构体指针；
在逻辑上是连续的，但是在物理空间上不一定连续，因为链表节点都是每次插入数据时在堆上申请出来的；每次申请出来的空间不一定是连续的；

二.无头单向非循环链表的结构

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等；

二.无头单向非循环链表的结构及实现

一.结构：

二.功能函数的实现（含性能分析与图解）
  1. 打印链表
  2. 创建节点函数
  3. 头插节点函数
  4. 头删节点函数
  5. 尾插节点函数
  6. 尾删节点函数
  7. 查找函数
  8. 在一节点位置之前插入一个节点
  9. 在一节点位置之后插入一个节点
  10. 在一节点位置之前删除一个节点
  11. 在一节点位置之后删除一个节点
打印链表

图解：遍历访问

先定义一个结点指针指向头节点，往后依次遍历，与数组不同的是，不是cur++，而是让cur指向下一个节点，即cur=cur->next;

代码实现：

void SLPrint(SLNode* pphead)
{
  assert(pphead);     //断言
  SLNode* cur = pphead;     //让cur指向头节点进行遍历
  while (cur)        //注意：条件不是cur->next，因为如果是cur->next为空就不进入循环的话，则最后一个节点就访问不到
  {
    printf("%d ", cur->val);
    cur = cur->next;
  }
  printf("NULL");    //最后打印一个NULL、方便观察
  printf("\n");
}

性能分析：

时间复杂度：O(N)

空间复杂度：O(1)

创建节点函数

代码实现：

SLNode* BuySLnewnode(SLDateType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));   //注意：创建的是节点，一个结构体，而不是一个数据类型
  if (newnode == NULL)          //判断
  {
    perror("malloc fail");
    exit(-1);             //开辟失败，以异常退出程序
  }
  newnode->next = NULL;     //下一个节点置NULL
  newnode->val = x;         //赋值
  return newnode;           //返回该该结点指针
}
头插节函数

图解：

代码实现：

void SLPushFront(SLNode** pphead, SLDateType x)   
//注意：这里需要节点的二级指针，因为外面调用的时候，如果传的是头指针的话，是传值，
//函数里面改变不影响头指针的指向，所以这里需要二级指针，函数调用的时候需要传二级指针
{
  SLNode* newnode = BuySLnewnode(x);     //创建新节点
  if (*pphead == NULL)       //检查，如果为空链表
  {
    *pphead = newnode;      //直接将*pphead指向新节点
  }
  else
  {
    newnode->next = *pphead;    //第二种情况
    (*pphead) = newnode;
  }
}

性能分析：

时间复杂度：O(1)

空间复杂度：O（1）

头删节点函数

图解：

代码实现：

void SLPopFront(SLNode** pphead)
{
  assert(*pphead);    //头指针不能为空
  if((*pphead)->next==NULL)     //第一种情况
  {
    free(*pphead);     
    *pphead = NULL;
    return;
  }
  SLNode* tmp = (*pphead)->next;   //保存下一个节点
  free(*pphead);
  *pphead = tmp;
}

性能分析：

时间复杂度：O(1)

空间复杂度：O(1)

尾插节点函数

图解：

代码实现：

void SLPushBack(SLNode** pphead, SLDateType x)
{
  SLNode* newnode = BuySLnewnode(x);
  if (*pphead == NULL)     //空链表
  { 
    *pphead = newnode;
    return;
  }
  SLNode* tail = *pphead;     //定义一个尾指针
  while (tail->next)
  {
    tail = tail->next;
  }                           //退出循环后tail->next为NULL；
  tail->next = newnode;       //链接
}

性能分析：

时间复杂度：O(N)

空间复杂度：O(1)

尾删节点函数

图解：

代码实现：

在这里插入代码片void SLPopBack(SLNode** pphead)
{
  assert(*pphead);
  if ((*pphead)->next == NULL)   //第一种情况
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  SLNode* Prevtail = *pphead;    //记录尾指针前面的一个节点
  SLNode* tail = *pphead;        //尾指针
  while (tail->next)
  {
    Prevtail = tail;           
    tail = tail->next;
  }
  free(tail);             //释放掉尾节点
  Prevtail->next = NULL;   
}

性能分析：

时间复杂度：O(N)

空间复杂度：O(1)

查找函数

代码实现：

SLNode* SLFind(SLNode* pphead, SLDateType x)
{
  assert(pphead);
  SLNode* cur = pphead;       //遍历查找
  while (cur)
  {
    if (cur->val == x)
    {
      return cur;      //返回节点指针
    } 
    cur = cur->next;
  }
  return NULL;         //没找到，返回NULL
}

性能分析：

时间复杂度：O(N)

空间复杂度：O(1)

在pos位置之前插入一个节点

图解：

代码实现：

//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{
  assert(*pphead);
  assert(pos);
  if (pos == *pphead)        //第一种情况：头插
  {
    SLPushFront(pphead, x);
      
    return;
  }
  SLNode* newnode = BuySLnewnode(x);     
  
  SLNode* cur = *pphead;     //遍历，找到pos的前一个节点
  while (cur->next)
  {
    if (cur->next == pos)      //找到了
    {
      newnode->next = cur->next;    //链接
      cur->next = newnode;
      return;
    }
    cur = cur->next;
  }
}

性能分析：

时间复杂度：O(N)

空间复杂度：O(1)

在pos位置之后插入一个节点

图解：

代码实现：

//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x)
{
  assert(pos);
  SLNode * newnode = BuySLnewnode(x);     
  newnode->next = pos->next;   //链接
  pos->next = newnode;
}

性能分析：

删除pos位置之前一个节点

图解：

代码实现：

//删除pos之前的节点
void SLErase(SLNode** pphead, SLNode* pos)
{
  assert(pos);
  assert(pos != *pphead);
  if (pos== (*pphead)->next)  //头删，第一种情况
  {
    free(*pphead);
    (*pphead) = pos;
    return;
  }
  SLNode* cur = *pphead;
  while (cur)
  {
    if (cur->next->next == pos)   //找到pos前面的第二个节点
    {
      free(cur->next);
      cur->next = pos;     //链接
      return;
    }
    cur = cur->next;
  }
}

性能分析：

时间复杂度：O(N)

空间复杂度：O(1)

删除pos位置之后一个节点

图解：

代码实现：

//删除pos之后的节点
void SLEraseAfter(SLNode* pos)
{
  assert(pos);
  assert(pos->next);   //当pos后无节点，无意义
  if (pos->next->next == NULL)   //尾删
  {
    pos->next = NULL;
    return;
  }
  SLNode* cur = pos->next->next;   
  free(pos->next);   
  pos->next = cur;   //链接
  cur = NULL;
}

性能分析：

时间复杂度：O(1)

空间复杂度：O(1)

二.总代码
```cpp
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
typedef struct SListNode
{
  SLDateType val;
  struct SListNode* next;
}SLNode;
SLNode* BuySLnewnode(SLDateType x);
void SLPrint(SLNode* pphead);
void SLPushBack(SLNode** pphead, SLDateType x);
void SLPushFront(SLNode** pphead, SLDateType x);
void SLPopFront(SLNode** pphead); 
void SLPopBack(SLNode** pphead);
SLNode* SLFind(SLNode* pphead,SLDateType x);
//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos,SLDateType x);
//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x);
//删除pos之后的节点
void SLEraseBack(SLNode* pos);
//删除pos之前的节点
void SLErase(SLNode** pphead,SLNode* pos);
```cpp
#include"SList.h"
SLNode* BuySLnewnode(SLDateType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->next = NULL;
  newnode->val = x;
  return newnode;
}
void SLPrint(SLNode* pphead)
{
  assert(pphead);
  SLNode* cur = pphead;
  while (cur)
  {
    printf("%d ", cur->val);
    cur = cur->next;
  }
  printf("NULL");
  printf("\n");
}
void SLPushFront(SLNode** pphead, SLDateType x)
{
  SLNode* newnode = BuySLnewnode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    newnode->next = *pphead;
    (*pphead) = newnode;
  }
}
void SLPushBack(SLNode** pphead, SLDateType x)
{
  SLNode* newnode = BuySLnewnode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
    return;
  }
  SLNode* tail = *pphead;
  while (tail->next)
  {
    tail = tail->next;
  }
  tail->next = newnode;
}
void SLPopFront(SLNode** pphead)
{
  assert(*pphead);
  if((*pphead)->next==NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  SLNode* tmp = (*pphead)->next;
  free(*pphead);
  *pphead = tmp;
}
void SLPopBack(SLNode** pphead)
{
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  SLNode* Prevtail = *pphead;
  SLNode* tail = *pphead;
  while (tail->next)
  {
    Prevtail = tail;
    tail = tail->next;
  }
  free(tail);
  Prevtail->next = NULL;
}
SLNode* SLFind(SLNode* pphead, SLDateType x)
{
  assert(pphead);
  SLNode* cur = pphead;
  while (cur)
  {
    if (cur->val == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{
  assert(*pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
    return;
  }
  SLNode* newnode = BuySLnewnode(x);
  
  SLNode* cur = *pphead;
  while (cur->next)
  {
    if (cur->next == pos)
    {
      newnode->next = cur->next;
      cur->next = newnode;
      return;
    }
    cur = cur->next;
  }
}
//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x)
{
  assert(pos);
  SLNode * newnode = BuySLnewnode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//删除pos之后的节点
void SLEraseBack(SLNode* pos)
{
  assert(pos);
  assert(pos->next);
  if (pos->next->next == NULL)
  {
    pos->next = NULL;
    return;
  }
  SLNode* cur = pos->next->next;
  free(pos->next);
  pos->next = cur;
  cur = NULL;
}
//删除pos之前的节点
void SLErase(SLNode** pphead, SLNode* pos)
{
  assert(pos);
  assert(pos != *pphead);
  if (pos== (*pphead)->next)
  {
    free(*pphead);
    (*pphead) = pos;
    return;
  }
  SLNode* cur = *pphead;
  while (cur)
  {
    if (cur->next->next == pos)
    {
      free(cur->next);
      cur->next = pos;
      return;
    }
    cur = cur->next;
  }
}
三.性能分析

与顺序表相比：

优点：

1.按需申请，没有空间浪费；

2.头插头删效率高

缺点：

1.不支持下标随机访问

2.尾插尾删效率低

文章标签：
C语言
存储
关键词：
数据结构c语言
数据结构链表C语言
链表c语言
数据结构链表
C语言数据结构
GOTXX
目录
相关文章
ephemerals__
|
19天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
98 9
ephemerals__
|
18天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
60 16
ephemerals__
|
18天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
67 8
ephemerals__
|
21天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
48 4
ephemerals__
|
21天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
39 0
這～悸ベ雨落憂殇
|
存储 缓存 C语言
数据结构——双链表（C语言）
数据结构——双链表（C语言）
這～悸ベ雨落憂殇
46 0
7fa6b5ui5pmtk
|
5月前
|
存储
数据结构——双向链表（C语言版）
数据结构——双向链表（C语言版）
7fa6b5ui5pmtk
31 2
7fa6b5ui5pmtk
|
5月前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
46 2
Darknesscor
|
测试技术 C语言
数据结构单链表的实现（C语言）
数据结构单链表的实现（C语言）
Darknesscor
26 0
ForcibleBugMaker
|
6月前
|
存储 缓存 程序员
初阶数据结构之---顺序表和链表（C语言）
初阶数据结构之---顺序表和链表（C语言）
ForcibleBugMaker
86 1