AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构链表详解(不仅顺序表可以，我链表也可以)

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

我们上节学习了顺序表的实现.

顺序表的缺点：

  • 任意位置插入或者删除元素的效率低：每次插入或者删除需要搬移元素；
  • 考虑空间的大小是否需要开辟空间

以下为顺序表与链表的不同点

链表

链表的概念及其结构

概念：链表是一种物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链 接次序实现的 。

链表的分类

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然链表的类型很多，但是我们实际中最常用还是两种结构：

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

链表的实现

#pragma once
//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;
 
typedef struct SListNode {
  SLTDataType data;
  struct SListNode* 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);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
 
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

链表形式：

//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;
 
typedef struct SListNode {
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

节点的创建:

链表是一个个节点连接起来的，所以我们的第一步应该动态申请节点

//开辟新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)//判断开辟是否成功
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}

链表的增删：

尾插

我们先要创建一个存放x的新节点，然后找到节点的尾，在将为节点的next指向新节点

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
  if (*pphead==NULL) {
    *pphead = newnode;
  }
  else {
    //创建一个尾节点，找尾
    SLTNode* ptail = *pphead;
    while (ptail->next) {
      ptail = ptail->next;//找链表下一个为NULL的地址
    }
    //下一个为NULL，出循环
    ptail->next = newnode;
  }
}

头插

头插对于尾插简单不少，先创建新节点，将新节点的next指向头节点，然后将地址赋给头节点

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
  if (*pphead == NULL) {
    *pphead = newnode;
  }
  else {
    newnode->next = *pphead;
    *pphead = newnode;//头节点为新的节点
  }
}

尾删

//尾删
void SLTPopBack(SLTNode** pphead) {
  assert(pphead && *pphead);
  if ((*pphead)->next == NULL) {//->的优先级高于();
    //只存在一个节点
    free(*pphead);
    *pphead = NULL;
  }
  else {
    //找尾节点
    SLTNode* pcur = *pphead;//保存尾节点的上一个节点
    SLTNode* ptail = *pphead;
    while (ptail->next) {
      pcur = ptail;
      ptail = ptail->next;
    }
    free(ptail);
    ptail = NULL;
    pcur->next = NULL;
  }
}

头删

//头删
void SLTPopFront(SLTNode** pphead) {
  assert(pphead && *pphead);
  SLTNode* pcur = (*pphead)->next;
  free(*pphead);
 
  *pphead = NULL;
  *pphead = pcur;
}

查找 

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

打印

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

链表的重点

这是一串链表，在链表中的增删查改，其实是需要关注其节点；

1、尾删：则是需要找到尾节点，进行删除

如果我们将为释放掉，那尾节点的上一个节点，指向哪里，将会沦为野指针，是非常危险的，所以我们得创建一个指针，用来找到这个节点，这就是尾删的重点

2、头删：找到头节点的下一个节点，在删除头节点

与尾删类似，我们需要考虑如果将phead删除，我们如何找到新的头节点

综上所述：链表的难度常常发生在其释放时，指针的丢失或者成为野指针，如果注意其，我们将事半功倍，减少bug的产生；

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
 
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
 
//销毁链表
void SListDesTroy(SLTNode** pphead);

在指定位置之前插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
  assert(pphead && *pphead);
  assert(pos);
  SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
  if (pos == *pphead) {
    //头插
    SLTPushFront(*pphead, x);
  }
  else{
    SLTNode* prev = *pphead;
        //找到pos的上个节点
    while (prev->next != pos) {
      prev = prev->next;
    }
    newnode->next = pos;
    prev->next = newnode;
  }
}

在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
  assert(pos);
  SLTNode* newnode = SLTBuyNode(x);
  SLTNode* pcur = pos->next;
    //保存pos下一个节点，以防节点丢失
  pos->next = newnode;
  newnode->next = pcur;
}

删除pos之后的节点 

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

链表的摧毁

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

总体展示：

#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
#include<assert.h>
 
 
void SLTPrint(SLTNode* phead) {
  SLTNode* pcur = phead;
  while (pcur) {//pcur!=NULL
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("NULL\n");
}
 
//开辟新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}
 
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
  if (*pphead==NULL) {
    *pphead = newnode;
  }
  else {
    //创建一个尾节点，找尾
    SLTNode* ptail = *pphead;
    while (ptail->next) {
      ptail = ptail->next;//找链表下一个为NULL的地址
    }
    //下一个为NULL，出循环
    ptail->next = newnode;
  }
}
 
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
  if (*pphead == NULL) {
    *pphead = newnode;
  }
  else {
    newnode->next = *pphead;
    *pphead = newnode;//头节点为新的节点
  }
}
 
//尾删
void SLTPopBack(SLTNode** pphead) {
  assert(*pphead && pphead);
  //只有一个节点，直接释放掉
  if ((*pphead)->next == NULL) //-> 优先级高于*
  {
    free(*pphead);
    *pphead = NULL;
  }
  else {
      //链表有多个节点
 
      SLTNode* prev = *pphead;
      SLTNode* ptail = *pphead;
      while (ptail->next) {
        prev = ptail;
        ptail = ptail->next;
      }
      free(ptail);
      ptail = NULL;
      prev->next = NULL;
  }
}
 
//头删
void SLTPopFront(SLTNode** pphead) {
  //链表不能为空
  assert(pphead && *pphead);
 
  SLTNode* next = (*pphead)->next; //-> 优先级高于*
  free(*pphead);
  *pphead = NULL;
  *pphead = next;
 
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  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&&*pphead);
  assert(pos);
  SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
  //如果为头插
  if (pos == *pphead) {
    SLTPushFront(pphead,x);
  }
  else {
    SLTNode* prev = *pphead;
    while (prev->next != pos) {
      prev = prev->next;
    }
    //找到pos的上一个节点
    prev->next = newnode;
    newnode->next = pos;
  }
}
 
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = SLTBuyNode(x);
  SLTNode* pcur = pos->next;
  pos->next = newnode;
  newnode->next = pcur;
 
}
 
 
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && *pphead);
  assert(pos);
  //pos是头结点/pos不是头结点
  if (pos == *pphead)
  {
    //头删
    SLTPopFront(pphead);
  }
  else {
    SLTNode* prev = *pphead;
    while (prev->next != pos) {
      prev = prev->next;
    }
    prev->next = pos->next;
    //减少创建一个节点保存pos->next的节点
    free(pos);
    pos = NULL;
  }
}
 
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
  assert(pos && pos->next);
  SLTNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}
 
//销毁链表
void SListDesTroy(SLTNode** pphead) {
  assert(pphead&&*pphead);
  SLTNode* pcur = *pphead;
  while (pcur)
  {
    SLTNode* next = pcur->next;
    free(pcur);
    pcur = next;
 
  }
  *pphead = NULL;
}


以上我们完成了链表的实现，可以尝试一下使用顺序表或链表实现通讯录！！！！


文章标签：
存储
关键词：
数据结构链表
数据结构顺序表
数据结构顺序表链表
链表数据结构
链表顺序表
悲伤小伞
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
55 4
龙大吉
|
24天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
46 5
aliyun1622584902-46568
|
1月前
|
存储
顺序表和链表（2）
【10月更文挑战第23天】
aliyun1622584902-46568
56 2
顺序表和链表（2）
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
87 4
aliyun1622584902-46568
|
1月前
|
存储 算法 数据管理
顺序表和链表（1）
【10月更文挑战第22天】
aliyun1622584902-46568
23 2
肾透侧视攻城狮
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找等具体详解步骤以及举例说明
肾透侧视攻城狮
32 3
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
29 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
39 2
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
26 1
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
48 0