探秘Python中的链表:从零开始的奇妙之旅

引言

链表之所以重要,是因为它提供了一种灵活的方式来存储和操作数据集合。不同于数组,链表允许我们在无需重新分配内存的情况下动态地添加或删除元素。这使得它成为处理不确定大小数据集的理想选择。此外,在某些特定场景下(如实现缓存机制),链表可以比其他数据结构表现得更加出色。

基础语法介绍:链表的核心概念

在深入探讨之前,我们先来了解一下链表的基本构成。链表是由一系列节点组成的数据结构,每个节点包含两部分:存储数据的数据域和指向下一个节点的引用(指针)。最后一个节点的指针通常设置为None,表示链表的结束。

创建一个简单的链表节点类

class ListNode:def __init__(self, value=0, next=None):self.value = value  # 节点值self.next = next    # 指向下一个节点的链接

通过这个简单的定义,我们就创建了一个能够用于构建链表的基本单元——节点。

基础实例:动手创建链表

让我们通过一个例子来看看如何使用上述定义来创建一个链表。

假设我们需要创建一个链表来存储一组数字:1 -> 2 -> 3

# 创建节点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)# 链接节点
node1.next = node2
node2.next = node3

这段代码展示了如何实例化多个节点对象,并将它们链接起来形成一个链表。

进阶实例:链表操作实战

当涉及到更复杂的操作,比如查找、插入或删除节点时,链表的优势便体现出来了。接下来,我们将实现这些功能。

查找节点

def find_node(head, target):current = headwhile current is not None:if current.value == target:return currentcurrent = current.nextreturn None

插入新节点

def insert_after(node, new_value):new_node = ListNode(new_value)new_node.next = node.nextnode.next = new_node

删除节点

def delete_node(node):if node.next is not None:node.value = node.next.valuenode.next = node.next.next

这些函数分别实现了在链表中查找指定值的节点、在某个节点之后插入新节点以及删除一个已知节点的功能。

实战案例:链表在真实项目中的应用

在现实世界的软件开发中,链表经常被用来解决各种问题。例如,在设计浏览器的历史记录系统时,我们可以利用双端链表来快速实现前进和后退功能;又或者在构建LRU(最近最少使用)缓存时,链表同样是一个很好的选择。

示例:实现LRU缓存

from collections import OrderedDictclass LRUCache:def __init__(self, capacity: int):self.cache = OrderedDict()self.capacity = capacitydef get(self, key: int) -> int:if key not in self.cache:return -1self.cache.move_to_end(key)  # 将访问过的项移到末尾return self.cache[key]def put(self, key: int, value: int) -> None:if key in self.cache:self.cache.move_to_end(key)self.cache[key] = valueif len(self.cache) > self.capacity:self.cache.popitem(last=False)  # 移除最久未使用的项

这里使用了Python内置的OrderedDict来模拟链表的行为,实现了一个简易版的LRU缓存。

扩展讨论:链表的变体与挑战

虽然本文主要介绍了单向链表,但实际应用中还有双向链表、循环链表等多种形式。每种类型都有其独特的应用场景和优缺点。随着数据量的增长和技术的发展,如何高效地管理和操作链表也成为了不断研究的话题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/427763.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

什么是CSRF攻击,该如何防护CSRF攻击

CSRF攻击(跨站请求伪造,Cross-Site Request Forgery)是一种网络攻击手段,攻击者利用已通过身份验证的用户,诱导他们在不知情的情况下执行未授权操作。这种攻击通常发生在用户登录到可信网站并且有活动的会话时&#xf…

Python编码系列—Python组合模式:构建灵活的对象组合

🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中…

cv2.bitwise_or 提取ROI区域

原图如下所示,想提取圆形ROI区域,红色框 img np.ones(ori_img.shape, dtype"uint8") img img * 255 cv2.circle(img, (50,50), 50, 0, -1) self.bitwiseOr cv2.bitwise_or(ori_img, circle)使用一个和原图尺寸一致的图像做mask,图白圆黑 以…

MySQL:索引02——使用索引

目录 引言 1、自动创建索引 2、手动创建索引 2.1 主键索引 2.2 查看索引信息 2.3 唯一索引 2.4 普通索引 2.5 复合索引 3、删除索引 3.1 主键索引 3.2 其他索引 4、查看执行计划 4.1 不加条件,查询所有 4.2 使用主键查询 4.3 子查询使用索引 4.4 普通索…

【架构设计】多级缓存:应用案例与问题解决策略

【架构设计】多级缓存:应用案例与问题解决策略 多级缓存系统的工作原理及其在提升应用性能方面的关键作用。通过对比本地缓存与分布式缓存的特点 | 原创作者/编辑:凯哥Java | 分类:架构设计系列教程 多级缓存…

在基准测试和规划测试中选Flat还是Ramp-up?

Flat测试和Ramp-up测试是各有优势的,下面我们就通过介绍几种实用的性能测试策略来分析这两种加压策略的着重方向。 基准测试 基准测试是一种测量和评估软件性能指标的活动,通过基准测试建立一个已知的性能水平(称为基准线)&…

WPS生成目录

导航窗格:视图->导航窗格 可修改标题的样式,之后的标题直接套用即可 修改其他标题样式也是这样 添加编号:可以选上面的模版 也可自定义编号 生成目录:引用->目录->选用一个 但是我想把目录插到另一页 当我添加几个标题…

Spark-RDD持久化

一、Spark的三种持久化机制 1、cache 它是persist的一种简化方式,作用是将RDD缓存到内存中,以便后续快速访问,提高计算效率。cache操作是懒执行的,即执行action算子时才会触发。 2、persist 它提供了不同的存储级别&#xff0…

无人机黑飞打击技术详解

随着无人机技术的普及,无人机“黑飞”(未经授权或违反规定的飞行)现象日益严重,对公共安全、隐私保护及重要设施安全构成了严重威胁。为有效应对这一挑战,各国政府和安全机构纷纷研发并部署了一系列无人机黑飞打击技术…

HTML简介

HTML简介 1.HTML概述2.HTML元素3.HTML属性4.HTML 注释5.HTML颜色 1.HTML概述 HTML 是用来描述网页的一种语言。 HTML 指的是超文本标记语言HTML 不是一种编程语言&#xff0c;而是一种标记语言标记语言是一套标记标签HTML 使用标记标签来描述网页 例子&#xff1a; <htm…

Kotlin cancel CoroutineScope.launch的任务后仍运行

Kotlin cancel CoroutineScope.launch的任务后仍运行 import kotlinx.coroutines.*fun main() {runBlocking {val coroutineScope CoroutineScope(Dispatchers.IO)val job coroutineScope.launch {var i 0while (i < Int.MAX_VALUE) {iprintln(i)}}// 2ms 取消协程delay(…

2.计算机网络基础

2. 计算机网络基础 (1) 计算机网络的定义 计算机网络是指将地理位置不同、具有独立功能的多个计算机系统通过通信线路和设备连接起来,以功能完善的网络软件实现网络中资源共享的系统。最简单的定义是:计算机网络是一些互相连接的、自治的计算机系统的集合。最庞大的计算机网…

在 PostGIS 中进行千万级空间数据的空间查询和关键字查询

一、目的 本测试在探究在有限的计算机配置下&#xff0c;如何高效地对千万级的空间数据进行空间查询和关键字查询。通过实际操作和测试&#xff0c;评估不同查询策略的性能&#xff0c;为处理大规模空间数据提供可行的解决方案。 计算机配置如下&#xff1a; 内存&#xff0…

声网SDK脚本运行错误

文章目录 运行步骤无法运行.bat电脑出现警告--更改执行策略若无出现-更新power shell搜索最新版本的 PowerShell安装新版本 仍无法解决-手动下载第三方库 2024-9-9运行步骤 无法运行.bat 电脑出现警告–更改执行策略 若无出现-更新power shell 搜索最新版本的 PowerShell 在…

记录|如何对批量型的pictureBox组件进行批量Image设置

目录 前言一、问题表述二、批量化处理更新时间 前言 参考文章&#xff1a; 一、问题表述 问题就是上图所示&#xff0c;这些的命名风格统一&#xff0c;只是最后的数字是不同的。所以存在可以批量化进行处理的可能性。 二、批量化处理 private void SetPictureBoxImages(){for…

ElementPlus表单验证报错 formEl.validate is not a function

出现问题的代码 <!-- 密码重置弹框 --><el-dialog v-model"innerVisible" width"500" title"密码重置" append-to-body><el-form ref"ruleFormRef" style"max-width: 600px" :model"passForm" sta…

HarmonyOS元服务与卡片

元服务与卡片 文章目录 一、元服务1.介绍2.常见元服务项目步骤 二、卡片1.介绍2.卡片的创建3.卡片的数据的变更4.卡片的进程间通讯4.1使用工具包4.2使用步骤 5.卡片路由postCardAction&#xff1a;快速拉起后台5.1格式5.2快速拉起指定页面--router5.3调用后台功能--call5.3卡片…

委托的注册和注销

让我们来回顾一下委托的内容。 委托 是一种复杂的数据类型&#xff0c;需要我们先定义出来。当定义好类型后&#xff0c;声明委托变量来使用。 可以装载方法&#xff0c;只可以装载具有相同返回类型和参数列表的方法。 委托变量名&#xff08;参数列表&#xff09;&#xf…

使用Webpack创建vue脚手架并搭建路由---详解

1.使用 vue 库 vue 是一个非常好用的 javascript 库&#xff0c;现在已经发行了 vue 3&#xff0c;我们可以直接导入使用库文件&#xff0c;也可以使用单文件&#xff08;SFC&#xff09;的形式&#xff0c;直接使用库文件会简单一点&#xff0c;我们先来试一下吧。 1.1安装 v…

Qt 模型视图(二):模型类QAbstractItemModel

文章目录 Qt 模型视图(二)&#xff1a;模型类QAbstractItemModel1.基本概念1.1.模型的基本结构1.2.模型索引1.3.行号和列号1.4.父项1.5.项的角色1.6.总结 Qt 模型视图(二)&#xff1a;模型类QAbstractItemModel ​ 模型/视图结构是一种将数据存储和界面展示分离的编程方法。模…