关注我们

Python - 双向链表

无涯教程已经在前面的章节中看到了链表(Linked Lists)，这只能向前走，在本章中将看到另一种类型的链表，其中可以向前和向后移动，叫双向链接。

创建双向链表

使用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)

执行以上代码后，将产生以下输出-

链接：https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-advanced-linked-list.html

来源：LearnFk无涯教程网

62 8 12

插入节点

在这里，将看到如何使用以下程序将节点插入到"双向链接列表"中，该程序使用一种名为insert的方法，将新节点插入到双向链表的开头的第三个位置。

# 创建节点类
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

# 定义push方法添加元素	
   def push(self, NewVal):

      NewNode=Node(NewVal)
      NewNode.next=self.head
      if self.head is not None:
         self.head.prev=NewNode
      self.head=NewNode

#定义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

#定义打印链表的方法
   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.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)

执行以上代码后，将产生以下输出-

链接：https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-advanced-linked-list.html

来源：LearnFk无涯教程网

62  8  13  12

追加节点

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

# 创建节点类
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

# 定义push方法在开头添加元素
   def push(self, NewVal):
      NewNode=Node(NewVal)
      NewNode.next=self.head
      if self.head is not None:
         self.head.prev=NewNode
      self.head=NewNode

# 定义 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

# 定义打印方法
   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.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)