数据结构——单链表(不带头节点)

简介: 链表是一种物理存储结构上非联系,非顺序的存储结构,但数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的概念

链表是一种物理存储结构上非联系,非顺序的存储结构,但数据元素的逻辑顺序是通过链表中的指针链接实现的


逻辑结构:


c1050e1ad3104b53ad8698b6f495c65b.png




实际物理结构:


ecfff507a0a64b249b2925d7103079cf.png



每个链表节点都有自己的地址,链表的物理结构实际上是前一个结点保存着下一个结点的地址


所以从上面图中可以看出:

1.链表在逻辑上是连续的,但在物理上不是连续的

2.现实中,每个结点都是从堆中申请的

3.在堆中申请空间,按照一定规则进行分配,所以两次连续的开辟空间可以连续,可能不连续


链表的分类

实际中的链表有多种结构

分别为:


带头节点或不带头结点

单向或双向

循环或不循环

所以链表一共有8种结构


但是常用的只有:不带头节点非循环单链表 和 带头循环双向链表两种


单链表的实现

这里我们介绍的是不带头节点非循环单链表


单链表的结构

一个节点即存放了元素的值,也存放了下一个节点的地址,所以在结构体中,定义一个SLTDataType类型的data,以及结构体的自引用:struct SListNode* next作为指向下一个节点的指针


所以结构体如下:


typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
1


到这里,我们知道了可以通过一个节点找到下一个节点,但是我们如何找到头节点呢?


解决办法就是用一个结构体类型的指针去指向头节点,也解释存放头节点的地址。





5899924843974743951b0d9df3b315ec.png



所以在接下来的函数中,传这个头指针就可以了


单链表的接口函数

创建节点函数

因为每个节点都需要在堆中开辟,所以可以封装成一个函数,需要调用malloc去开辟空间


同时,在这个函数中,将data的值存放到节点中,因为不知道当前下一个节点的地址,所以next指针赋为NULL,最后返回这个节点的地址


SLTNode* SLTBuyNode(SLTDataType x)
{
  SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
  if (new == NULL)
  {
  perror("malloc fail");
  return;
  }
  new->next = NULL;
  new->data = x;
  return new;
}


打印函数

从头节点开始,直到NULL,遍历链表,并且打印出来


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


尾插函数

在实现尾插函数前,如果此时头指针指向的为NULL,在尾插函数中便会改变头指针的指向,也就是改变头指针的值,如果这个函数是传的一级指针的话,虽然在尾插函数中改变了头指针的指向,但在主函数中,头指针的改变并没有改变


传一级指针的情况图如下

61b6ff50fad9442e973745151ab12739.png





71e84603a32b4ba5957b3aa07749c3e3.png


所以这样的情况下,就需要传二级指针,将头节点的二级指针pphead传过去,让后通过解引用*pphead去改变头指针的指向





76a1fe994c3c4898b1f9d3a55eda7814.png





所以在后面的会改变头指针指向的函数中,都需要传二级指针


接下来,实现尾插函数


我们应先创建节点,调用SLTBuyNode函数

接下来还有一点要注意的:

如果此时头指针是空,就说明它后面没有任何节点,所以需要把newnode的节点地址赋值给头指针

如果不为空,找到尾节点,在尾节点的后面插入新节点


这里还需要注意的一个点是:二级指针是头指针的地址,这个地址一定不能为空,如果为空就出问题了,所以在函数开始应用assert断言判断一下pphead是否为空


头节点的值可能为NULL,所以不用断言判断*pphead


void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  else
  {
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}
1


头插函数

头插函数在头部插入,所以一点会改变头指针的指向,所以仍需传二级指针


然后灵newnode->next等于*pphead,然会再将newnode的值赋给头指针


void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}


头删函数

头删函数一定会改变头指针指向,所以需要传二级指针


头删,一定必须是链表中有节点,如果没有节点,则头删没有意义,如果链表为空,那么头指针的值就为null,所以我们可以通过断言判断*pphead是否为空,同时仍需判断pphead,所以这个函数的开头需要断言2次


因为节点都是动态开辟出来的,所以要用free函数释放,如果直接直接free*pphead,那么后面的节点都找不到了,因为也free掉了next的值


所以可以定义一个head变量指向第一个节点,然后先将head->next赋给*pphead,接下来再free掉head就可以了


void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLTNode* head = *pphead;
  *pphead = head->next;
  free(head);
  head = NULL;
}


目录
相关文章
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
34 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
分布式计算 Hadoop Unix
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
45 1
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)