python 高级链表

在前面的章节中我们已经看到了链接列表，但它只能在前面进行介绍。在本章中，我们看到另一种链接列表，其中可以前进和后退。这样一个链表被称为双链表。以下是双向链表的特点。

• 双链表包含称为第一个和最后一个的链接元素。
• 每个链接都有一个数据字段和两个称为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

# adding data elements      
   def push(self, newval):
      newnode = node(newval)
      newnode.next = self.head
      if self.head is not none:
         self.head.prev = newnode
      self.head = newnode

# print the doubly linked list      
   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

插入双链表中

在这里我们将看到如何使用以下程序将节点插入到双向链接列表中。该程序使用一个名为插入的menthod，它将新节点插入到双向链表头部的第三个位置。

# create the node class
class node:
   def __init__(self, data):
      self.data = data
      self.next = none
      self.prev = none

# create the doubly linked list
class doubly_linked_list:

   def __init__(self):
      self.head = none

# define the push method to add elements        
   def push(self, newval):

      newnode = node(newval)
      newnode.next = self.head
      if self.head is not none:
         self.head.prev = newnode
      self.head = newnode

# define the insert method to insert the element        
   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

# define the method to print the linked list
   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)

当上面的代码被执行时，它会产生以下结果 -

62  8  13  12

附加到双向链表

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

# create the node class
class node:
   def __init__(self, data):
      self.data = data
      self.next = none
      self.prev = none
# create the doubly linked list class
class doubly_linked_list:

   def __init__(self):
      self.head = none

# define the push method to add elements at the begining
   def push(self, newval):
      newnode = node(newval)
      newnode.next = self.head
      if self.head is not none:
         self.head.prev = newnode
      self.head = newnode

# define the append method to add elements at the end
   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

# define the method to print
   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)

当上面的代码被执行时，它会产生以下结果 -

62 8 12 9 45

请注意元素9和45在追加操作中的位置。