AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【数据结构入门】-链表之单链表（1）

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

回顾

在讲解链表之前我们先来看看顺序表有哪些缺陷呢？


1.空间不够需要增容，而增容就需要付出代价，realloc增容（一种是原地扩容，另一种是异地扩容）时会容易产生内存碎片（异地扩容时）。

2.顺序表为了频繁扩容，所以空间一旦满了基本上就是扩2倍，可能会存在空间的浪费（因为扩出来的空间可能用不了那么多）。

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

realloc原地扩容：


int main()
{
  int* p1 = (int*)malloc(10 * sizeof(int));
  int* p2 = (int*)realloc(p1, 11 * sizeof(int));
  return 0;
}

1.png

realloc（异地扩容）：


#include<stdlib.h>
int main()
{
  int* p1 = (int*)malloc(10 * sizeof(int));
  int* p2 = (int*)realloc(p1, 1000 * sizeof(int));
  return 0;
}

2.png

链表

针对顺序表存在的一些缺陷，所以就设计出来了链表。然而顺序表也并不是一无是处，对于顺序表是一块连续的空间，只需要存储第一个空间的地址，就可以找到所有的数据（对于这种物理上是连续的好处，比如a[i]等价于*(a+i)）。

而对于链表倘若要遍历所有的数据，就需要通过指针来进行链接（第一个存第二个的地址、第二个存第三个的地址、第三个存第四个的地址…），所以这也是链表的代价，每存储一个数据就需要伴随一个指针,即每个数据都要存一个指针去链接后面数据节点不支持随机访问（用下标直接访问第i个）。

同时链表一定程度上也更好的解决了顺序表头部、中间插入数据时还需要挪动数据。链表就不需要这么麻烦，只需要改指针的链接，不需要挪动数据。

这里指的是单链表，当然链表不仅仅只是这一种结构，我们先从最简单的单链表开始，循序渐进。


链表的概念及结构

概念：链表是一种物理存储结构上非连接、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，可以根据自己的需要按需申请空间。


typedef int SLTDateType;
struct SListNode
{
  SLTDateType data;//data就是我们要存储的数据
  struct SListNode* next;
};


各种节点

void SListPrint(SLTNode* phead);
void SListPushBack(SLTNode** pphead,SLTDateType x);
void SListPustFront(SLTNode** pphead, SLTDateType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找
//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//某个位置插入
//void SListInsert(SLTNode* phead, int pos, SLTDateType x);//某个位置插入
void SListInsertAfter(SLTNode* pos, SLTDateType x);
void SListErase(SLTNode** pphead, SLTNode* pos);
//void SListErase(SLTNode** phead, int pos);
void SListEraseAfter( SLTNode* pos);
void SListDestory(SLTNode** pphead);//销毁链表


打印链表

首先，phead是一个结构体指针指向第一个节点，cur也是如此，循环打印每个节点的数据就是通过cur = cur->next;走下去的，直到cur为空指针为止。

3.png


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


尾插

//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyListNode(x);
  //起初链表中是啥也没有的
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  else
  {
  //找到尾部=节点
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}


注意：第一种情况：倘若链表中起初啥也没有的，所以就需要我们先创建一个节点。

第二种情况：此时链表中是有数据的，此时我们要想尾插一个尾节点，就需要先找到尾。找到尾部节点的空指针后，直接把此空指针置为新节点的指针（即tail->next = newnode;）。

我们发现，即使链表是否为空，我们都需要新创建一个节点。所以我们专门分装一个专门创建一个节点的函数，并把这个节点的地址返回就好了。这样我们也方便以后头插等情况时候创建新节点。

还有一个点需要注意，请看这里：void SListPushBack(SLTNode** pphead, SLTDateType x)，我们在进行尾插的时候为什么要传二级指针过去呢？这的确是一个值得思考的问题。当我们想要进行尾插即SListPushBack(&plist, 1); SListPushBack(&plist, 2);的时候，如果我们不传plist的地址的话，那么在尾插函数（SListPushBack）内部pphead的改变是无法改变外部的plist的。所以我们就需要传plist的地址过去，此时我们也就需要二级指针来进行接收（因为plist本身就是一个指针）。

总之我们如果想改变plist的值的话，就需要将其地址传过去，否则形参就是实参的一份临时拷贝，形参的改变是无法改变实参的。


创建节点

S 

LTNode* 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 SlistPopBack(SLTNode** pphead)
{
  //温柔一点
  if (*pphead == NULL)
  {
  return;
  }
  //粗暴一点
  //assert(*pphead != NULL);
  //走到这里意味着一定有一个节点
  if ((*pphead)->next == NULL)
  {
  free(*pphead);
  *pphead = NULL;
  }
  else
  {
  SLTNode* prev = NULL;
  SLTNode* tail = *pphead;
  //while (tail->next != NULL)
  while (tail->next)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  tail = NULL;
  prev->next = NULL;
  }
}


进行尾删时总共三种情况：第一，链表为空；第二，链表只要一个节点；第三，链表有1个以上的节点。

这里我们来看一下最复杂的情况（第三种）：当链表有一个以上的节点时，当我们尾删链表的最后一个节点时，我们还需要把最后一个链表的前一个链表的next置为空指针，否则其就变成了野指针。但是由于单链表是无法找到前一个节点的next指针的。所以我们定义一个prev，在tail往下走（即tail = tail->next;）之前先进行prev = tail;。另外tail置不置空无所谓，因为出了tail的作用域其就被销毁了。


头插

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


头删

void SListPopFront(SLTNode** pphead)
{
  //空
  //一个节点
  //一个以上节点
  assert(pphead);
  //处理一个或者多个节点都可以，但是唯独不能处理节点为空
  /*if (*pphead == NULL)
  {
  return;
  }*/
  assert(*pphead != NULL);//节点为空直接报错
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
  //实际上我们可以把一个节点或者一个以上节点进行统一处理。
}


这里我们先明确一个问题，问题1：free（）释放的是指针呢？还是释放的是内存呢？应该是这样的：free释放的是指针指向的内存。

问题2：内存泄漏是内存丢了还是指针丢了？应该是这样的：内存泄漏是指针丢了，我们直到如果指针在的话（可以找到）我们依然可以随时释放指针指向的空间；但是如果指针真的丢了（找不到了）那我们连哪些内存没有释放都不知道。内存是不会丢的，因为内存一直是在那个位置，free只是把这块空间的使用权还给系统，同时把这块空间置为随机值。


查找

查找返回的是一个指针。


SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
  if (cur->data == x)
  {
    return cur;
  }
  else
  {
    cur = cur->next;
  }
  }
  return NULL;//来到这里说明到最后都没有找到，返回空
}


在pos之前去插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead);
  assert(pos);
  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;
  }
}


在pos之后去插入

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


注意：顺序不要颠倒（）newnode->next = pos->next; pos->next = newnode;。


删除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
  //相当于头删
  /**pphead = pos->next;
  free(pos);*/
  SListPopFront(pphead);
  }
  else
  {
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
  }
}



销毁链表

void SListDestory(SLTNode** pphead)//销毁链表
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
  SLTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  *pphead = NULL;
}


总代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;//data就是我们要存储的数据
  struct SListNode* next;
}SLTNode;
void SListPrint(SLTNode* phead);
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);//查找
//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//某个位置插入
//void SListInsert(SLTNode* phead, int pos, SLTDateType x);//某个位置插入
void SListInsertAfter(SLTNode* pos, SLTDateType x);
void SListErase(SLTNode** pphead, SLTNode* pos);
//void SListErase(SLTNode** phead, int pos);
void SListEraseAfter( SLTNode* pos);
void SListDestory(SLTNode** pphead);//销毁链表

Slist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
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 SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  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)
{
  //温柔一点
  if (*pphead == NULL)
  {
    return;
  }
  //粗暴一点
  //assert(*pphead != NULL);
  //走到这里意味着一定有一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* prev = NULL;
    SLTNode* tail = *pphead;
    //while (tail->next != NULL)
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;
  }
}
void SListPopFront(SLTNode** pphead)
{
  //空
  //一个节点
  //一个以上节点
  assert(pphead);
  //处理一个或者多个节点都可以，但是唯独不能处理节点为空
  /*if (*pphead == NULL)
  {
    return;
  }*/
  assert(*pphead != NULL);//节点为空直接报错
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;//来到这里说明到最后都没有找到，返回空
}
//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead);
  assert(pos);
  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;
  }
}
//在pos之后去插入，更合适，也更简单
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    //相当于头删
    /**pphead = pos->next;
    free(pos);*/
    SListPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//删除后一个
void SListEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);//报错就说明你用错来
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
  //next = NULL;//置不置空没有意义
}
void SListDestory(SLTNode** pphead)//销毁链表
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

Slist.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;//data就是我们要存储的数据
  struct SListNode* next;
}SLTNode;
void SListPrint(SLTNode* phead);
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);//查找
//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//某个位置插入
//void SListInsert(SLTNode* phead, int pos, SLTDateType x);//某个位置插入
void SListInsertAfter(SLTNode* pos, SLTDateType x);
void SListErase(SLTNode** pphead, SLTNode* pos);
//void SListErase(SLTNode** phead, int pos);
void SListEraseAfter( SLTNode* pos);
void SListDestory(SLTNode** pphead);//销毁链表
文章标签：
人工智能
存储
关键词：
数据结构链表
数据结构单链表
数据结构入门
链表数据结构
链表单链表
Parallel
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
54 4
龙大吉
|
23天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
44 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
83 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
26 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
36 2
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
48 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
57 0
数据分析螺丝钉
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
数据分析螺丝钉
49 0
数据分析螺丝钉
|
6月前
|
存储 SQL 算法
LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
数据分析螺丝钉
49 2
进朱者赤
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
进朱者赤
65 2