数据结构之“线性表(单链表)”

精选原创

秃了也强了 2023-04-28 19:40:58 博主文章分类：数据结构与算法 ©著作权

文章标签 链表数据代码实现 文章分类 代码人生 yyds干货盘点 阅读数186

链表对于大家来说并不陌生，这里还是有必要的介绍一下：为什么称之为”链表“呢？因为形成链表的基本结构就像链子一样，一节连着一节的相互关系，在我们内存中用该结构存储的数据只要知道其中一个数据的位置就能顺着找到其它位置的数据，这就是我们数据结构“线性表”的其一“链表”结构。

一，基本形态

每个节点由一个存储数据和指针组成，“指针”的作用是为了指向下一个节点，形成链接关系。

首先了解单链表：

逻辑图：

解析：“head”指针变量指向头节点的空间，头节点成员“next”指针变量指向节点"1"的空间，节点“1”成员“next”指针变量指向节点“2”的空间，节点“2”成员“next”指向节点"3"的空间........直到最后一个节点“4”成员"next"指向NULL,表明之后就没有其它的节点数据

简易的说：由一个头指针指向链表的头节点，从头节点开始依次指向下一个节点，形成这样的链表形式。

物理图(内存中表示)：

总的来说：每个数据空间都存着下一个数据空间的地址，直到最后一个的数据空间存放的地址为NULL。

二，基本结构

了解了单链表的基本形态，下面以代码形式展示单链表的美妙之处：

单链表的基本结构：(在头文件进行定义，“C为例”)

typedef int SLDataType; //为了方便之处，将我们要存的数据类型进行重命名。以“int”为例

//单链表的基本结构
typedef struct SListNode
{
  SLTDataType data; //存储数据
  struct SListNode *next; //存储下一个节点指针”链接作用“。
}SLN; // 名字简化方便书写

单链表的基本结构实现了，下面针对这个结构完成一些基本接口函数功能：”增”，“删”，“改“，”查“。

三，基本功能

围绕”增”，“删”，“改“，”查“的基本功能声明以下函数：

注意：对各类函数的取名方式一定要通俗易懂！切忌不能随便以”a,b,c“等简简单单毫无相关的命名方式进行命名，推荐该函数的实现功能的相关英文来对此命名！

此单链表是以一个变量指针来保存该链表的起始位置，刚开始该”变量指针“是置NULL且不需对此初始化，一旦有数据要输入用动态开辟的空间来保存该数据，并用当前最后一个节点的空间指向新开辟的空间即可，如果是第一个节点则用该“变量指针”指向其节点即可。

void SListPrint(SLN *phead); //打印全部数据
void SListPushBack(SLN **phead, SLDataType x); //尾插数据
void SListPopBack(SLN **phead); //尾删数据
void SListPushFront(SLN **phead, SLDataType x); //头插数据
void SListPopFront(SLN **phead); //头删数据
void SListInsert(SLN **phead,SLN *pos, SLDataType x); //位置(前面)插入数据
void SListDelete(SLN **phead,SLN *pos); //删除数据
SLN* SListFind(SLN *phead, SLDataType x); //查找(返回地址，否则返回NULL)
void SListDestroy(SLN **phead); //销毁

注意：调用此些接口函数如果要改变其“变量指针”中的值，函数的传值方式必须用传址调用才能改变其址！切记：根据各类函数实现的因素进行传值或者传值需要深刻思想再继续决定编写

四，接口实现

以上几个示例中只有增加或者删除数据需要传址调用(因为会影响“变量指针”)，其余功能都不需要传址调用(不会影响“变量指针的值”)，如果是变量指针进行传址调用，函数形参用二级指针进行接收！

展示具体实现：

✨void SListPrint(SLN *phead); //打印全部数据

实现其功能要素：采用从头开始遍历方式，逐个输出每个节点的值，直到遇到最后一个节点指向NULL便结束打印。

代码实现：

void SListPrint(SLN *phead) //打印全部数据
{
  assert(phead); //确保头指针有数据
  
  //循环遍历方式，遇NULL结束
  SLN *cur = phead; //创建一个指针进行循环控制
  
  while(cur)
  {
    printf("->%d ", cur->data); 
    cur = cur->next; //进行下一个节点
  }
  
  printf("->NULL"); 
}

✨void SListPushBack(SLN **phead, SLDataType x); //尾插数据

实现其功能要素：尾插数据其两者情况：①头指针未指向任何节点(没有任何数据)让其指向新开辟空间节点。②正常尾插数据，先找到最后一个节点让其指向新开辟空间节点。

代码实现：

void SListPushBack(SLN **phead, SLDataType x) //尾插数据
{
  SLN *newnode = (SLN*)malloc(sizeof(SLN));
    if(!newnode)//判断开辟失败
    {
      printf("malloc fail\n");
      exit(-1);
    }
  	else
    {
      newnode->data = x;
    	newnode->next = NULL;
    }
  //先判断头指针是否指向节点
  if(*phead==NULL)
  {
    
    *phead = newnode;
  }
  else
  {
    SLN* cur = *phead;
    //找到尾节点，实现尾插
    while(cur->next)
    {
      cur = cur->next;
    }
    cur->next = newnode;
  }
  
}

逻辑图展示：

①开辟新节点，赋值并其指针指向NULL

②找到最后节点位置，并让其指向新节点实现尾插

✨void SListPopBack(SLN **phead); //尾删数据

实现其功能要素：实现尾删数据需注意：是否有节点满足我们删除。尾删最后一个节点时，记得把指向该节点的指针置NULL，避免”野指针“的问题！

代码实现：

void SListPopBack(SLN **phead) //尾删数据
{
  assert(*phead); //判断是否有节点
  //实现尾删时，因为头指针指向第一个节点，首先找到最后一个节点再对其删除(释放空间)
 	SLN *cur = *phead; //保存头节点
  //因单链表的性质：只能往后找，不能回顾之前的节点，一但释放当前空间，就不能使它前一个指针指向NULL，从而形成”野指针“
  //所以：
  SLN *prev = NULL; //保存"cur"上一个节点
  //找到尾节点
  while(cur->next)
  {
    prev = cur;// 记录前一个位置
    cur = cur->next;
  }
  
  free(cur); //尾删
  prev->next = NULL; //使其前一个节点置NULL
}

逻辑图展示：

①遍历到最后一个节点的同时保存其上一个节点位置

②将最后节点进行释放删除

③将其上一节点指向NULL实现尾删

✨void SListPushFront(SLN **phead, SLDataType x); //头插数据

头插数据相比尾插数据虽然不用先找最后一个节点，但在插入的过程中注意指针指向的先后顺序

实现其功能要素：头插时先让新节点指向头节点，再让头指针指向新节点使其成为新的头节点。这里不需格外考虑为空节点情况，如果为空正常头插并不影响。

代码实现：

void SListPushFront(SLN **phead, SLDataType x) //头插数据
{
  SLN *newnode = (SLN*)malloc(sizeof(SLN));
  if(!newnode)//判断开辟是否成功
  {
    printf("malloc fail\n");
    exit(-1);
  }
  else
  {
    newnode->data = x; //赋值
    newnode->next = *phead;//新节点指向头节点
    *phead = newnode; //头指针指向新节点，使其成为新的头节点;
  }
}

逻辑图展示：

①开辟新空间

②开辟成功，赋值并先将其指向头节点

③再将头指针指向新节点实现头插

✨void SListPopFront(SLN **phead); //头删数据

头删数据需要注意的是，释放头节点空间前先保存其下一个节点的地址。

实现其功能要素：头删数据考虑是否有节点满足删除。对其删除后将头指针指向下一个节点，使其成为新的头节点

代码实现：

void SListPopFront(SLN **phead) //头删数据
{
  assert(*phead); //断言
  //在删除头节点之前，先保存其下一个节点的地址
  SLN *cur = *phead; //保存头节点 
  SLN *nextnode = *cur->next; //保存头节点的下一节点地址
  
  free(cur); //删除头节点
  *phead = nextnode; 
}

逻辑图展示：

①保存头节点以及头节点的下一节点

②释放头节点空间

③将头指针指向下一节点地址实现头删

void SListInsert(SLN **phead,SLN *pos, SLDataType x); //位置(前面)插入数据

单链表实现在某个位置的前面插入数据比在某个位置的后面插入数据相对来说较为复杂点，因为单链表无法自行回顾之前的节点位置，则就需要一个临时变量来存储其前一个节点的地址。

实现其功能要素：在插入数据的过程中，结合了”尾删“的相关因素：保存该节点的前一节点的地址，在插入过程中顺序也很重要。如果此刻该链表还没有节点以及该链表只有一个节点则实现头插功能。

代码实现：

void SListInsert(SLN **phead,SLN *pos, SLDataType x) //位置(前面)插入数据
{
  assert(pos);
  assert(phead);
  SLN *newnode = (SLN*)malloc(sizeof(SLN));
  if(!newnode)//判断开辟是否成功
  {
    printf("malloc fail\n");
    exit(-1);
  }
  else
  {
    newnode->data = x; //赋值
    SLN *prev = NULL;
    SLN *cur = *phead;
    //判断无节点以及只有一节点情况
    if(*phead == pos)
    {
      newnode->next = cur;
      *phead = newnode;
    }
    else
    {
       //找到pos的前一个节点位置
    	while (cur != pos)
   	 {
     	 prev = cur;
    	 cur=cur->next;
  	 }
   	 //找到前一节点位置，进行链接插入
  	 newnode->next = cur;
   	 prev->next = newnode;
    }
   
  }
}

逻辑图展示：

①开辟新空间

②找到pos位置，并保存其前一节点地址

③先将新节点指向pos节点，再将前一节点指向新节点实现位置前插入

✨void SListDelete(SLN **phead,SLN *pos); //删除数据

删除某个位置的节点同样结合了“尾删”的因素

实现其功能要素：如果删除某个位置，在释放该空间前，先将其前一个节点链接该空间的后一个节点，再进行释放即可

代码实现：

void SListDelete(SLN **phead,SLN *pos) //删除数据
{
  assert(*phead);
  assert(phead&&pos);
  
  SLN *cur=*phead;
  SLN *prev=NULL;
  //如果是删除第一个节点需特别处理
  if(*phead == pos)
  {
    *phead = cur->next;
    free(cur);
  }
  //找到删除节点的前一节点
  while(cur!=pos) 
    prev = cur;
    cur = cur->next;
  }
  //将前一节点指向删除节点的下一节点，再释放删除节点
  prev->next = cur->next;
  free(cur);
}

逻辑图展示：

①找到需删除的节点以及保存其前一节点位置

②将前一节点指向其后一节点

③将其节点删除实现删除数据

✨SLN* SListFind(SLN *phead, SLDataType x); //查找(返回地址，否则返回NULL)

实现查找功能就是遍历整个单链表直到遇到要查找的那个数并返回该数的节点位置，如果遍历完整个链表都未找到则返回NULL。显而易见该单链表实现查找功能的时间复杂度为O(n)。

实现其功能要素：该功能分为找的到和找不到的情况进行处置。找到了返回该节点地址，找不到返回NULL

代码实现：

SLN* SListFind(SLN *phead, SLDataType x) //查找(返回地址，否则返回NULL)
{
  assert(phead); //如果链表为空则不进行查找
  //在循环内部找到了返回地址，循环结束则返回NULL
  SLN *cur = phead; //临时保存头节点
  
  while(cur)
  {
    if (cur->data == x)
      return cur;
    
    cur = cur->next;
  }
  
  return NULL;
}

//有了查找功能接口，就能利用接口来实现更改

//例如将链表中的“3”改为30

SLN *pos = SListFind(phead,3);//查找“3”节点位置

if(pos)//如果不为NULL则表示找到，改变即可
  pos->data = 30;

//链表中有多个相同的数，且需要更改该数之后的数

//例如链表中有3个三，需将第二个3改为30

SLN *pos = SListFind(phead, 3); //找到第一个三的位置
pos = SListFind(pos->next, 3); // 在该节点之后的节点开始找，即可找到第二个三的位置 
//同时也可利用循环，输出所有三的位置
int i=1;
while(pos)
{
  printf("第%d个三，地址：%p\n", i,pos);
  pos = SListFind(pos->next, 3);
}

✨void SListDestroy(SLN **phead); //销毁

将所有数据进行销毁利用循环方式依次遍历每个节点，同时并对其进行空间释放，最后将头指针置NULL即可。

显而易见释放空间的时间复杂度为O(n)。

实现其功能要素：因为每个节点的空间都是在内存的堆上开辟的，释放空间需遍历每个空间的地址对其进行释放。

注意：释放当前节点空间的前需保存下一节点的位置，否则释放完当前节点则找不到之后节点位置了。

且注意野指针的问题！

代码实现：

void SListDestroy(SLN **phead) //销毁
{
  assert(phead); 有效地址
  SLN *cur = *phead; //当前节点
  SLN *next =  NULL; //下一节点
  //遍历节点释放空间
  while(cur)
  {
    next = cur->next;
    free(cur);
    cur = next;
  }
 	//释放完所有空间后，将头指针置NULL
  *phead = NULL;
}

五，完结撒花🎇

以上就是该单链表的实现，可以发现单链表的插入和删除的时间复杂度都是O(1)，非常适合对数据的操作，但是读取数据的时间复杂度确实O(n)，跟线性表其一的“顺序表”的优缺点恰恰互补，所以如果单单只对数据进行读取的话“顺序表”的结构就非常适合，它支持随机访问。如果要对数据频繁进行“增”，“删”操作的话，这里的“单链表”结构就非常合适，所以我们生活中对一些数据的实际应用就可以很好的决择我们用什么结构来实现它，来大大提高效率。

数据结构不仅只于此，一起来深度学习更多神奇的数据结构吧！

数据结构之“线性表(单链表)”

数据结构之“线性表(单链表)”

一，基本形态

二，基本结构

三，基本功能

四，接口实现

五，完结撒花🎇

Recommend

Aurélia de Azambuja to Judge Luxembourg Design Awards 2023

MySQL学习笔记：数据类型-字段选型

What the US needs for future nuclear power tech to get off the ground

288Hz业界最高刷新率 TCL华星助力长虹超羽速电视AWE发布

Vinted Vitess Voyage: Chapter 1 - Autumn is coming | Vinted Engineering

How to prevent orphan words in text views on iOS and macOS

使用 Flutter 如何实现客户端证书验证 mtls

Transitional Serifs: Bridging Typeface History

Doing different: making a better world throughout the Windows 11 PC ecosystem

YouTube Music app now allows you to listen to podcasts

About Joyk