Python-data-structure-python-advanced-linked-list

Python-高度なリンクリスト

前の章で、リンク先のリストを既に見ましたが、ここでは前進のみが可能です。 この章では、前方と後方の両方に移動できる別のタイプのリンクリストを示します。 このようなリンクリストは、二重リンクリストと呼ばれます。 以下は、二重リンクリストの機能です。

• 二重リンクリストには、firstおよびlastというリンク要素が含まれています。
• 各リンクには、データフィールドと、nextおよびprevと呼ばれる2つのリンクフィールドがあります。
• 各リンクは、次のリンクを使用して次のリンクにリンクされます。
• 各リンクは、前のリンクを使用して前のリンクにリンクされます。
• 最後のリンクは、リストの終わりを示すためにリンクをヌルとして運びます。

二重リンクリストの作成

Nodeクラスを使用して、二重リンクリストを作成します。 これで、Singly Linked Listで使用したのと同じアプローチを使用しますが、ヘッドとネクストポインターを使用して適切な割り当てを行い、ノードに存在するデータに加えて各ノードに2つのリンクを作成します。

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

二重リンクリストへの挿入

ここでは、次のプログラムを使用して、二重リンクリストにノードを挿入する方法を確認します。 プログラムはinsertという名前のメントードを使用し、二重リンクリストの先頭から3番目の位置に新しいノードを挿入します。

# 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の位置に注意してください。