刪除指定值的所有實例的鏈接列表

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代碼有點複雜得多，它需要（與嵌套循環等）。你應該能夠使它更簡單一點。

下面是我如何做兩個循環，一個接一個。第一個循環用於引導節點，其中包含要刪除的值。第二個循環用於處理列表的其餘部分。

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 

我已經省去了對getter和setter函數的調用，因爲它們分散注意力，在Python代碼中通常不是必需的。在其他語言中使用getter和setter函數有很好的理由，但通常只需在Python中直接使用屬性就可以了（如果您需要在不更改API的情況下更改它們的實現方式，可稍後將它們轉換爲property描述符）。如果這是一項家庭作業，您可能需要進行修復。

正如我在代碼中評論的那樣，在第一個if塊中使用類似raise ValueError("cannot remove from an empty list")的東西也可能是適當的，而不是將該錯誤消息作爲字符串返回。 remove方法通常不返回任何內容（與返回None相同），因此除非您從交互式會話中調用該函數，否則很有可能不會注意到返回值。異常更有用，因爲當它們發生在不期望的地方時（這對調試很好），它們將程序流程分解。