Python - 数据结构之链表
-
简述
链表是一系列数据元素,它们通过链接连接在一起。每个数据元素都以指针的形式包含与另一个数据元素的连接。Python 在其标准库中没有链表。我们使用上一章讨论的节点概念来实现链表的概念。我们已经看到了如何创建节点类以及如何遍历节点的元素。在本章中,我们将研究称为单链表的链表类型。在这种类型的数据结构中,任何两个数据元素之间只有一个链接。我们创建这样一个列表并创建其他方法来插入、更新和删除列表中的元素。 -
链表的创建
使用我们在上一章学习的节点类创建了一个链表。我们创建一个 Node 对象并创建另一个类来使用这个 ode 对象。我们通过节点对象传递适当的值以指向下一个数据元素。下面的程序创建具有三个数据元素的链表。在下一节中,我们将看到如何遍历链表。 -
遍历链表
单链表只能从第一个数据元素开始向前遍历。我们通过将下一个节点的指针分配给当前数据元素来简单地打印下一个数据元素的值。例子
输出
执行上述代码时,会产生以下结果 - -
在链表中插入
在链表中插入元素涉及将指针从现有节点重新分配到新插入的节点。根据新数据元素是在链表的开头、中间还是末尾插入,我们有以下场景。在开头插入
这涉及将新数据节点的下一个指针指向链表的当前头。所以链表的当前头成为第二个数据元素,新节点成为链表的头。例子
输出
执行上述代码时,会产生以下结果 -最后插入
这涉及将链表的当前最后一个节点的下一个指针指向新的数据节点。所以链表的当前最后一个节点成为倒数第二个数据节点,新节点成为链表的最后一个节点。例子
输出
执行上述代码时,会产生以下结果 -在两个数据节点之间插入
这涉及更改特定节点的指针以指向新节点。这可以通过同时传入新节点和现有节点来实现,之后将插入新节点。所以我们定义了一个附加类,它将新节点的下一个指针更改为中间节点的下一个指针。然后将新节点分配给中间节点的下一个指针。输出
执行上述代码时,会产生以下结果 - -
移除项目
我们可以使用该节点的密钥删除现有节点。在下面的程序中,我们定位要删除的节点的前一个节点。然后,将该节点的next指针指向要删除的节点的下一个节点。例子
输出
执行上述代码时,会产生以下结果 -