python 高級鏈表

在前面的章節(jié)中我們已經(jīng)看到了鏈接列表，但它只能在前面進行介紹。在本章中，我們看到另一種鏈接列表，其中可以前進和后退。這樣一個鏈表被稱為雙鏈表。以下是雙向鏈表的特點。

• 雙鏈表包含稱為第一個和最后一個的鏈接元素。
• 每個鏈接都有一個數(shù)據(jù)字段和兩個稱為next和prev的鏈接字段。
• 每個鏈接都使用其下一個鏈接與其下一個鏈接鏈接。
• 每個鏈接都使用其上一個鏈接與之前的鏈接鏈接。
• 最后一個鏈接將鏈接作為空來標記列表的結(jié)尾。

創(chuàng)建雙向鏈表

我們使用node類創(chuàng)建一個雙鏈表?，F(xiàn)在我們使用與單鏈表中相同的方法，但是除了存在于節(jié)點中的數(shù)據(jù)之外，頭指針和下一個指針將用于正確分配以在每個節(jié)點中創(chuàng)建兩個鏈接。

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)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

62 8 12

插入雙鏈表中

在這里我們將看到如何使用以下程序?qū)⒐?jié)點插入到雙向鏈接列表中。該程序使用一個名為插入的menthod，它將新節(jié)點插入到雙向鏈表頭部的第三個位置。

# 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)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

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)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

62 8 12 9 45

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