python实现链表的方法

这篇文章将为大家详细讲解有关python实现链表的方法，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于网站设计、成都网站制作、茄子河网络推广、小程序设计、茄子河网络营销、茄子河企业策划、茄子河品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供茄子河建站搭建服务，24小时服务热线：18982081108，官方网址：www.cdcxhl.com

一、概念梳理

链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一，同时也是比较高阶的数据结构（例如棧、环形缓冲和队列）

简单的说，一个列表就是单数据通过索引集合在一起。在C里面这叫做指针。比方说，一个数据元素可以由地址元素，地理元素、路由信息活着交易细节等等组成。但是链表里面的元素类型都是一样的，是一种特殊的列表。

一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中，相反，你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素。列表最后一项习惯用NIL表示，相当于python里面的None。

这里介绍两种不同的列表——单链表和双链表。双链表中的某个节点只会指向列表中的下一个元素，但是在双链表里面，当前节点同时也会指向前一个节点。所以双链表会占用更多的内存，因为它需要额外的变量去存储索引。

python实现链表的方法

单链表可以从头到尾顺序查询，但是反过来就不是那么容易了。然而，双链表不管你是从哪个节点开始，从任意方向查询都是一样的。在单链表中增加和删除节点只需要两步，但是在双链表里就需要四步了。

但是在python里面没有提供像双链表一样的数据结构，所以我们可以自己创建一个这样的数据结构。

二、如果使用python创建链表

（1）将节点定义成一个数据结构

首先我们将节点类定义成ListNode，该类在初始化实例对象时，定义了两个实例变量，其中data用来存储节点的值，next用来存储下一个节点的索引，下面详细介绍一下一个节点要定义的方法和属性

__init__()：初始化节点
self.data：存储节点的值
self.next：存储指向下一个节点的索引
has_value()：将当前节点值和其他的值比较

上面的方法和属性涵盖了一个节点应有的基本属性和行为

Listing1:The ListNode class

python实现链表的方法

上面创建了最简单的节点类，下面初始化ListNode的对象

Listing2:初始化节点

python实现链表的方法

上面创建了三个独立的节点

（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)

python实现链表的方法