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

数据结构---链表

news 来源：原创 2025/6/26 3:40:34

1. 简介

链表（Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表的一个主要优点是能够高效地插入和删除元素，尤其是在数组中需要移动大量元素的情况下。

1.1 链表的基本操作

插入：可以在链表的任意位置插入新节点。
删除：可以从链表的任意位置删除节点。
查找：遍历链表查找特定的节点。
更新：修改链表中某个节点的值。

1.2 链表类型

链表有多种变体，每种类型在特定场景下有不同的应用。

单链表适用于简单的数据结构，头部插入和删除高效，适合实现栈、队列等数据结构。
双链表适用于需要频繁从两端或中间插入、删除节点的场景，适合实现双向队列、LRU缓存等。
循环链表适用于需要循环访问或周期性任务调度的场景，适合实现循环队列、约瑟夫问题等。

1.3 比较

特性	单链表 (Singly Linked List)	双链表 (Doubly Linked List)	循环链表 (Circular Linked List)
节点结构	每个节点有一个指针指向下一个节点	每个节点有两个指针，分别指向前一个和下一个节点	最后一个节点的指针指向头节点，形成环
遍历方向	只能从头到尾遍历	可以从头到尾、从尾到头遍历	循环访问，遍历方向根据链表类型
空间复杂度	O(n)	O(n)	O(n)
插入和删除效率	在头部插入删除高效，其他位置较慢	在任意位置插入删除高效	插入删除效率与单链表或双链表类似，循环性优势
适用场景	适用于简单的线性访问	适用于需要从两端访问节点的场景	适用于需要循环遍历的场景

2. 单链表

单链表是最基本的链表类型，它的每个节点只包含一个指向下一个节点的指针。每个节点包含两个部分：数据域和指针域（指向下一个节点的指针）。

特点：

只能从头到尾进行单向遍历。
插入和删除操作通常比较高效，尤其在头部插入删除时。

class SinglyLinkedList {static class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}}private Node head;// 插入元素public void insert(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = newNode;}}// 打印链表public void printList() {Node temp = head;while (temp != null) {System.out.print(temp.data + " -> ");temp = temp.next;}System.out.println("null");}
}

3. 双链表

双链表是每个节点都有两个指针，一个指向下一个节点，另一个指向前一个节点。相比于单链表，双链表允许在两端（头尾）插入或删除节点，操作更灵活。

特点：

可以在两个方向（前后）进行遍历。
删除节点时更加灵活，可以直接访问前驱节点。
每个节点需要更多的内存来存储两个指针。

class DoublyLinkedList {static class Node {int data;Node next;Node prev;Node(int data) {this.data = data;this.next = null;this.prev = null;}}private Node head;// 插入元素public void insert(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = newNode;newNode.prev = temp;}}// 打印链表public void printList() {Node temp = head;while (temp != null) {System.out.print(temp.data + " <-> ");temp = temp.next;}System.out.println("null");}
}

4. 循环链表

循环链表是链表的变体，其中最后一个节点的指针指向头节点，形成一个环。循环链表可以是单向的（单循环链表）或双向的（双循环链表）。

特点：

可以从任意节点开始遍历，遍历过程中可以循环回到起点。
适合需要循环访问的场景，如实现循环队列、约瑟夫问题等。

4.1 单向循环链表

class CircularLinkedList {static class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}}private Node head;// 插入元素public void insert(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;newNode.next = head; // 成环} else {Node temp = head;while (temp.next != head) {temp = temp.next;}temp.next = newNode;newNode.next = head; // 成环}}// 打印链表public void printList() {if (head == null) return;Node temp = head;do {System.out.print(temp.data + " -> ");temp = temp.next;} while (temp != head);System.out.println("(back to head)");}
}

4.2 双向循环链表

class CircularDoublyLinkedList {static class Node {int data;Node next;Node prev;Node(int data) {this.data = data;this.next = null;this.prev = null;}}private Node head;// 插入元素public void insert(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;newNode.next = head;newNode.prev = head;} else {Node temp = head;while (temp.next != head) {temp = temp.next;}temp.next = newNode;newNode.prev = temp;newNode.next = head;head.prev = newNode; // 将头节点的prev指针指向新节点}}// 打印链表public void printList() {if (head == null) return;Node temp = head;do {System.out.print(temp.data + " <-> ");temp = temp.next;} while (temp != head);System.out.println("(back to head)");}
}

不积跬步，无以至千里 --- xiaokai

数据结构---链表

1. 简介链表（Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表的一个主要优点是能够高效地插入和删除元素，尤其是在数组…...

编程日记 2025/6/26 3:40:34

【系统架构设计师】真题论文: 论无服务器架构及其应用（包括解题思路和素材）

更多内容请见：备考系统架构设计师-专栏介绍和目录文章目录真题题目（2017年试题3）解题思路论文素材参考无服务器架构概念和特点无服务器架构的核心技术组件无服务器架构在不同领域的应用真题题目（2017年试题3）近年来，随着信息技术的迅猛发展和应用需求的快速更迭，…...

编程日记 2025/6/24 12:29:07

深度学习模型：BiLSTM (Bidirectional LSTM) - 双向长短时记忆网络详解

一、引言在深度学习领域，序列数据的处理一直是一个关键任务。循环神经网络（RNN）及其变体在自然语言处理、语音识别、时间序列分析等诸多领域发挥着重要作用。然而，传统的 RNN 面临着梯度消失或梯度爆炸等问题，导致难…...

编程日记 2025/6/22 11:06:30

【计算机网络】实验3：集线器和交换器的区别及交换器的自学习算法

实验 3：集线器和交换器的区别及交换器的自学习算法一、实验目的加深对集线器和交换器的区别的理解。了解交换器的自学习算法。二、实验环境 • Cisco Packet Tracer 模拟器三、实验内容 1、熟悉集线器和交换器的区别 (1) 第一步：构建网络…...

编程日记 2025/6/25 20:12:21

playwright 学习复仇记-2 Selector选择器定位元素

前言 Selector 选择器，也就是通常说的元素定位了，页面上点点点的操作，都是基于元素定位，所以这块是重点需要学的核心内容。 Selector 选择器说到元素定位，大家肯定会首先想到 selenium 的八大元素定位，其…...

编程日记 2025/6/26 3:14:02

C语言——实现计算房屋总价

//功能：计算房屋总价 //房屋总价房屋面积 * 单价 //契税房屋总价 * 0.15% //印花税房屋总价 * 0.05% //功能：计算房屋总价 //房屋总价房屋面积 * 单价 //契税房屋总价 * 0.15% //印花税房屋总价 * 0.05%#include<stdio.h>void main()…...

编程日记 2025/6/25 18:08:30

Vue3 脚手架扩展

当 yarn dev 运行成功后，我们继续添加扩展首先我们要安装一些依赖其中的vue-router和vuex安装最新版的就行，因为项目是vue3 element-plus和less，less-loader最好按照我这个版本来下载 element-plus是一个vue常用的ui组件库 element-plus/…...

编程日记 2025/6/26 2:31:53

Ubuntu 20.04 程序运行导致“段错误 (核心已转储)”的原因分析及解决方案 ubuntu

Ubuntu 20.04 程序运行导致“段错误 (核心已转储)”的原因分析及解决方案在Ubuntu 20.04系统中，运行程序时出现“段错误 (核心已转储)”是一种常见的错误提示。本文将详细解析导致段错误的原因，并提供完整的解决方案，辅以示例说明&#xff…...

编程日记 2025/6/24 8:06:43

Mysql常用sql语句

数据库操作 # 创建数据库 create database 库名 charsetutf8; # 使用数据库 use 库名; # 退出数据库 quit # 查看所有数据库 show databases; # 查看当前使用的数据库 select database(); # 删除数据库 drop database 库名; 表操作 #查看当前数据库中所有表 show tables;#创…...

编程日记 2025/6/23 1:35:04

SpringBoot 架构下的在线家具商城：规划与实践之路

第1章绪论 1.1选题动因当前的网络技术，软件技术等都具备成熟的理论基础，市场上也出现各种技术开发的软件，这些软件都被用于各个领域，包括生活和工作的领域。随着电脑和笔记本的广泛运用，以及各种计算机硬件的完善和升…...

编程日记 2025/6/25 18:50:03

request和websocket

当然，可以为你详细介绍 FastAPI 中的 Request 对象。Request 对象在 FastAPI 中扮演着重要的角色，负责封装来自客户端的 HTTP 请求信息。了解 Request 对象的使用方法和属性，有助于你更高效地处理请求数据、访问请求上下文以及进行各种操作。…...

编程日记 2025/6/25 14:20:45

前端【9种前端常见的设计模式】

🌟9种前端常见的设计模式哈喽小伙伴们，这期给大家整理了一些有关9种前端常见的设计模式，覆盖多方面基础知识，建议大家收藏阅读。文章目录 🌟9种前端常见的设计模式🌟1. 外观模式🌟 2. 代理模…...

编程日记 2025/6/26 2:50:21

IDEA使用HotSwapHelper进行热部署

目录前言JDK1.8特殊准备DECVM安装插件安装与配置参考文档相关下载前言碰到了一个项目，用jrebel启动项目时一直报错，不用jrebel时又没问题，找不到原因，又不想放弃热部署功能因此思考能否通过其他方式进行热部署，找…...

编程日记 2025/6/26 2:54:06

【Django-xadmin】

时间长不用,会忘的系列 1、Django-xadmin后台字段显示处理主要是修改每个模块下adminx.py文件代码解释：第1行控制表单字段显示第2行控制列表字段显示第3行控制搜索条件第4行控制过滤条件第5行支持单个或多个字段信息修改第6行列表分页，每页显示多少行…...

编程日记 2025/6/24 21:26:55

AI 计算基础设施的战略转折点分析

核心技术范式转移我们正处于计算架构的重大转折点。第一个根本性转变是从传统的 CPU 编程范式，向以 GPU 为核心的神经网络运算模式转移。这不仅仅是硬件架构的改变，更代表了整个软件开发和应用部署方式的革新。第二个转变则是在这个新的基础设施之上&a…...

编程日记 2025/6/25 8:46:06

Java基于SpringBoot+Vue的IT技术交流和分享平台（附源码+lw+部署）

博主介绍：✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...

编程日记 2025/6/22 14:11:24

二：OpenStack环境准备-controller node

一：工具、环境准备-controller node 二：OpenStack环境准备-controller node 三：安装服务-controller node 四：工具、环境准备-compute node 五：OpenStack环境准备-compute node 六：安装服务-compute node 七…...

编程日记 2025/6/24 20:25:55

解决stable-diffusion-webui时的问题：No module ‘xformers‘. Proceeding without it

p.s 被另一篇文章坑了，装个xformers把我原先的pytorch降智了&%$^# 注意：！！！xformers非强制安装；可优化显存，提高性能和出图速率，对于GPU能力有限的用户很有用；安装过…...

编程日记 2025/6/23 11:14:46

清理Linux/CentOS7根目录的思路

在使用Linux服务器过程中，经常会遇到磁盘空间不足的问题，好多应用默认安装在根目录下，记录一下如何找到问题所在，清理根目录（/） 1. 检查空间使用情况 1.1 查看分区占用： df -h输出&#xff1…...

编程日记 2025/6/24 18:22:35

人工智能-深度学习-BP算法

BP算法的核心思想是通过计算损失函数对网络参数的梯度，然后使用梯度下降法来更新网络参数，从而最小化损失函数。误差反向传播算法(BP)的基本步骤: 前向传播：正向计算得到预测值。计算损失：通过损失函数计算预测值和真实值的差…...

编程日记 2025/6/24 23:12:12

C++小问题

怎么分辨const修饰的是谁是限定谁不能被改变的？ 在C中，const关键字的用途和位置非常关键，它决定了谁不能被修改。const可以修饰变量、指针、引用等不同的对象，并且具体的作用取决于const的修饰位置。理解const的规则能够帮助我们…...

编程日记 2025/6/22 22:13:44

如何让控件始终处于父容器的居中位置（父容器可任意改变大小）

前言： 大家好，我是上位机马工，硕士毕业4年年入40万，目前在一家自动化公司担任软件经理，从事C#上位机软件开发8年以上！我们在C#开发winform程序的时候，有时候需要将一个控件居中显示&#xff0c…...

编程日记 2025/6/25 10:42:56

Python 调用 Umi-OCR API 批量识别图片/PDF文档数据

目录一、需求分析二、方案设计（概要/详细） 三、技术选型四、OCR 测试 Demo 五、批量文件识别完整代码实现六、总结一、需求分析市场部同事进行采购或给客户报价时，往往基于过往采购合同数据，给出现在采购或报价的金额…...

编程日记 2025/6/21 22:42:04

Java基础访问修饰符全解析

一、Java 访问修饰符概述 Java 中的访问修饰符用于控制类、方法、变量和构造函数的可见性和访问权限，主要有四种：public、protected、default（无修饰符）和 private。 Java 的访问修饰符在编程中起着至关重要的作用，它…...

编程日记 2025/6/23 12:45:38

朗迪锋亮相2024人因工程与智能系统交互国际会议

2024年11月28日至30日，2024人因工程与智能系统交互国际会议在深圳隆重举办。此次大会以推动我国人因工程学科发展为目标，致力于加强国际学术交流，深入探讨人工智能时代的智能系统交互，旨在培育新质生产力，助力经济社会…...

编程日记 2025/5/31 7:52:48

OpenGL学习过程总结

1、矩阵参考链接第三课：矩阵变换...

编程日记 2025/5/21 7:47:18

webGL入门教程_06变换矩阵与绕轴旋转总结

变换矩阵与绕轴旋转总结目录 1. 变换矩阵简介2. 平移矩阵3. 缩放矩阵4. 旋转矩阵 4.1 绕 Z 轴旋转4.2 绕 X 轴旋转4.3 绕 Y 轴旋转 5. 组合变换矩阵6. 结论 1. 变换矩阵简介在计算机图形学中，变换矩阵用于在三维空间中对物体进行操作，包括&#xff…...

编程日记 2025/5/30 6:46:36

SELECTTRIGGER_SCHEMA AS Database,TRIGGER_NAME AS Trigger,EVENT_OBJECT_TABLE AS Table,EVENT_MANIPULATION AS Event,ACTION_STATEMENT AS Statement FROMinformation_schema.TRIGGERS;创建触发器遇到报错： You do not have the SUPER privilege and binary lo…...

编程日记 2025/6/24 8:50:36

基于Java Springboot个人财务APP且微信小程序

一、作品包含源码数据库设计文档万字PPT全套环境和工具资源部署教程二、项目技术前端技术：Html、Css、Js、Vue、Element-ui 数据库：MySQL 后端技术：Java、Spring Boot、MyBatis 三、运行环境开发工具：IDEA/eclipse 微信…...

编程日记 2025/6/25 23:27:26

GateWay使用手册

好的，下面是优化后的版本。为了提高可读性和规范性，我对内容进行了结构化、简化了部分代码，同时增加了注释说明，便于理解。 1. 引入依赖在 pom.xml 中添加以下依赖： <dependencies><!-- Spring Cloud Gate…...

编程日记 2025/6/23 7:05:43

go语言读取yaml配置文件内容

1、config.yaml配置文件内容假设如下 name: "example" version: 1.0 settings:timeout: 30debug: truefeatures:- feature1- feature22、定义结构体 go语言定义结构体匹配yaml内容 package mainimport ("fmt""log""os""gopkg.…...

编程日记 2025/6/21 5:09:20

Proteus8.17下载安装教程

Proteus是一款嵌入式系统仿真开发软件，实现了从原理图设计、单片机编程、系统仿真到PCB设计，真正实现了从概念到产品的完整设计，其处理器模型支持8051、HC11、PIC10/12/16/18/24/30/DsPIC33、AVR、ARM、8086和MSP430等，能够帮助用…...

编程日记 2025/6/21 17:43:15

【AI】Sklearn

长期更新，建议关注、收藏、点赞。友情链接： AI中的数学_线代微积分概率论最优化 Python numpy_pandas_matplotlib_spicy 建议路线：机器学习->深度学习->强化学习目录预处理模型选择分类实例： 二分类比赛网格搜索实例&…...

编程日记 2025/6/3 20:07:47

图数据库 | 10、图数据库架构设计——高性能图存储架构(上)

老夫在之前的三大篇内容中，介绍了图数据库的三大组件—图计算、图存储以及图查询语言。（都归拢在图数据库原理、架构与应用这个专栏中了，感兴趣的朋友可以在去找阅读。） 接下来，老夫还将继续深化这三大组件&#xff0…...

编程日记 2025/6/2 10:24:42

el-table 组件二次封装（vue2）

PublicTable.vue  <template><div class"table-common"><el-table v-loading"loading" :ref"tableid" border style"width: 100%" :data"tableDatas" :row-key"rowKey&quo…...

编程日记 2025/6/22 17:00:23

张量并行和流水线并行在Transformer中的具体部位

目录张量并行和流水线并行在Transformer中的具体部位一、张量并行二、流水线并行张量并行和流水线并行在Transformer中的具体部位张量并行和流水线并行是Transformer模型中用于提高训练效率的两种并行策略。它们分别作用于模型的不同部位，以下是对这两种并行的具体说…...

编程日记 2025/6/25 8:19:33

详解Qt pdf 之QPdfSelection 选择文本类

文章目录 QPdfSelection 类详解前言详细说明公共函数说明1. 构造函数2. text3. boundingRect4. isEmpty5. startPage6. endPage 使用场景示例代码代码说明总结 QPdfSelection 类详解前言 QPdfSelection 是 Qt PDF 模块中的一个类，用于表示在 PDF 文档中被选中的…...

编程日记 2025/6/23 22:10:17

一款支持80+语言，包括：拉丁文、中文、阿拉伯文、梵文等开源OCR库

大家好，今天给大家分享一个基于PyTorch的OCR库EasyOCR，它允许开发者通过简单的API调用来读取图片中的文本，无需复杂的模型训练过程。项目介绍 EasyOCR 是一个基于Python的开源项目，它提供了一个简单易用的光学字符识别&#xff…...

编程日记 2025/6/24 21:41:53

matlab 中的 bug

在matlab中绘图，设置 axe 的背景颜色 axes_in3.Color #00235B ;打印的时候 print(figure_handle1,-dpng,-r300,"merge_yt_ey") ;此时保存的图片无法识别背景颜色原因在于 matlab 中的 InverseHardcopy 将 InvertHardcopy 设置成 off 则可以解决这个问…...

编程日记 2025/5/29 9:17:14

【算法刷题指南】优先级队列

🌈个人主页： 南桥几晴秋 🌈C专栏： 南桥谈C 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据…...

编程日记 2025/6/25 7:59:55

android user版本默认usb模式为充电模式

android插入usb时会切换至默认设置的模式，debug版本为adb，user版本为mtp protected long getChargingFunctions() {// if ADB is enabled, reset functions to ADB// else enable MTP as usual.if (isAdbEnabled()) {return UsbManager.FUNCTION_ADB;} e…...

编程日记 2025/6/22 6:30:10

[极客大挑战 2019]HardSQL--详细解析

信息搜集登录系统，有两个可能的注入点： 随便输一下看看传参类型： 都是GET型。 SQL注入传参 usernameadmin’&password123 传参 usernameadmin&password123’ username和password传参，四种闭合方式只有单引号报错&a…...

编程日记 2025/6/22 11:53:32

java基础概念46-数据结构1

一、引入 List集合的三种实现类使用了不同的数据结构！ 二、数据结构的定义三、常见的数据结构 3-1、栈特点：先进后出，后进先出。 java内存容器： 3-2、队列特点：先进先出、后进后出。栈VS队列-小结 3-3、数组 3-…...

编程日记 2025/6/24 4:39:05

数学建模选MATLAB还是Python？

在进行数学建模时，选择合适的编程语言和工具对于建模的效率和效果至关重要。目前，MATLAB和Python是两个常用的数学建模工具，它们各自有优缺点，适用于不同的场景。本文将从多个维度对MATLAB和Python进行比较，帮助大家做…...

编程日记 2025/6/20 19:38:35

【C++】多线程

目录一概念 1 多线程 2 多进程与多线程 3 多线程理解二创建线程 1 thread 2 join() 和 detach() 3 this_thread 三 std::mutex 1 lock 和 unlock 2 lock_guard 3 unique_lock 四 condition_variable 五 std::atomic 一概念 1 多线程在C11之前&#xff0…...

编程日记 2025/6/23 7:05:52

【计算机网络】实验2：总线型以太网的特性

实验 2：总线型以太网的特性一、实验目的加深对MAC地址，IP地址，ARP协议的理解。了解总线型以太网的特性（广播，竞争总线，冲突）。二、实验环境 • Cisco Packet Tracer 模拟器三、实…...

编程日记 2025/6/23 19:20:34

基于Matlab合成孔径雷达(SAR)回波信号建模与多指标质量评估

本研究基于合成孔径雷达（SAR）技术，建立了一个雷达回波信号的模拟模型，并通过多项评价指标对信号质量进行深入评估。首先，研究定义了与SAR系统相关的关键物理参数，如工作频率、平台速度、脉冲宽度、采样率等…...

编程日记 2025/6/25 13:56:12

spring boot3.3.5 logback-spring.xml 配置

新建 resources/logback-spring.xml 控制台输出颜色有点花可以自己更改 <?xml version"1.0" encoding"UTF-8"?>  <configuration debug"false" scan"false"><springProperty …...

编程日记 2025/6/20 6:17:24