Python - 数据结构之高级链表
-
简述
我们已经在前面的章节中看到过链表只能向前移动。在本章中,我们看到了另一种类型的链表,它可以向前和向后移动。这样的链表称为双向链表。以下是双向链表的特点。-
双向链表包含一个名为 first 和 last 的链接元素。
-
每个链接带有一个数据字段和两个链接字段,称为 next 和 prev。
-
每个链接都使用其下一个链接与其下一个链接链接。
-
每个链接都使用其前一个链接与其前一个链接链接。
-
最后一个链接带有一个为空的链接以标记列表的结尾。
-
-
创建双向链表
我们使用 Node 类创建一个双向链表。现在我们使用与单链表中使用的方法相同的方法,但是除了节点中存在的数据之外,head 和 next 指针将用于正确分配以在每个节点中创建两个链接。例子
输出
执行上述代码时,会产生以下结果 - -
插入双向链表
在这里,我们将看到如何使用以下程序将节点插入到双向链接列表中。该程序使用一种名为 insert 的方法,该方法将新节点插入到双向链表头部的第三个位置。例子
输出
执行上述代码时,会产生以下结果 - -
附加到双向链表
追加到双向链表将在末尾添加元素。例子
输出
执行上述代码时,会产生以下结果 -请注意附加操作中元素 9 和 45 的位置。