[数据结构] -- 单链表

简介: [数据结构] -- 单链表

链表


概念

链表是一种物理存储结构上非连续、非顺序的存储结构,

数据元素的逻辑顺序是通过链表中的指针链接次序实现的,

单链表一般不会单独使用,
只有头插和头删实现简单且效率高


结构

链表也属于线性表,线性表在物理上存储时,

通常以数组(顺序表)和链式结构(链表)的形式存储,

链式结构在逻辑上是连续的,但在物理上不一定连续


现实中的结点一般是从堆上申请出来的

             

从堆上申请的空间,是按照一定的策略来分配的,

两次申请的空间可能连续,也可能不连续


链表的分类

单向链表和双向链表

单向链表(常用)

双向链表

带头(哨兵位) 或 不带头(哨兵位) 链表

带头(哨兵位) 链表

不带头(哨兵位) 链表

循环链表

带头双向循环链表(常用)


顺序表和链表的优缺点


顺序表 链表
存储空间 物理上一定连续 逻辑上连续,物理上不一定连续
访问 随机访问 不支持随机访问
任意位置插入或删除元素 效率低 修改指针指向
应用 空间不够扩容,元素高效存储,随机访问 分节点,开节点,可以在任意位置插入或删除


在SList.h文件中


定义单链表的结构

typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;   //数据
  struct SListNode* next; //指针域next
}SLTNode;

实现单链表的接口/方法

//打印链表
void SLTPrint(SLTNode* phead);    
 
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
 
//查找
SLTNode* SLTFind(SLTNode** phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);


在SList.c文件中


打印单链表(遍历链表)

//SLTNode*,表示 phead 是一个指向 SLTNode 类型的指针。
void SLTPrint(SLTNode* phead)   //接收一个指向链表头节点的指针 phead 作为参数
{
  //一级指针
  SLTNode* pcur = phead;
  while (pcur)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("NULL");
 
  printf("\n");
}

开辟空间

//开辟空间
SLTNode* SLTBuyNode(SLTDataType x)
{
  //为一个 SLTNode 类型的结构体分配内存,以便访问和操作这个新分配的 SLTNode 结构体
  //所以返回值为SLTNnode*
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(1);
  }
 
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}

开辟空间molloc返回值问题

函数原型:

尾部插入元素

//尾部插入元素
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
 
  SLTNode* newnode = SLTBuyNode(x);
  //头结点为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
    return;
  }
 
  //头结点不为空
  SLTNode* ptail = *pphead;
  while (ptail->next)
  {
    ptail = ptail->next;
  }
 
  ptail->next = newnode;
}

传参的时候为什么要传二级指针?

二级指针,在函数内部修改头指针本身的值

一级指针,用于遍历和访问链表

以下的 打印链表和销毁链表函数 说明一级和二级指针的意思

测试尾插

 

头部插入元素

//头部插入元素 
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
 
  SLTNode* newnode = SLTBuyNode(x);
 
  newnode->next = *pphead;  // *pphead表示头结点
  *pphead = newnode;
}

测试

尾部删除元素

free作用:

①free(ptail);之后,ptail指针本身的值并未改变,但它所指向的内存已经被释放,因此不应该再使  用这个指针访问已经被释放的内存。

②我们只需要确保不要再使用这个指针来访问内存,而不必将其置为NULL

//尾部删除元素 
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);  //保证头结点不为空
 
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
 
  //有多个结点
  SLTNode* ptail = *pphead;
  SLTNode* prev = NULL;
 
  while (ptail->next)
  {
    prev = ptail;
    ptail = ptail->next;
  }
  
  //单链表最后一个结点,只有数据域data且指针域的值是NULL
  // 释放尾节点的内存
  free(ptail);
 
  // 将尾节点的前驱节点的next置为NULL,实现删除尾节点 
  prev->next = NULL;
}

测试

头部删除元素

void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);  //保证头结点不为空
 
  SLTNode* next = (*pphead)->next;
 
  free(*pphead);
  *pphead = next;
}

测试

查找元素

//查找
SLTNode* SLTFind(SLTNode** phead, SLTDataType x)
{
  assert(phead);
 
  SLTNode* pcur = *phead;
  while (pcur)
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
 
  return NULL;
}

在指定位置之前插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
 
  SLTNode* newnode = SLTBuyNode(x);
  //pos刚好是头节点
  if (newnode->next == *pphead)
  {
    SLTPushBack(pphead, x);
    return;
  }
 
  //pos刚好不是头节点
  SLTNode* pcur = *pphead;
  while (pcur->next != pos)
  {
    pcur = pcur->next;
  }
 
  pcur->next = newnode;
  newnode->next = pos;
}

测试

删除pos节点

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
 
  //刚好是头节点
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
    return;
  }
 
  //不是头节点
  SLTNode* pcur = *pphead;
  while (pcur->next != pos)
  {
    pcur = pcur->next;
  }
  pcur->next = pos->next;
  free(pos);
  pos = NULL;
}

测试

在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
 
  SLTNode* newnode = SLTBuyNode(x);
 
  SLTNode* pcur = pos->next;
  pos->next = newnode;
  newnode->next = pcur;
}

删除pos之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
 
  SLTNode* p1 = pos->next;
  SLTNode* pcur = pos->next->next;
 
  pos->next = pcur;
 
  free(p1);
  p1 = NULL;
}

测试

销毁链表

//销毁链表
//SLTNode**,表示 pphead 是一个指向 SLTNode* 类型的指针的指针
void SListDesTroy(SLTNode** pphead)
{
  /*  pphead:(二级指针)*/
  assert(pphead);
 
  //一级指针
  assert(*pphead);//头结点不为空,链表不为空
 
  SLTNode* pcur = *pphead;  //*pphead 是头指针本身(一级指针),用于遍历和访问链表
  
  //先释放,后置空
  while (pcur)
  {
    SLTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  *pphead = NULL;
}
目录
相关文章
|
4月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
37 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
609 6