AI 助理
备案控制台
开发者社区 安全 文章 正文

【数据结构】无头+单向+非循环链表（SList）（增、删、查、改）详解

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

一、链表的概念及结构

1、链表的概念

之前学习的顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，而链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，可以实现更加灵活的动态内存管理。

注：之所以引出链表，是因为顺序表存在一些缺点。

  • 顺序表在中间 / 头部的插入和删除，需要挪动很多数据，时间复杂度为 O(N)，效率低下。
  • 增容需要申请新空间，拷贝数据，释放旧空间。消耗不小。
  • 增容一般是一次增长 2 倍，那就一定会造成空间浪费。例如当前的容量为 100，满了以后增容到 200，这时再继续插入 5 个数据，后面不再插入，那么就浪费了 95 个数据空间。

2、链表的组成

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：

  1. 数据域：存储数据元素。
  2. 指针域：存储下一个结点地址。

3、链表的结构

（1）链表的物理结构（现实中）

（2）链表的逻辑结构（想象中）

注：

  • 链式结构在逻辑上是连续的，但在物理上不一定连续。
  • 现实中的结点一般都是从堆上申请出来的。
  • 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

二、无头+单向+非循环链表的接口实现

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

1、创建文件

  • test.c（主函数、测试顺序表各个接口功能）
  • SList.c（单链表接口函数的实现）
  • SList.h（单链表的类型定义、接口函数声明、引用的头文件）

2、SList.h 头文件代码

// SList.h
// 无头+单向+非循环链表增删查改实现
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int SLTDateType;
 
typedef struct SListNode
{
    SLTDateType data; // 数据域
    struct SListNode* next; // 指针域
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 销毁单链表中所有节点
void SListDestory(SListNode** pphead)
// 单链表打印
void SListPrint(SListNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pphead);
// 单链表头删
void SListPopFront(SListNode** pphead);
// 单链表查找
SListNode* SListFind(SListNode* phead, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 求单链表长度
int SListSize(SListNode* phead);
// 单链表判空
bool SListEmpty(SListNode* phead);

三、在 SList.c 中实现各个接口函数

1、动态申请一个节点

// 动态申请一个节点
SListNode* BuyListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

2、销毁（释放）所有节点

// 销毁单链表中所有节点
void SListDestory(SListNode** pphead)
{
    assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur); // 释放节点
    cur = next;
  }
  *pphead = NULL;
}

注：assert() 放在函数里面检查参数，一方面是为了安全，另一方面是为了防止其他人在调用该函数时，出现不正确的使用，导致错误传入参数，这样可以及时提醒到他。所以写代码时一定要考虑到其他人不正确的使用该函数时的场景，以此避免不必要的麻烦。

3、单链表打印

// 单链表打印
void SListPrint(SListNode* phead)
{
    // 不需要断言 -- 空链表也可以打印
    SListNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

4、单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);  //动态申请一个节点
 
  if (*pphead == NULL) // 单链表中没有节点时
  {
    *pphead = newnode; // plist指向新节点
  }
 
  else // 单链表中已经有节点时
  {
    SListNode* tail = *pphead;
    while (tail->next != NULL) // 找到单链表中的最后一个节点
    {
      tail = tail->next;
    }
    tail->next = newnode; // 最后一个节点的next指向新节点
  }
}
 错误写法❌：

（传一级指针的值，用一级指针接收）指针传值，相当于把 plist 指针变量的值拷贝给 phead，给 phead 赋值 newnode，phead 的改变不会影响 plist。

// 错误写法：
// 单链表尾插
void SListPushBack(SListNode* phead, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);  //动态申请一个节点
 
  if (phead == NULL) // 单链表中没有节点时
  {
    phead = newnode; // plist指向新节点
  }
 
  else // 单链表中已经有节点时
  {
    SListNode* tail = phead; // 找到尾节点
    while (tail->next != NULL) // 找到单链表中的最后一个节点
    {
      tail = tail->next;
    }
    tail->next = newnode; // 最后一个节点的next指向新节点
  }
}

因为当链表为空时，我们需要改变 plist 的指向，使其指向第一个节点。而初始 plist 和 phead 都指向 NULL，调用函数后，phead 指向了新的节点，而 plist 还是指向 NULL 的。

解决方法：

plist 是指向第一个节点的指针，想要在函数中改变 plist 的值（指向），必须要把 plist 指针的地址 作为实参传过去，形参用二级指针接收，这样在函数中对二级指针解引用得到 plist 的值，就可以改变 plist 的值（指向）了。

  • 单链表为空时，plist 直接指向新节点。
  • 单链表不为空时，先找到单链表的尾节点，然后将尾节点的 next 指向新节点。

5、单链表头插

// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  SListNode* newnode = BuyListNode(x); // 动态申请一个节点
  newnode->next = *pphead; // 新节点的next指针指向plist指向的位置
  *pphead = newnode; // plist指向头插的新节点
}

6、单链表尾删

// 单链表的尾删
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
    assert(*pphead); //链表为空就无法再进行尾删了
 
  // 温柔处理方式
  /*if (*pphead == NULL)
  {
    return;
  }*/
 
  // 粗暴处理方式
  assert(*pphead);
 
  if ((*pphead)->next == NULL) // 链表一个节点
  {
    free(*pphead);
    *pphead = NULL;
  }
 
  else // 链表中有多个节点
  {
        // 写法一：
    /* SListNode* prev = NULL;
    SListNode* tail = *pphead;
    while(tail->next != NULL) // 找到链表的尾节点的上一个节点
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail); // 删除尾节点
    tail = NULL;
    prev->next = NULL;  // 置空 */
 
        //写法二：
    SListNode* tail = *pphead;
    while (tail->next->next != NULL) // 找到链表的尾节点的上一个节点
    {
      tail = tail->next;
    }
    free(tail->next); // 删除尾节点
    tail->next = NULL; // 置空
  }
}

  • 单链表只有一个节点时，删除节点，plist 指向 NULL。
  • 单链表有多个节点时，先找到单链表尾节点的上一个节点，删除尾节点，然后将该节点的 next 指向 NULL。
  • 因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。

7、单链表头删

// 单链表头删
void SListPopFront(SListNode** pphead)
{
  assert(pphead);
    assert(*pphead); // 链表为空就无法再进行头删了
 
  /*if (*pphead == NULL)
  {
    return;
  }
  else
  {
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
  }*/
 
  SListNode* cur = *pphead; // 保存头节点的地址
  *pphead = cur->next; // plist指向头节点的下一个节点
  free(cur); // 删除头节点
}

注：因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。

8、单链表查找指定值的节点

// 单链表查找
SLTNode* SListFind(SListNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur; // 找到了 返回该节点的地址
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL; // 未找到，返回NULL
}

9、单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos); // pos位置不能为空
  SListNode* newnode = BuySListNode(x); // 动态申请一个节点
  newnode->next = pos->next; // 新节点的next指针指向pos位置后一个节点
  pos->next = newnode; // pos位置的next指向新节点
}

为什么不在pos位置之前插入？
  • 单链表不适合在 pos 位置之前插入，因为需要遍历链表找到 pos 位置的前一个节点，时间复杂度为O(N)。
  • 单链表更适合在 pos 位置之后插入，如果在后面插入，只需要知道 pos 位置即可，简单得多。
  • C++ 官方库里面单链表给的也是在之后插入。

10、单链表删除指定pos位置之后的节点

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
  assert(pos); // pos位置不能为空
  assert(pos->next); // pos位置不能是尾节点
  SListNode* next = pos->next; // 保存pos位置的后一个节点
  pos->next = pos->next->next;
  free(next); // 释放pos位置的后一个节点
}

为什么不删除pos位置？
void SListErase(SListNode** pphead, SLTNode* pos) // O(N)
{
  assert(pphead);
  assert(pos);
 
  if (*pphead == pos)
  {
    /* *pphead = pos->next;
    free(pos); */
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    //pos = NULL;
  }
}
  • 删除 pos 位置同样需要传入单链表的二级指针。
  • 单链表不适合在 pos 位置插入，因为需要遍历链表找到 pos 位置的前一个节点，以改变其指向，时间复杂度大。

11、求单链表长度

// 求单链表长度
int SListSize(SListNode* phead)
{
  int size = 0;
  SListNode* cur = phead;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}

12、判断单链表是否为空

// 单链表判空
bool SListEmpty(SListNode* phead)
{
    // 写法一：
  return phead == NULL;
  
  // 写法二：
  //return phead == NULL ? true : false;
}

四、代码整合

// SList.c
#include "SList.h"
 
// 动态申请一个节点
SListNode* BuyListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
 
// 销毁单链表中所有节点
void SListDestory(SListNode** pphead)
{
    assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur); // 释放节点
    cur = next;
  }
  *pphead = NULL;
}
 
// 单链表打印
void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
 
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
  SListNode* newnode = BuySListNode(x);  //动态申请一个节点
 
  if (*pphead == NULL) // 单链表中没有节点时
  {
    *pphead = newnode; // plist指向新节点
  }
 
  else // 单链表中已经有节点时
  {
    SListNode* tail = *pphead;
    while (tail->next != NULL) // 找到单链表中的最后一个节点
    {
      tail = tail->next;
    }
    tail->next = newnode; // 最后一个节点的next指向新节点
  }
}
 
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  SListNode* newnode = BuyListNode(x); // 动态申请一个节点
  newnode->next = *pphead; // 新节点的next指针指向plist指向的位置
  *pphead = newnode; // plist指向头插的新节点
}
 
// 单链表的尾删
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
    assert(*pphead); //链表为空就无法再进行尾删了
  assert(*pphead);
 
  if ((*pphead)->next == NULL) // 链表一个节点
  {
    free(*pphead);
    *pphead = NULL;
  }
  else // 链表中有多个节点
  {
    SListNode* tail = *pphead;
    while (tail->next->next != NULL) // 找到链表的尾节点的上一个节点
    {
      tail = tail->next;
    }
    free(tail->next); // 删除尾节点
    tail->next = NULL; // 置空
  }
}
 
// 单链表头删
void SListPopFront(SListNode** pphead)
{
  assert(pphead);
    assert(*pphead); // 链表为空就无法再进行头删了
 
  SListNode* cur = *pphead; // 保存头节点的地址
  *pphead = cur->next; // plist指向头节点的下一个节点
  free(cur); // 删除头节点
}
 
// 单链表查找
SLTNode* SListFind(SListNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur; // 找到了 返回该节点的地址
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL; // 未找到，返回NULL
}
 
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos); // pos位置不能为空
  SListNode* newnode = BuySListNode(x); // 动态申请一个节点
  newnode->next = pos->next; // 新节点的next指针指向pos位置后一个节点
  pos->next = newnode; // pos位置的next指向新节点
}
 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
  assert(pos); // pos位置不能为空
  assert(pos->next); // pos位置不能是尾节点
  SListNode* next = pos->next; // 保存pos位置的后一个节点
  pos->next = pos->next->next;
  free(next); // 释放pos位置的后一个节点
}
 
// 求单链表长度
int SListSize(SListNode* phead)
{
  int size = 0;
  SListNode* cur = phead;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
 
// 单链表判空
bool SListEmpty(SListNode* phead)
{
    // 写法一：
  return phead == NULL;
}


文章标签：
存储
C++
安全
关键词：
数据结构链表
数据结构循环链表
单向链表
数据结构单向
数据结构无头单向循环链表
炫酷的伊莉娜
目录
相关文章
杀死一只知更鸟debug
|
9天前
|
Java
java数据结构，双向链表的实现
文章介绍了双向链表的实现，包括数据结构定义、插入和删除操作的代码实现，以及双向链表的其他操作方法，并提供了完整的Java代码实现。
杀死一只知更鸟debug
14 1
java数据结构，双向链表的实现
2的n次方_
|
1月前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
44 10
【数据结构】链表从实现到应用，保姆级攻略
百色彭于晏
|
2月前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
百色彭于晏
39 0
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
是基德吖
|
3月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
是基德吖
48 1
【数据结构OJ题】复制带随机指针的链表
chian-ocean
|
2月前
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
chian-ocean
83 4
aliyun6365824167
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
19 0
aliyun6365824167
|
2月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现（赋源码）
因为头结点的存在，plist指针始终指向头结点，不会改变。
aliyun6365824167
23 0
aliyun6365824167
|
2月前
|
存储 测试技术
【初阶数据结构篇】单链表的实现（附源码）
在尾插/尾删中，都需要依据链表是否为空/链表是否多于一个节点来分情况讨论，目的是避免对空指针进行解引用造成的错误。
aliyun6365824167
21 0
国中之林
|
2月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
国中之林
14 0
国中之林
|
2月前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
国中之林
13 0