指定された値のすべてのインスタンスを削除するリンクリスト

Question

リンクリストで同じ値のすべてのインスタンスを削除することに多くの問題があります。問題はremove関数のself.head部分と関係があることを理解しています。

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


def getData(self): 
    return self.data 

def getNext(self): 
    return self.next 

def setData(self,newdata): 
    self.data = newdata 

def setNext(self,newnext): 
    self.next = newnext 


class UnorderedList: 

def __init__(self): 
    self.head = None 

#Checks to see if the list is empty 
def isEmpty(self): 
    return self.head == None 

#Adds the item at the beginning of the list 
def add(self,item):   
    temp = Node(item) 
    temp.setNext(self.head) 
    self.head = temp 

#Prints the Unordered List 
def __str__(self): 
    result = "[" 
    current = self.head 
    if current != None: 
     result += str(current.data) 
     current = current.next 
     while current: 
      result += ", " + str(current.data) 
      current = current.next 
    result += "]" 
    return result 

# Removes a specified item from the list 
def remove(self, item): 
    if self.head == None: 
     return 'Cannot remove from an empty list' 

    current = self.head  
    while current != None: 
     iterator = current 
     while iterator != None: 
      prev = iterator 
      iterator = iterator.getNext() 
      if iterator is None: 
       break 
      if iterator.getData() == item: 
       Next = iterator.getNext() 
       prev.setNext(Next) 
     current = current.getNext() 



mylist = UnorderedList() 

for i in range(50): 
    mylist.add(2) 
mylist.remove(2) 
print(mylist) 

結果：[2、2、2、2、2]

期待される結果：[]

Answer 1

私はあなたのremoveコードは、それが（と必要以上に少し複雑だと思いますネストされたループなど）。あなたはもっと簡単にそれを働かせることができるはずです。

ここでは、2つのループを順番に実行する方法を説明します。最初のループは、削除しているノードの先頭ノードです。 2番目のループはリストの残りの部分を処理するためのものです。

def remove(self, item): 
    if self.head == None: 
     return 'Cannot remove from an empty list' # note, you may want to raise an exception 

    while self.head is not None and self.head.data == item: # first loop, for leading values 
     self.head = self.head.next 

    if self.head is not None: # rest is only needed if the first loop didn't empty the list 
     current = self.head 
     while current.next is not None: # second loop, over all later items 
      if current.next.data == item: # check for matching items 
       current.next = current.next.next # and remove them 
      else: 
       current = current.next 

私は、彼らは気が散るとPythonコードでは通常は必要ありませんしているので、あなたが持っているgetterとsetter関数の呼び出しを残してきました。他の言語でgetterとsetter関数を使う良い理由がありますが、Pythonで属性を直接使うのは大丈夫です（APIを変更せずに実装する方法を変更する必要がある場合は、後でproperty記述子に変えることができます）。これが宿題のためのものであれば、おそらくそれを修正する必要があります。

コードにコメントしたとおり、エラーメッセージを文字列として返すのではなく、最初のifブロックにraise ValueError("cannot remove from an empty list")のようなものを使用することも適切な場合があります。 removeメソッドは、通常、何も返しません（これは返すのと同じです）。したがって、対話セッションから関数を呼び出さない限り、戻り値が通知されない可能性があります。例外は予想外の場所で発生したときにプログラムフローを分割するので（デバッグに適しています）、例外はずっと便利です。