【数据结构】单链表---C语言版(全网最最最最细!小白必必必必看!!!有图有真相!)(一)

简介: 【数据结构】单链表---C语言版(全网最最最最细!小白必必必必看!!!有图有真相!)(一)

6aa83f29045d4dc09f6173c0d85a3362.jpg


🐸一、前言

终于放假啦!🤩🤩停更了两个月,在假期要把欠下的补回来&有规律的学习!🤓
本篇文章来自《数据结构与算法》 专栏,本篇的内容是单链表的学习,也是数据结构的基础,希望烙铁们可以理解消化哦🥰!!!

🐸二、单链表与顺序表的区别

🐵1.存储形式上的区别

顺序表 在物理上和逻辑上都是连续的

单链表 在物理上是不连续的,在逻辑上是连续的

🐵2.空间上的区别

顺序表一般有固定的空间大小,当空间不够时需要进行扩容,扩容时往往不能准确知道需要扩容的空间大小,很容易会造成空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

单链表 用一个空间申请一个空间,相比顺序表不那么浪费空间(并不是完全不浪费)

总结 :在存储数据时,如果知道具体空间大小,就用顺序表进行存储,不知道具体空间大小,就用单链表

🐵3.时间上的区别

1️⃣随机插入、删除元素的时间复杂度:

顺序表:时间复杂度为 O(n),因为其空间是连续的,在某个位置插入时,这个位置后面的元素都要往后挪动位置;

单链表:时间复杂度为 O(1),只需要改变前驱元素及插入删除元素的指向;

2️⃣查找指定元素,修改指定位置元素的时间复杂度:

顺序表:时间复杂度为 O(1),依靠下标直接可以找到指定元素,对其操作;

单链表:时间复杂度为 O(n),需要从链表头结点往下遍历;

🐸三、单链表详解

🍎创建单链表

🥰这里先创建三个文件:

1️⃣:SList.h文件,用于函数的声明

2️⃣:SList.c文件,用于函数的定义

3️⃣:Test.c文件,用于测试函数

建立三个文件的目的: 将单链表作为一个项目来进行编写,方便我们的学习与观察。

⭕接口1:定义结构体(SLTNode)

🥰请看代码与注释👇

//自定义类型
typedef int SLTDataType;
//创建单链表
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

⭕接口2:打印(SLTPrint)

🥰请看代码与注释👇

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

⭕接口3:释放(SLTDestroy)

🥰请看代码与注释👇

//释放
void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

⭕接口4:创建新结点(BuyLTNode)

🥰请看代码与注释👇

//创建新结点
SLTNode* BuyLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("mallic fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

⭕接口5:头插(SLTPushFront)

🥰请看代码与注释👇

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{ 
  assert(pphead);   //链表为空,pphead也不为空,因为他是头指针plist的地址
                    // *pphead 不能断言,链表为空,也需要能插入
  SLTNode* newnode = BuyLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

⭕接口6:尾插(SLTPushBack)

🚨主要思想就是 找尾,要注意尾插有两种情况:空链表和非空链表

很多烙铁容易找错,这里要找的是尾结点,而不是空

尾结点(tail):next为空的

🥰请看代码与注释👇

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuyLTNode(x);
  //1.空链表
  //2.非空链表
  if (*pphead == NULL)
  {
    *pphead = newnode;    //改变的结构体的指针plist(用结构体指针的地址)
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;    //改变的结构体尾结点
  }
}

目录
相关文章
|
3天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
10天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
9 0
|
10天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
10 1
|
10天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
10天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
7 0
|
10天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
8 0
|
11天前
数据结构——栈(C语言版)
数据结构——栈(C语言版)
|
11天前
数据结构——队列(C语言版)
数据结构——队列(C语言版)
|
2天前
数据结构——栈和队列
数据结构——栈和队列
|
5天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
12 3