链表是计算机科学里面应用最广泛的数据结构之一这篇文章主要介绍了使用 python 实现链表操作, 需要的朋友可以参考下
一概念梳理
链表是计算机科学里面应用应用最广泛的数据结构之一它是最简单的数据结构之一, 同时也是比较高阶的数据结构(例如棧环形缓冲和队列)
简单的说, 一个列表就是单数据通过索引集合在一起在 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)使用队列实现双向列表
来源: http://www.phperz.com/article/18/0214/363228.html