当前位置: 首页 > news >正文

链表及其基本操作

1.单链表:

1.1定义/性质:

  • 链表是线性表的链式存储方式。

  • 单链表通过指针线性遍历,删除/增加节点时间复杂度为O(1),访问节点时间复杂度为O(n)。

  • 单链表分为带头结点和不带头结点两种,带头结点是为了方便统一操作(删除和插入操作都是通过指next指针来完成的,当只有一个节点的时候做删除操作/没有节点的时候做插入操作,这两种情况要特殊处理)。

对节点的描述如下:

typedef struct LNode{ElemType Data;//数据域struct Lnode next;//指针域
}Node;

1.2单链表的操作:

默认下列情况都有头结点。

1.2.1初始化(创建):

该操作初始化头指针和头结点:

Node* init(){Node* L=(Node*)malloc(sizeof(struct LNode));L->next=NULL;return L;
}

1.2.2插入操作:

有头插法和尾插法两种方法:

对于头插法,先插入的在后,后插入的在前:

Node* HeadInsert(){Node* tmp=(Node*)malloc(sizeof(struct LNode));//创建新节点tmp->next=L->next;//新节点指向头节点的指向L->next=tmp;//头结点指向新节点return L;
}

对于尾插法,要设置一个尾指针,通过尾指针完成插入

1.2.3删除操作:

删除操作要通过next指针完成,并且单链表是单向的,所以只能删除遍历到的节点的下一个节点(只能改变该节点的指向,也就是下一个节点)。

bool Delete(Node* L,int P){//删除值为p的节点for(Node* i=L,i;i=i->next){if(L->next->Data=P){//如果下一个节点的值为PL->next=L->next->next;return true;}}return false;
}

1.2.4反转操作:

法一:空间复杂度O(n)

遍历链表并使用头插法建立一个新链表即可。

法2:空间复杂度O(1)

借助两个辅助指针p,q;

初始p指向头结点(p=L),原指针L指向尾节点的指向(L=NULL);

具体步骤:p用于遍历链表,每次操作q取出p遍历到的节点并且连接到L的前面(包括头结点都逆转了),再让L指向q指向的(L=q)。

1.3其他单链表:

循环单链表:

尾节点指向头结点而不是NULL,判断链表是否为空的方法是尾节点的指针是否等于头结点的指针。

2双链表:

在单链表的基础上,每个节点增加了一个指向前驱的指针pre。

2.1双链表的操作:

在做双链表的操作时要注意每一步的先后顺序。

对于该双链表:

2.1.1插入操作:

在p指针指向的节点后插入一个节点a:

  1. 更新a的前后指针;

  1. 通过a来更新p,q的指针,由于我们的指针是p,所以先更新q再更新p(q要通过p得到)。

2.1.2删除操作

假设a节点已经插入了,删除节点a:

先更新q再更新p即可。

相关文章:

链表及其基本操作

1.单链表:1.1定义/性质:链表是线性表的链式存储方式。单链表通过指针线性遍历,删除/增加节点时间复杂度为O(1),访问节点时间复杂度为O(n)。单链表分为带头结点和不带头结点两种,带头结点是为了方便统一操作&#xff08…...

【Java基础 下】 031 -- 反射 动态代理

一、什么是反射? 换句话说就是(从类里拿出来) 可以获取到:(利用反射,我们可以获取到类中所有的东西) 获取是先从class字节码文件中获取的 二、获取class对象的三种方式 三种方式也对应了三种阶段…...

springcloud3 GateWay

一 GateWay 1.1 GateWay的作用 gateway相当于所有服务的门户,将客户端请求与服务端应用相分离,客户端请求通过gateway后由定义的路由和断言进行转发,路由代表需要转发请求的地址,断言相当于请求这些地址时所满足的条件&#xff…...

万字长文:Stable Diffusion 保姆级教程

万字长文:Stable Diffusion 保姆级教程 2022年绝对是人工智能爆发的元年,前有 stability.ai 开源 Stable Diffusion 模型,后有 Open AI 发布 ChatGPT,二者都是里程碑式的节点事件,其重要性不亚于当年苹果发布iPhone&a…...

WAMP搭建靶场

WAMP W:windows A:apache M:mysql,mariadb P:php 1. 下载phpstudy Windows版phpstudy下载 - 小皮面板(phpstudy) 2. 安装phpstudy 默认安装即可 3. 下载DVWA靶场 https://github.com/digininja/DVWA/archive/…...

Uipath Excel 自动化系列13-ForEachExcelSheet(遍历Sheet)

活动描述 ForEachExcelSheet(遍历Sheet):遍历Excel中的工作表,可以对 Excel 工作簿中的每个工作表重复一个或多个活动,该活动需与Use Excel File 活动选择的 Excel 文件一起使用。 使用场景:当处理包含多张工作表的 Excel 文件,…...

JDBC快速入门

🍎道阻且长,行则将至。🍓 目录 一、JDBC入门 1.概述 (1)JDBC本质 (2)JDBC好处 2.快速入门 (1)步骤 (2)实践 (3)两个小问题 一、JDBC入门 1.概述 JDBC就是使用Java语言操作关系型数据库的一套API,全称:( Java…...

蓝桥杯三月刷题 第六天

文章目录💥前言😉解题报告💥星期计算🤔一、思路:😎二、代码:💥考勤刷卡🤔一、思路:😎二、代码:💥卡片🤔一、思路:😎二、代…...

分享几个常用的运维 shell 脚本

今天咸鱼给大家分享几个不错的 Linux 运维脚本,这些脚本中大量使用了 Linux 的文本三剑客: awkgrepsed 建议大家这三个工具都要了解并最好能够较为熟练的使用 根据 PID 显示进程所有信息 根据用户输入的PID,过滤出该PID所有的信息 #! /b…...

分隔链表(精美图示详解哦)

全文目录引言分隔链表题目描述与思路实现总结引言 前面,我们熟悉了管理链表中的数据的方法,也了解了几道与链表相关的题目: 戳我看单链表详解哦 在本篇文章中,我们将再了解一道题目:分隔链表: 分隔链表OJ…...

腾讯乐固加固+app签名+多渠道打包

一、腾讯乐固-基础版免费加固-上传未加固的app-下载加固包(加固成功会清除原apk的签名信息和多渠道信息)https://console.cloud.tencent.com/ms/reinforce/list/basic二、使用AndroidStudio自带工具apksigner对apk重新签名找到apksigner.bat文件 路径D:\…...

Spring Boot整合Redis缓存(Lettuce)

spring-boot-demo-cache-redis 此 demo 主要演示了 Spring Boot 如何整合 redis&#xff0c;操作redis中的数据&#xff0c;并使用redis缓存数据。连接池使用 Lettuce。 Lettuce官网 pom.xml <!-- data-redis --> <dependency><groupId>org.springframework…...

Feign

而Feign则会完全代理HTTP请求&#xff0c;我们只需要像调用方法一样调用它就可以完成服务请求及相关处理。Feign整合了Ribbon和Hystrix&#xff0c;可以让我们不再需要显式地使用这两个组件。 Feign具有如下特性&#xff1a; 支持可插拔的HTTP编码器和解码器; 支持Hystrix和…...

【代码训练营】day54 | 392.判断子序列 115.不同的子序列

所用代码 java 判断子序列 LeetCode 392 题目链接&#xff1a;判断子序列 LeetCode 392 - 简单 思路 这题和之前求最长公共子序列一样。 dp[i] [j]&#xff1a;以i-1为结尾的字符串s 和 以j-1为结尾的字符串t 组成的相同子序列的长度 递推公式&#xff1a; 相等dp[i][j] d…...

【unity3D】创建TextMeshPro(TMP)中文字体(解决输入中文乱码问题)

&#x1f497; 未来的游戏开发程序媛&#xff0c;现在的努力学习菜鸡 &#x1f4a6;本专栏是我关于游戏开发的学习笔记 &#x1f236;本篇是unity的TMP中文输入显示乱码的解决方式 创建 TextMeshPro 中文字体遇到的问题描述解决方式Font Asset Creator 面板扩展中文字体文本遇到…...

JAVA开发(JAVA中的异常)

在java开发与代码运行过程中&#xff0c;我们经常会遇到需要处理异常的时候。有时候是在用编辑器写代码&#xff0c;点击保存的时候&#xff0c;编辑器就提示我们某块代码有异常&#xff0c;强制需要处理。有时候是我们启动&#xff0c;运行JAVA代码的时候的&#xff0c;日志里…...

lesson8-Linux多线程

Linux线程概念 线程在进程内部执行,是OS调度的基本单位OS是可以做到让进程进行资源的细粒度划分的物理内存是以4kb为单位的我们的.exe可执行程序本来就是按照地址空间的方式进行编译的页表映射 - 详细图 理解线程 线程在进程的地址空间内运行, 进程内部具有多个执行流的,而线程…...

python的django框架从入门到熟练【保姆式教学】第四篇

在前三篇博客中&#xff0c;我们介绍了Django的模型层、数据库迁移、视图层和URL路由。本篇博客将介绍Django的模板层&#xff0c;讲解如何使用模板来创建美观的Web页面。 模板层&#xff08;Template&#xff09; Django的模板层是Django应用程序的另一个核心组件。模板是一…...

Codeforces Round 852 (Div. 2)

A Yet Another Promotion 题意&#xff1a;要买n千克物品&#xff0c;第一天的价格为a&#xff0c;第二天的价格为b。第一天有促销活动&#xff0c;每买m千克物品&#xff0c;可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。 思路&#xff1a;分类讨论&…...

【PTA Data Structures and Algorithms (English)】7-2 Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K3, then you must output 3→2→1→6→5→4; if K4, you must output 4→3→2→1→5→6. Input Specif…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...