python 高級(jí)鏈表

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

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

創(chuàng)建雙向鏈表

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

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)

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

62 8 12

插入雙鏈表中

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

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

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(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)

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

62 8 12 9 45

請(qǐng)注意元素9和45在追加操作中的位置。