专栏首页hui单链表的头尾插法详解

单链表的头尾插法详解

单链表头尾插法详解
  • 头插法构造单链表
    • 代码实现
    • 头插法过程
  • 尾插法构造单链表
    • 代码实现
    • 尾插法过程
  • 单链表头尾插法对比

#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;		// 单链表存储元素的数据类型

// 定义单链表结构体
typedef struct Node(){
	ElemType data;			// 单链表结点数据域
	struct Node *next;		// 单链表结点地址域(指向下一个结点)
}*LinkList, Node;

头插法构造单链表

代码实现

/*
 *	头插法创建单链表(带头结点)
 *	datas 接收数组,用于赋值链表的结点数据
 *	len datas数组的长度,便于遍历
*/
LinkList CreateHeadListH(ElemType *datas, int len){
	// 创建头结点
	LinkList head, new_node;
	head = (LinkList)malloc(sizeof(Node));
	// head -> data = len;	// 可以把链表长度存在头结点的数据域中
	head -> next = NULL;

	// 分配新节点并用头插法链接起来
	for(int i=0;i<len;i++){
		new_node = (LinkList)malloc(sizeof(Node));
		new_node -> data = datas[i];
		new_node -> next = head -> next;
		head -> next = new_node;
	}
	return head;
}

头插法过程

头插法往单链表头部插入,假设

datas[] = {2, 4, 6};

首先创建头结点

分配第一个新节点时

head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = NULL;

new_code -> data = datas[0]; 		-->		new_code -> data = 2;
new_code -> next = head -> next;	-->		new_code -> next = NULL;

然后让 head 结点的地址域指向新结点(这里指第一个结点)

head -> next = new_code1;

最终形成

分配第二个新结点时

head 结点的数据域为空 head -> data = NULL, ,地址域也为第一个结点的地址 head -> next = new_node1;

new_code -> data = datas[1];		-->		new_code -> data = 4;

让第二结点的地址域指向第一个结点(此时第一个结点位置存在 head 结点的地址域)

new_code -> next = head -> next;	-->		new_code -> next = new_code1;

然后让 head 头结点的地址域指向第二个结点的位置

head -> next = new_code2;

最终形成

分配第三个新结点后

关键代码

头插法每次插入新结点时都是往头结点处插入。

new_node -> next = head -> next;	// 先让新结点地址域指向头结点地址域的结点位置
head -> next = new_node;			// 然后让头结点的地址域指向新结点位置

如此循环就形成了头插法构造单链表。

尾插法构造单链表

代码实现

/*
 *	尾插法创建单链表(带头结点)
 *	datas 接收数组,用于赋值链表的结点数据
 *	len datas数组的长度,便于遍历
*/
LinkList CreateHeadListT(ElemType *datas, int len){
	// 创建头结点
	LinkList head, p, new_node;
	head = (LinkList)malloc(sizeof(Node));
	head -> next = NULL;
	p = head;

	// 分配新节点并用尾插法链接起来
	for(int i=0;i<len;i++){
		new_node = (LinkList)malloc(sizeof(Node));
		new_node -> data = datas[i];
		new_node -> next = NULL;
		p -> next = new_node;
		p = new_node;
	}
	return head;
}

尾插法过程

尾插法往单链表尾部插入,还是假设单链表的结点数据分别为。

datas[] = {2, 4, 6};

创建头结点跟头插法是一样的我就不重复叙述了。

分配第一个新结点时

head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = NULL; 变量p等于头结点 p = head;

先让新结点赋值

new_code -> data = datas[0];		-->		new_code -> data = 2;
new_code -> next = NULL;			--> 	new_code -> next = NULL

后让链表链接起来

p -> next = new_code;
p = new_code;

一开始 p = head 所以让头结点的地址域指向新结点,,后让 p 等于新结点(此时新结点代表第一个结点)。

分配第二个新结点时

head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = new_node1;

此时变量 p 就等于第一个结点,不再等于头结点。

继续让新结点与单链表链接起来

p -> next = new_code;
p = new_code;	

让第一个结点的地址域指向新结点(此时新结点代表第二个结点),让p等于第二个结点。

分配第三个新结点后

关键代码

p -> next = new_code;	// 让p的地址域指向新结点
p = new_code;			// 然后让p等于新插入进来的结点(一直等于最后一个结点)

尾插法每次插入新结点时都是往尾结点处插入。

如此循环就形成了尾插法构造单链表。

单链表头尾插法对比

同样是数据 datas[] = {2, 4, 6, 8}; 但链接的效果是不一致的,思想也不同。

头插法: head --> 8 --> 6 --> 4 --> 2

结点一直往 单链表头部插入,先进入的数据结点链接在末尾端(刚好逆序),有点像栈的特性,先进后出

尾插法: head --> 2 --> 4 --> 6 --> 8

结点一直往 单链表尾部插入,先进入的数据结点还是在前驱。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树和二叉树

    ​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(Sub...

    忆想不到的晖
  • 顺序表与链表的比较

    结点的数据域a1占8个字节,地址域占4个字节,所以存储密度 = 8 / 12 = 67%

    忆想不到的晖
  • C语言实现单链表

    单链表是由多个结点链接组成,它的每个结点包含两个域,一个数据域和一个链接域(地址域)。

    忆想不到的晖
  • webpack打包原理入门探究(五)loader初探(一)

    添加 webpack.app.config.js 文件, 配置 module, 用于加载 loader

    公众号---志学Python
  • 代码分享:用java备份MySQL数据库

    t-io官网的数据库都会定时备份,并且可以通过http直接下载到本地(这个当然需要特权,不是人人有这个操作权限),为了操作的灵活性,采用java来实现MySql...

    talent-tan
  • 优化生产环境中的 Kubernetes 资源分配

    我和 Kubernetes 的初次接触就涉及到将应用容器化并部署到生产环境集群中,当时我的工作重点是把 buffer 吞吐量最高(低风险)的某个端点从单个应用程...

    米开朗基杨
  • 锋利的jQuery第二期

    时隔几天,小朱又和大家见面了,带领大家继续我们的jQuery之旅,上次说到如果jQuery框架与prototype框架同时引用需要处理好控制权的问题,对...

    聚沙成塔
  • Java网络编程--Netty中的ByteBuf

    由于JDK中提供的ByteBuffer无法动态扩容,并且API使用复杂等原因,Netty中提供了ByteBuf。

    CodingDiray
  • [知乎作答]·关于在Keras中多标签分类器训练准确率问题

    本文来自知乎问题 关于在CNN中文本预测sigmoid分类器训练准确率的问题?中笔者的作答,来作为Keras中多标签分类器的使用解析教程。

    小宋是呢
  • TensorFlow核心使用要点

    正文之前,小梦先来说说什么是TensorFlow。TensorFlow是谷歌研发的第二代人工智能学习系统,可被用于语音识别或图像识别等多项机器深度学 习领域。T...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券