使用python实现链表操作
作者:黑加仑妞 发布时间:2021-07-29 23:30:38
一、概念梳理
链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧、环形缓冲和队列)
简单的说,一个列表就是单数据通过索引集合在一起。在C里面这叫做指针。比方说,一个数据元素可以由地址元素,地理元素、路由信息活着交易细节等等组成。但是链表里面的元素类型都是一样的,是一种特殊的列表。
一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中,相反,你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素。列表最后一项习惯用NIL表示,相当于python里面的None
这里介绍两种不同的列表——单链表和双链表。双链表中的某个节点只会指向列表中的下一个元素,但是在双链表里面,当前节点同时也会指向前一个节点。所以双链表会占用更多的内存,因为它需要额外的变量去存储索引
图一、单链表
图2:双链表
单链表可以从头到尾顺序查询,但是反过来就不是那么容易了。然而,双链表不管你是从哪个节点开始,从任意方向查询都是一样的。在单链表中增加和删除节点只需要两步,但是在双链表里就需要四步了。
但是在python里面没有提供像双链表一样的数据结构,所以我们可以自己创建一个这样的数据结构
二、如果使用python创建链表
(1).将节点定义成一个数据结构
首先我们将节点类定义成ListNode,该类在初始化实例对象时,定义了两个实例变量,其中data用来存储节点的值,next用来存储下一个节点的索引,下面详细介绍一下一个节点要定义的方法和属性
__init__():初始化节点
self.data:存储节点的值
self.next:存储指向下一个节点的索引
has_value():将当前节点值和其他的值比较
上面的方法和属性涵盖了一个节点应有的基本属性和行为
Listing1:The ListNode class
上面创建了最简单的节点类,下面初始化ListNode的对象
Listing2:初始化节点
上面创建了三个独立的节点
(2)创建一个单链表类
现在我们定义一个名为SingleLinkedList的类去管理我们的节点,它包含了下面这些方法:
__init__():初始化对象
list_length():返回节点数量
output_list():输出节点值
add_list_item():在列表末尾增加一个新的节点
unordered_search():根据一个特殊值去查询列表
remove_list_item_by_id():根据节点id移除节点
下面一一讲解这些方法
__init__()定义了head和tail,都初始化为None
Listing3:The SingleLinkedList class(part one)
(3)、添加节点
通过add_list_item()添加列表元素。先检测是不是ListNode的实例,如果不是,就新建一个节点。如果列表还是空的话,就把该节点当作头节点,如果不是空,就将当前节点指向下一个元素(也就是刚新添加的节点)。把新节点添加到列表当中
Listing4:The SinglelinkedList class(part two)
list_length()方法计算节点数量,返回列表的长度。在一个循环当中循环列表,self.next依次指向下一个节点
Listing5:The SingleLinkedList class(part three)
output_list()用来输出新的节点值
Listing6:The SingleLinkedList class(part four)
下面我们初始化SingleLinkedList的实例track,然后创建4个节点。
(4)查询列表
查询整个列表使用unordered_search()。它需要使用一个额外的参数帮助查询。列表的头是切入点。
(5)、从列表中移除一个元素
从列表中移除一个节点 时,指向该节点索引需要被移动到,被移除节点的下一个节点。被移除的节点会由python的垃圾回收机制清除
Listing10:Removing a node by node number
(6)、创建一个双链表
创建双链表其实就是在ListNode的基础上,在创建一个previous的属性
Listing11:Extended list node class
然后我们就可以依据上面的定义新建一个双链表类
添加新的节点跟单链表有所不同
移除双链表中的节点
python实际运用
输出结果
(7)、使用队列实现双向列表
来源:https://www.jianshu.com/p/cbde180b9445
猜你喜欢
- 本文实例讲述了python+Django+apache的配置方法。分享给大家供大家参考,具体如下:下载安装xampp套件下载mod_pyth
- 如何制作一个WAP手机的WML网页?代码如下:<%@Language=VBScriptMaxNoAds = 10'
- 原始数据在这里1.观察数据首先,用Pandas打开数据,并进行观察。import numpy import pandas as pdimpo
- 我用FSO生成了unicode的文件,但这不是我想要的。FSO可以生成utf-8格式编码的html文件吗?用什么办法才能生成?FSO的编码问
- 如果使用Python做大型海量数据批量任务时,并且backend用mongodb做数据储存时,常常面临大量读写数据库的情况。尤其是大量更新任
- 1 捕捉一个异常捕捉一个异常 以用0作为除数会得到ZeroDivisionError异常为例,print(1/0)为例程序的持续执行,不因该
- 问:怎样实现ORACLE中用一条SQL实现其它进制到十进制的转换?答:具体示例如下:-----二进制转换十进制---------------
- 和设计师打过交道的人一定也见到过少数极品,不是扎着小辫子留着小胡子,就是剃了光头抽根烟,通常说起来一套一套的人作品都很一般般,而作品一般般的
- 今天,由于工作需要,我在自己的电脑上配置了Mysql5环境,同时安装了一个phpMyAdmin管理工具,安装完成后,发现在phpMyAdmi
- 引言解释器环境:python3.5.1我们都知道python网络编程的两大必学模块socket和socketserver,其中的socket
- 这个翻滚代码没有使用什么marquee或者其它位移方法,而是每隔一秒把列表最顶端的那个li删掉,把这个li里面的内容插入到最底端新生成的li
- modelform是model衍生出来的form .modelform的用法非常死.首先在models.py里创建模型表.所有的form组件
- 本文实例讲述了PHP日志LOG类定义与用法。分享给大家供大家参考,具体如下:<?php/*** PHP log 类 */class C
- 今天我们继续向大家介绍一款翻页效果的制作。当鼠标移动到链接上时,翻页的链接区除了有悬停效果,还会放大。这样的效果具有很强烈的效果。大家适当美
- 起因修改了表结构以后执行python3 manage.py migrate 报错:django.db.utils.OperationalEr
- 本文通过Python3+PyQt5实现自定义部件–Counters自定 窗口部件。这个窗口是3*3的网格。本文有两个例子如下: /home/
- 解决方法:1。 改表法。可能是你的帐号不允许从远程登陆,只能在localhost。这个时候只要在localhost的那台电脑,登入mysql
- import md5 import sys def sumfile(fobj): m = md5.new() while True: d =
- 你一定很喜欢像QQ或者MSN好友登录提示的效果吧,那么怎么样能在网页中实现呢?asp之家为大家找到了这
- 如何通过PHP实现Des加密算法代码实例注:php7以上不支持了,因为php7去掉了某些函数, 另外变量的{}要改为[]<?phpcl