Python实现双向链表

单向链表请参考:

在本文中,我们将看到另一种类型的链表,可以向前和向后移动;这样的链接列表称为双重链接列表(双向链表)。以下是双向链表的功能:

  • 双链表包含一个名为first和last的链接元素。
  • 每个链接包含一个数据字段和两个链接字段,分别称为next和prev。
  • 每个链接都使用其下一个链接与其下一个链接链接。
  • 每个链接都使用其先前的连接与其先前的链接链接。
  • 最后一个链接带有一个空链接,以标记列表的结尾。

创建双向链表

我们使用Node类创建一个双向链接列表。 现在,我们使用与“单链接列表”中相同的方法,但是除了节点中存在的数据之外,还将使用头和后指针进行正确分配,以在每个节点中创建两个链接。

class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None
 
class doubly_linked_list:
 
   def __init__(self):
      self.head = None
 
   # 添加数据元素
   def push(self, NewVal):
      NewNode = Node(NewVal)
      NewNode.next = self.head
      if self.head is not None:
         self.head.prev = NewNode
      self.head = NewNode
 
   # 打印双向链表
   def listprint(self, node):
      while (node is not None):
         print(node.data),
         last = node
         node = node.next
 
dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.listprint(dllist.head)

执行上面代码将打印 62 8 12 。

插入双向链表

将新节点插入到双向链表的开头的第三个位置。

修改代码,为doubly_linked_list类添加insert方法:

   # 定义插入方法插入元素
   def insert(self, prev_node, NewVal):
      if prev_node is None:
         return
      NewNode = Node(NewVal)
      NewNode.next = prev_node.next
      prev_node.next = NewNode
      NewNode.prev = prev_node
      if NewNode.next is not None:
         NewNode.next.prev = NewNode
 
 
dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)

重新运行程序等到:62 8 13 12。

附加到双向列表

将元素追加到双向链表的最后。

修改代码,加入append()方法。

   #定义append方法 添加元素到末端
   def append(self, NewVal):
 
      NewNode = Node(NewVal)
      NewNode.next = None
      if self.head is None:
         NewNode.prev = None
         self.head = NewNode
         return
      last = self.head
      while (last.next is not None):
         last = last.next
      last.next = NewNode
      NewNode.prev = last
      return
 
dllist = doubly_linked_list()
dllist.push(12)
dllist.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)

重新执行程序,将打印:62 8 12 9 45。

请注意附加操作的元素9和45的位置。

原创内容,如需转载,请注明出处;

本文地址: https://www.perfcode.com/p/1370.html

分类: 计算机技术
推荐阅读:
如何查看硬盘序列号(S/N) 要在Windows系统上查看硬盘序列号只需要打开命令提示符【CMD】,运行以下命令:wmic diskdrive get model,serialnumber;黄色部分是你的硬盘名称,红色部分则是硬盘序列号;
使用pyi-set_version为PyInstaller打包出来的程序附加版本信息 本文将讲述如何使用 pyi-grab_version 获取版本信息的模板文件,以及使用 pyi-set_version 为打包好的程序附加版本信息。
Python enumerate()函数 在Python中,enumerate()是一个内置函数,用于将一个可迭代对象转换为一个枚举对象,该对象包含每个元素的索引和对应的值。enumerate()函数返回的是一个由元组组成的迭代器,每个元组包含两个元素,第一个元素是元素的索引,第二个元素是元素的值。
gcc编译错误undefined reference to `std::cout'解决方法 在对C++项目进行编译时,出现undefined reference to `std::cout'编译错误,解决方法如下;使用gcc编译器编译时,添加 -lstdc++ 编译选项;
Rust line宏的用法和示例 在Rust中,line宏用于获取代码中当前的行号;通过在代码中使用line宏,开发者可以轻松地在编译时获取到所在位置地行号信息,从而实现更灵活地代码逻辑和调试方案。
Golang多个返回值有什么作用 在 Go 语言中,函数可以返回多个值,这是一项非常实用的特性,其作用如下: