单链表的简单讲解

article/2025/9/20 8:58:39

注意：本人也是小白，如果出现错误希望各位读者能够包容

文章目录

  • 前言
  • 一、单链表的结构定义
  • 二、单链表的基本操作
    • 1.单链表的初始化
    • 2.单链表的创建
      • 1.头插法
          • 头插法图片讲解
      • 2.尾插法
          • 尾插法图片讲解
      • 3.头插法和尾插法的对比
    • 3.单链表的输出
    • 4.单链表的插入
      • 图片讲解（来自网上，仅供参考）
    • 5.单链表的删除
      • 图片讲解（来自网上，仅供参考）
  • 三、源码

前言

这次分享的是数据结构中单链表的创建和基本操作，这一部分是属于比较基础的内容，越是基础的越要投入精力去学习，不能眼高手低。在编写这篇博客的时候也出现了许多错误，这也算是一篇查漏补缺的博客。希望对大家有帮助。

一、单链表的结构定义

常规定义下的单链表，一般会包含数据域和指针域。

typedef struct node {int data;//数据域struct node* next;//指针域
}node,*linklist;//struct node可以用node替换	struct node*可以用linklist替换
//例如：struct node p	p是结构体node的变量  node q	q也是结构体node的变量
//struct node *p	p是结构体node的指针变量 linklist q q也是结构体node的指针变量
//想要详细了解，可以去查阅typedef和struct的用法

在这里插入图片描述
这个地方会出现两个让人比较迷的东西：结构指针node和linklist。本质上（可以自行去了解指针的深层的机制）而言，这两种类型是等价的。通常用linklist说明指针变量，强调它是某个单链表的头指针变量，定义为linklist L,L表示头指针。node用来定义单链表中结点的指针，例如node *p，p为结点的指针变量，p也可以定义为头结点。但是在方法的编写时，这两种定义会混合使用，非常容易迷惑我们的思维。所以我接下来的所有方法都只使用node来定义(当然你也可以两种都使用)。

二、单链表的基本操作

1.单链表的初始化

代码如下（示例）：

//初始化链表
void startlist(node* l) {l->next = NULL;
}
/*当然在主函数中是需要创建头结点的，你也可以换一种写法，可以不需要分配头结点内存的写法，请自行查阅node* l;l = (node*)malloc(sizeof(node));//分配头结点内存startlist(l);
*/

2.单链表的创建

1.头插法

//头插法创建单链表
void creatfromhead(node* head) {node* s;//新建一个结点指针变量int i = 1;int j;while (i != 0) {scanf("%d", &j);if (j != EOF) {s = (node*)malloc(sizeof(node));//新建一个结点，node*可以替换成linklists->data = j;//把输入的值赋值给新结点的指针域s->next = head->next;//把新结点插入到表头head->next = s;//头结点始终要放在表头}else {i = 0;}}
}
头插法图片讲解
//头插法核心代码
head->next = NULL;
s->next = head->next;
head->next = s;

单个结点
在这里插入图片描述
原始状态
在这里插入图片描述
第一个元素的插入过程（注意：1和2的过程不能颠倒，否则会导致链表缺失）
在这里插入图片描述
1表示把新结点插入到表头
2表示头结点始终要放在表头

第一个元素插入后
在这里插入图片描述
第二个元素的插入过程（其他元素也类似）
在这里插入图片描述
第二个元素插入后
在这里插入图片描述

2.尾插法

//尾插法
void creatfromtail(node* head) {node* s;//新建一个结点指针变量node* tail;//在建立一个尾结点指针变量int i = 1;int j;tail = head;//很重要的一步，令尾指针tail指向头结点head，便于做尾插入while (i != 0) {scanf("%d", &j);if (j != -1) {s = (node*)malloc(sizeof(node));//建立一个新结点s->data = j;tail->next = s;//尾指针的指针域指向新结点head（换一句话说，就是将新结点放在最后面）tail = s;//再让尾指针放在s后面，尾指针永远在最后面}else {i = 0;tail->next = NULL;//尾指针的指针域设置为空，表示链表结束}}
}
尾插法图片讲解
//核心代码
tail = head;
s->next = NULL;
tail->next = s;
tail = s;

原始状态
在这里插入图片描述
第一个元素的插入过程（注意：2和3的顺序不能颠倒，否则会导致链表生成出错）
在这里插入图片描述
1表示尾指针为空，链表结束
2表示将新结点放在链表的最后面
3表示尾指针一直指向链表的最后一个结点

第一个元素插入后
在这里插入图片描述
第二个元素插入的过程（其余元素的插入也类似）
在这里插入图片描述
第二个元素插入后
在这里插入图片描述

3.头插法和尾插法的对比

头插法建立链表的算法简短易懂，但是生成链表的结点顺序与原来输入的顺序相反，而用尾插法建立的链表可使输入和生成的结点顺序相同

原因：
根据上面的头插法和尾插法的算法，我们很容易知道，当用头插法依次插入值分别为1,2,3,4,5的结点（也叫做元素）后，单链表会如下图所示：

在这里插入图片描述
但是用尾插法同样插入值分别为1,2,3,4,5的结点后，单链表却会如下图所示：

在这里插入图片描述
而在这两个链表中，输出链表中各个元素的值只能从已知的头结点head开始遍历，所以分别用头插法和尾插法创建链表后，依次输出的元素的值刚好是相反的

3.单链表的输出

//输出链表
void printlist(node *l) {printf("该链表的内容为\n");;while (l->next != NULL) {printf("%d\t", l->next->data);l = l->next;}printf("\n");
}

4.单链表的插入

//单链表的插入
void enterlist(node* l, int i, int e) {node* p, * s;int k = 0;if (i <= 0) {printf("插入的位置不合理\n");}p = l;while (p != NULL && k < i - 1) {//查找第i-1个结点p = p->next;k++;}if (p == NULL) {//当遍历完整个表也没找到时，说明插入位置不合理（i过大） printf("插入的位置不合理\n");}s = (node*)malloc(sizeof(node));s->data = e;s->next = p->next;// 因为p时第i-1个结点 故 s的指针域应该指向第i个结点 p->next = s;printf("插入成功\n");
}

图片讲解（来自网上，仅供参考）

在结点p之前插入一个新的结点q:对于不带头结点的单链表，结点p的位置有所不同，插入操作有以下两种情况：

1)在链表的表头插入：

 	(1)创建一个新的结点q。(2)将此结点的数据域赋值为e，并将它的next指针指向第一个结点，即L。(3)将L修改为指向新的结点q。        操作示意图如下：

在这里插入图片描述
2)在链表的中间插入
(1)创建一个新的结点q。
(2)将此结点的数据域赋值为e，并将它的next指针指向p。
(3)查找到p的前驱结点pre。
(4)将pre的next指针指向新创建的结点q。
操作示意图如下：
在这里插入图片描述

//不带头结点的单链表的插入操作void LinkedListInertQE1(LinkedList L, LinkedList p, ElemType e){q=(LNode *)malloc(sizeof(LNode));        //创建一个新的结点qif(q==NULL){printf("申请空间失败！");exit(0);}q->data=e;if(p==L)   //在表头插入{q->next=L;L=q;}else      //在表的中间进行插入{pre=L;while((pre!=NULL)&&(pre->next!=p))           //寻找p的前驱pre=pre->next;q->next=pre->next;pre->next=q;}}//带头结点的单链表的插入操作void LinkedListInertQE2(LinkedList L, LinkedList p, ElemType e){q=(LNode *)malloc(sizeof(LNode));        //创建一个新的结点qif(q==NULL){printf("申请空间失败！");exit(0);}q->data=e;//插入新的结点pre=L;while((pre!=NULL)&&(pre->next!=p))           //寻找p的前驱pre=pre->next;q->next=pre->next;pre->next=q;}

5.单链表的删除

//单链表的删除操作
void dellist(node* l, int i) {node* p, * r;int k = 0;p = l;while (p->next != NULL && k < i - 1) {p = p->next;k++;}if (p->next == NULL) {printf("删除位置不合法\n");}r = p->next;p->next = r->next;printf("删除的元素是%d\n", r->data);free(r);
}

图片讲解（来自网上，仅供参考）

删除链表中的某个元素e，如果e在链表中出现不止一次，将删除第一次出现的e，否则什么也不做。 用p找到元素e所在的结点：

 1)p是链表中的第一个结点            (1)将L指向p->next。            (2)释放p。          示意图如下：

在这里插入图片描述
2)p是链表中的其他结点
(1)找到p的前驱结点pre。
(2)将pre->next指向p->next。
(3)释放p。
示意图如下：
在这里插入图片描述

//不带头结点的单链表的删除操作void LinkedListDeleteQE1(LinkedList L, LinkedList p, ElemType e){pre=L;while((pre!=NULL)&&(pre->next->data!=e))      //查找元素e的前驱pre=pre->next;p=pre->next;if(p!=NULL)                //找到需要删除的结点{if(p==L)                 //删除的是第一个结点L=p->next;else                     //删除的是其他结点pre->next=p->next;free(p);}}//带头结点的单链表的删除操作void LinkedListDeleteQE2(LinkedList L, LinkedList p, ElemType e){pre=L;while((pre!=NULL)&&(pre->next->data!=e))      //查找元素e的前驱pre=pre->next;p=pre->next;if(p!=NULL)                //找到需要删除的结点{pre->next=p->next;free(p);}}

三、源码

#include<stdio.h>
#include<stdlib.h>
#define _CRT_SECURE_NO_WARNINGS//链表结构
typedef struct node {int data;struct node* next;
}node,*LinkList;//初始化链表
void startlist(node* l) {l->next = NULL;
}//头插法
void creatfromhead(node* head) {node* s;int i = 1;int j;while (i != 0) {scanf("%d", &j);if (j != EOF) {s = (node*)malloc(sizeof(node));s->data = j;s->next = head->next;head->next = s;}else {i = 0;}}
}//尾插法
void creatfromtail(node* head) {node* s;node* tail;int i = 1;int j;tail = head;while (i != 0) {scanf("%d", &j);if (j != -1) {s = (node*)malloc(sizeof(node));s->data = j;tail->next = s;tail = s;}else {i = 0;tail->next = NULL;}}
}//输出链表
void printlist(node *l) {printf("该链表的内容为\n");;while (l->next != NULL) {printf("%d\t", l->next->data);l = l->next;}printf("\n");
}//按序号查找
node* search1(node* l, int i) {node* p;int j = 0;if (i <= 0) {return NULL;}p = l;while (p->next != NULL && j < i) {p = p->next;j++;}if (i == j) {return p;}else {return NULL;}
}//按值查找
node* search2(node* l, int e) {node* p;p = l->next;while (p != NULL) {if (p->data != e) {p = p->next;}else {break;}}return p;
}//求单链表的长度
int length(node* l) {node* p;p = l->next;int j = 0;while (p != NULL) {p = p->next;j++;}return j;
}//单链表的插入
void enterlist(node* l, int i, int e) {node* p, * s;int k = 0;if (i <= 0) {printf("插入的位置不合理\n");}p = l;while (p != NULL && k < i - 1) {p = p->next;k++;}if (p == NULL) {printf("插入的位置不合理\n");}s = (node*)malloc(sizeof(node));s->data = e;s->next = p->next;p->next = s;printf("插入成功\n");
}//单链表的删除操作
void dellist(node* l, int i) {node* p, * r;int k = 0;p = l;while (p->next != NULL && k < i - 1) {p = p->next;k++;}if (p->next == NULL) {printf("删除位置不合法\n");}r = p->next;p->next = r->next;printf("删除的元素是%d\n", r->data);free(r);
}int main() {node* l, * m;l = (node*)malloc(sizeof(node));startlist(l);printf("单链表已初始化\n");printf("用头插法插入链表l\n");creatfromhead(l);printlist(l);m = (LinkList)malloc(sizeof(node));startlist(m);printf("用尾插法插入链表m\n");creatfromtail(m);printlist(m);printf("查找链表m的第i个结点\n");int k;scanf("%d", &k);node* s;s = search1(m, k);printf("链表中第i个结点的值为：%d\n", s->data);printf("单链表的长度为：%d\n", length(m));printf("在链表m的第一个结点插入2\n");enterlist(m, 1, 2);printlist(m);printf("删除链表m中的第二个结点的值\n");dellist(m, 2);printlist(m);
}

效果图：
在这里插入图片描述


http://chatgpt.dhexx.cn/article/mApA34C5.shtml

相关文章

线性表之单链表~

线性表之单链表~

这次来介绍一下数据结构里面的单链表。 这是一个简单的链表&#xff0c;它是单向的&#xff0c;没有(哨兵位置)头结点&#xff0c;不循环&#xff0c;有一个头指针指向第一个节点。 和上次介绍线性表一样&#xff0c;我们同样研究它的 增&#xff0c;删&#xff0c;查&#x…
阅读更多...
链表(Linked List)----单链表

链表(Linked List)----单链表

链表是有序的列表,但是它在内存中是存储如下的: 链表是以节点的方式存储的,链式存储每个节点包含data域,next域指向下一个节点如上图:链表的各个节点不一定是连续存放的.链表分带头节点的链表和没有头节点的链表(根据实际的需求来确定) 使用带head头的单项链表实现-水浒英雄排行…
阅读更多...
单链表的插入与删除

单链表的插入与删除

链表是数据结构中的一种线性结构&#xff0c;表示数据运算之间的一种抽象关系。 1、单链表的结构如下&#xff1a; typedef struct node{datatype data; //数据struct node *next; //指向下一个节点的指针 }linklist_s; 其中包括一个数据域和一个指针域&#xff0c;向单链表…
阅读更多...
详解单链表（内有精美图示哦）

详解单链表（内有精美图示哦）

全文目录 引言链表链表的定义与结构链表的分类 单链表的实现及对数据的操作单链表的创建与销毁创建销毁 单链表的打印单链表的头插与头删头插头删 单链表的尾插与尾删尾插尾删 单链表的查找单链表在pos位置后插入/删除插入删除 单链表在pos位置插入/删除插入删除 总结 引言 在…
阅读更多...
【数据结构】单链表（超全）

【数据结构】单链表（超全）

目录 一、什么是链表&#xff1f;1.1 定义1.2 链表的分类 二、无头单向非循环链表2.1 结构2.2 如何遍历链表数据2.3 尾插2.4 创建新节点2.5 头插2.6 尾删2.7 头删2.8 单链表查找2.9 在pos位置之前插入2.10 删除pos位置数据2.11 在pos位置的后面插入2.12 删除pos位置后面的数据 …
阅读更多...
数据结构之单链表的插入

数据结构之单链表的插入

单链表的完整的代码在这篇文章下面&#xff0c;链接&#xff1a; https://blog.csdn.net/six_teen/article/details/113253545 什么是链表&#xff1f; 如上图&#xff0c;链表和生活中的链条很相似&#xff0c;链表在逻辑结构上是以链条的形式连接而成的&#xff0c;但物理结构…
阅读更多...
单链表的定义，插入与删除，查找，建立。

单链表的定义，插入与删除，查找，建立。

链表分为&#xff1a;单链表&#xff0c;双链表&#xff0c;循环链表&#xff0c;静态链表 一&#xff0c;单链表的定义 在内存空间中&#xff0c;各个节点在逻辑上相邻&#xff0c;但在物理上不相邻。 在单个的结点内部需要存放 数据域 和 指针域&#xff08;存放指向下一个…
阅读更多...
单链表的定义

单链表的定义

前言 在前面的文章中&#xff0c;我们系统的介绍了线性表的顺序存储实现——顺序表。紧接着我们要介绍线性表的链式存储实现——链表。而链表中又有许多的链表&#xff1a; 单链表双链表循环链表静态链表 这一篇文章中&#xff0c;我们先来介绍单链表。 单链表的定义 什么…
阅读更多...
（c语言）详解单链表

（c语言）详解单链表

1&#xff1a;什么是单链表。 我们知道顺序表底层原理其实就是一块可以自由控制大小的数组&#xff0c;顺序表可以实现在任何地方进行插入一个数据&#xff0c;如果顺序表的缺点在于如果要在起始位置插入一个数据就要把后面的每一个数据都往后挪&#xff0c;这样会大量消耗我们…
阅读更多...
双向链表中插入元素的几种方式

双向链表中插入元素的几种方式

dnode的结构如下&#xff1a;由前驱prior指针、后继next指针以及数据data&#xff0c;现需要在A、B节点中间插入C节点&#xff0c;给出了A的地址&#xff0c;以及C的地址。 1、利用将链表拆分然后插入方式进行&#xff1a; 先将节点C完全插入到B的前面&#xff0c;再将A指向C&…
阅读更多...
单链表的使用方法.数据结构(三)[上]

单链表的使用方法.数据结构(三)[上]

前言 提示&#xff1a;文本为数据解构(三)单链表&#xff1a; 本文具体讲解单链表的具体使用方法 提示&#xff1a;以下是本篇文 系列文章目录 第一章 数据解构(一) 第二章 顺序表的具体使用方法.数据解构(二) 文章目录 前言 系列文章目录 文章目录 一、单链表视图 二、…
阅读更多...
Linux设置ssh免密登录

Linux设置ssh免密登录

目录 1.在/root目录下输入命令 2.进入.ssh目录 3.将公钥id_rsa.pub写入到一个认证文件夹中 4.开启远程免密登录配置 5.免密远程登录本机 1.在/root目录下输入命令 [rootlocalhost ~]# ssh-keygen -t rsa -P "" Generating public/private rsa key pair. Enter …
阅读更多...
Linux SSH 免密登录

Linux SSH 免密登录

Linux SSH 免密登录 本篇我们来 看看 Linux 的免密登录的原理 以及实际操作一番 概述 什么是 Linux SSH 免密登录&#xff0c;我觉得大家应该都 多少听过 或者操作过&#xff0c;那你真的理解整个免密登录的过程吗&#xff1f; Linux SSH 免密登录 就是 可以不输入密码 就可以…
阅读更多...
SSH登录和SSH免密登录

SSH登录和SSH免密登录

在了解ssh的时候产生了概念混淆&#xff0c;发现ssh登录和ssh免密登录是两码事。 可以从目的和过程对比这两个概念&#xff1a; 1.目的 1.1 SSH登录 简单来说就是&#xff1a;建立客户端和服务器之间安全的远程连接&#xff0c;登录远程服务器&#xff0c;以访问文件系统 。…
阅读更多...
VSCode——SSH免密登录

VSCode——SSH免密登录

文章目录 本地PC端&#xff08;一般为Windows&#xff09;1. 检查自己是否已经生成公钥2. 配置VScode的SSH config 远程服务器端1. 服务器新建授权文件2. 赋权限3. 重启远程服务器的ssh服务 最全步骤&#xff1a;【设置ssh免密不起作用&#xff1f;彻底搞懂密钥】vscode在remot…
阅读更多...
SSH免密登录功能配置

SSH免密登录功能配置

文章目录 一、SSH免密登录功能配置&#xff08;1&#xff09;master虚拟机免密登录master虚拟机&#xff08;2&#xff09;将公钥拷贝到所创建的虚拟机上 一、SSH免密登录功能配置 ssh密钥登录比密码登录安全&#xff0c;主要是因为他使用了非对称加密&#xff0c;登录过程中需…
阅读更多...
CentOS开启SSH免密登录

CentOS开启SSH免密登录

CentOS开启SSH免密登录 要实现SSH免密登录&#xff0c;首先需要准备一组公钥和私钥。将公钥放到服务器上&#xff0c;将私钥放到客户机上。当客户机连接服务器时&#xff0c;服务器会根据自身的公钥校验客户机的私钥&#xff0c;如果校验通过则允许连接。 一、创建密钥 在客…
阅读更多...
Ubuntu开启SSH免密登录

Ubuntu开启SSH免密登录

Ubuntu开启SSH免密登录 要实现SSH免密登录&#xff0c;首先需要准备一组公钥和私钥。将公钥放到服务器上&#xff0c;将私钥放到客户机上。当客户机连接服务器时&#xff0c;服务器会根据自身的公钥校验客户机的私钥&#xff0c;如果校验通过则允许连接。 一、创建密钥 在客…
阅读更多...
git SSH免密登录

git SSH免密登录

git系列文章目录 第八章 git SSH免密登录的使用 文章目录 git系列文章目录前言一、生成密钥二、使用步骤1.使用VSCODE打开.pub文件复制其中的内容2.打开github或者gitee进入设置选项设置密钥3.使用密钥 总结 前言 虽然Windows系统提供了凭据功能&#xff0c;但是介绍ssh提交&a…
阅读更多...
配置SSH免密登录

配置SSH免密登录

配置SSH免密登录 1. 在各个虚拟机&#xff08;master、s1、s2&#xff09;家目录执行ssh-keygen -b 1024 -t rsa&#xff0c;输入2次回车&#xff0c;输入y/yes再继续回车 ssh-keygen -b 1024 -t rsa 2. 进入到.ssh目录中 ls -all #查看所有文件和文件夹 cd .ssh 查看目录 ls…
阅读更多...
推荐文章

Copyright @ 2022~2023