首页 > 编程语言 >探秘Python中的链表:从零开始的奇妙之旅

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

时间:2024-09-19 12:51:17浏览次数:10  
标签:node Python self value next 链表 探秘 节点

引言

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

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

在深入探讨之前,我们先来了解一下链表的基本构成。链表是由一系列节点组成的数据结构,每个节点包含两部分:存储数据的数据域和指向下一个节点的引用(指针)。最后一个节点的指针通常设置为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 = head
    while current is not None:
        if current.value == target:
            return current
        current = current.next
    return None

插入新节点

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

删除节点

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

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

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

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

示例:实现LRU缓存

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
        
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.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] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 移除最久未使用的项

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

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

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

标签:node,Python,self,value,next,链表,探秘,节点
From: https://blog.51cto.com/u_16918694/12056068

相关文章

  • Python中 递归(Recursion)的使用浅析
    递归的定义递归是一种在函数定义中调用函数自身的编程技巧和算法设计方法。递归中有两个关键要素1. 递归的终止条件。当满足这个条件时,递归不再继续调用自身,而是开始返回结果。这也叫 递归基例(BaseCase)。 如果没有正确设置递归基例,递归函数将无限地调用自身,直到耗尽系......
  • Python实现GUI小工具CSV文件转Excel
    目录专栏导读库的安装代码总结专栏导读......
  • 如何用Python爬取全部ETF基金实时数据!
    一般来说,我们都是交易ETF基金,就是可以在股票交易所买卖的那种基金,而不是基金公司或者天天基金网提供的基金。因为ETF基金的交易方式类似股票,当时会比股票更有优势,这个具体我们就不展开讲,不然跑题了。言归正传,我们来爬取全部800多只ETF基金的数据。1).打开东财的网站,点击基金,......
  • Python单体类编写技巧与类装饰器应用
    在软件开发中,有时希望某个类只能生成一个实例,这种模式被称为单体模式(SingletonPattern)。单体类确保整个程序中只有一个类实例,从而在多线程环境或全局配置中保持状态一致。Python作为一门灵活的编程语言,提供了多种实现单体类的方法,包括使用类装饰器来简化单体类的实现。本文将......
  • 离线安装Python Library教程
    当你的设备不能联网,你该如何下载原来一行pip命令就能下载的Python库?别慌,没有你想象的那么麻烦。下面我将介绍常用的两种方法:通过源代码和通过wheel文件。一.通过wheel文件(.whl)首先搜索你想要下载的python库的pypi页面这里以numpy为例:进入页面后,点击Downloadfiles,进入......
  • Python 单元测试详解:Unittest 框架的应用与最佳实践
    Python单元测试详解:Unittest框架的应用与最佳实践文章目录Python单元测试详解:Unittest框架的应用与最佳实践一什么是Unittest1不使用Unittest测试框架2使用Unittest测试框架二unittest使用建议1先写测试case后写测试逻辑2测试文件以_test.py结尾......
  • Python 异常控制详解:try-except 的应用与多种异常处理策略
    Python异常控制详解:try-except的应用与多种异常处理策略文章目录Python异常控制详解:try-except的应用与多种异常处理策略一可遇见的异常二处理多个异常1多个异常一起处理2多个异常分开处理三try-except-else四try-except-finally五raise手动抛出异常六Pyt......
  • [Python数据可视化] Plotly:交互式数据可视化的强大工具
    引言:在数据分析和可视化的世界中,Plotly是一颗耀眼的明星。它是一个开源的交互式图表库,支持多种编程语言,包括Python、R和JavaScript。Plotly的强大之处在于它能够创建出既美观又具有高度交互性的图表,使得数据探索和分析变得更加直观和有趣。本文将详细介绍Plotly的功能,......
  • python 深度神经网络训练,pytorch ,tensorflow paddle大模型训练中损失突然增大的原因
    在机器学习和深度学习的训练过程中,损失函数的数值突然变高可能是由多种因素引起的。以下是一些可能的原因和相应的解决方案:1.**学习率设置不当**:如果学习率过高,可能会导致模型在优化过程中跳过最小值,甚至导致模型发散。相反,如果学习率过低,则可能导致模型训练速度过慢,甚至停滞......
  • Python用TOPSIS熵权法重构粮食系统及期刊指标权重多属性决策MCDM研究|附数据代码
    原文链接:https://tecdat.cn/?p=37724原文出处:拓端数据部落公众号 分析师:SikunChen在当今世界,粮食系统的稳定性至关重要。尽管现有的全球粮食系统在生产和分配方面表现出较高的效率,但仍存在大量人口遭受饥饿以及诸多粮食安全隐患。与此同时,在学术领域,准确评估情报学期刊的质......