如何在python中实现链表

一、概念梳理

链表是计算机科学中使用最广泛的数据结构之一。它是最简单的数据结构之一，也是高阶数据结构（如堆栈、环形缓冲区和队列）

简单来说，列表就是通过索引对单个数据的集合。在 C 中，这称为指针。例如，一个数据元素可以由地址元素、地理元素、路由信息或交易详情等组成。但链表中的元素类型是相同的，是一种特殊的链表。

单个列表元素称为节点。这些节点不像数组那样顺序存储在内存中。相反，你可以通过使用从一个节点到另一个节点的指针，在内存中的不同位置找到这些元素。列表中的最后一项习惯上用 NIL 表示，相当于 python 中的 None。

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

单链表可以从头到尾依次查询，但是反过来就不是那么容易了。但是，双向链表查询在任何方向上都是相同的，无论你从哪个节点开始。在单链表中添加和删除节点只需要两步，而在双向链表中需要四步。

但是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）使用队列实现双向列表

python学习网，免费的在线学习
，欢迎关注！