Pythonの二重リンクリストでノードを削除する際の問題

Question

Pythonで二重リンクリストを作成しようとしましたが、私のLinkedListクラスのいくつかのメソッドに問題があります。 removeFrontとremoveRearのメソッドを削除した値を返すことができますが、これを動作させることはできません。テストリストで、ノードに値xを入力して削除しようとすると、xは返されません。

私は、ノードを削除するという考えは、次のノードを前のノードに接続することによってリストから切り離すことですが、これに対する私の試みは根本的に欠陥があると感じています。

私はまたpopメソッドを実装しようとしていますが（リスト内の特定の要素を削除するため）、どこから開始するのかはわかりません。ここに正しい方向に私を振り下ろすためのアドバイスをいただければ幸いです。ありがとうございました。

class Node: 

    def __init__(self,data): 
     self.data = data 
     self.next = None 
     self.prev = None 

class LinkedList: 

    def __init__(self): 
     self.front = None 
     self.rear = None 

    def isEmpty(self): 
     return self.front is None and self.rear is None 

    def addFront(self, data): 
     new_node = Node(data) 
     if self.front is None: 
      self.front = new_node 
      self.rear = self.front 
      self.front.prev = None 
      self.rear.next = None 
     else: 
      self.front.prev = new_node 
      new_node.next = self.front 
      self.front = new_node 
      self.front.prev = None 

    def addRear(self, data): 
     new_node = Node(data) 
     if self.front is None: 
      self.rear = new_node 
      self.front = self.rear 
      self.front.prev = None 
      self.rear.next = None 
     else: 
      self.rear.next = new_node 
      new_node.prev = self.rear 
      self.rear = new_node 
      self.rear.next = None 

    def removeFront(self): 
     if self.isEmpty(): 
      return None 
     else: 
      removed = self.front 
      self.front.prev = self.front 
      self.front.prev.next = None 
      return removed 

    def removeRear(self): 
     if self.isEmpty(): 
      return None 
     else: 
      removed = self.rear 
      self.rear.prev = self.rear 
      self.rear.prev.next = None 
      return removed 

    def pop(self, index): 
     # TODO: How to implement? 
     pass 

    def size(self): 
     current = self.front 
     count = 0 
     while current is not None: 
      count += 1 
      current = current.next 
     return count 

Answer 1

クイックコードレビュー：

• Node.__init__()は正しいです。
• LinkedList.__init__()が正しいです。
• LinkedList.isEmpty()が正しいです。
• LinkedList.size()が正しいです。

---

ここで適切にLinkedList.removeFront()を実装する方法です：

def removeFront(self): 
     if self.isEmpty(): 
      return None 
     else: 
      removed = self.front.data 
      self.front = self.front.next 
      if self.front is None: # List size was 1 
       self.rear = None 
      else: 
       self.front.prev = None 
      return removed 

私はあなたに練習としてremoveRear()の実装を残します。ロジックはremoveFront()と対称です。

---

LinkedList.addFront()は正しいのですが、単純化することができます。

def addFront(self, data): 
     new_node = Node(data) 
     if self.front is None: 
      self.front = new_node 
      self.rear = new_node 
      #self.front.prev = None # Already None 
      #self.rear.next = None # Already None 
     else: 
      self.front.prev = new_node 
      new_node.next = self.front 
      self.front = new_node 
      #self.front.prev = None # Already None 

あなたLinkedList.addRear()が正しいですが、同じように単純化することができます。

---

LinkedList.pop()を実装する方法について尋ねました。それは難しいものになるでしょう。複数のケースを考慮する必要があります。

• リストに要素が1つだけある場合はどうなりますか？
• 削除するノードが前面にある場合はどうなりますか？
• 削除するノードが背面にある場合はどうなりますか？
• 削除するノードが厳密に中間にある場合はどうなりますか？

  def removeFront(self): 
      if self.isEmpty(): 
       return None 
  
      # Store data so that it can be returned 
      data = self.front.data 
      if self.front == self.rear: 
       # List contains one item, set front & rear to initial state 
       self.front = self.rear = None 
      else: 
       # More than one item 
       self.front = self.front.next # Set front to point next item 
       self.front.prev = None   # Front doesn't have previous item 
  
      return data 
  

  removeRearは、同じロジックで正確に動作します：

Answer 2

は、ここでコメントをremoveFrontの実装です。popは、次の3つの異なるケースを考慮する必要があります実現するために

：

フロントが削除されている
• リアはフロントとリアの間
• ノードが

を削除されている削除されています

問題がどのような場合でも、削除するには正しいノードを見つける必要があります。リスト内を進んでいくうちに、これをループで行うことができます。正しいノードを見つけたら、最初のノードまたは最後のノードの場合にはremoveFrontまたはremoveRearを利用できます。ノードがどこかにある場合は、前の&ノードから切断し、残りのノードを一緒に結合する必要があります。