如何在雙向鏈表中實現插入方法？

Question

我需要在我的雙向鏈表中實現這個insert函數，並且無法正確地在給定索引處插入元素。我可以將元素添加到一個空列表對象，但是當我試圖在最後一個節點添加一個新的節點，我得到一個錯誤說：

「NoneType」對象沒有屬性「setPrev」

我明白這個錯誤是什麼意思，並試圖轉移我的功能，以避免此錯誤，並得到正確的輸出，但無濟於事。

問題：如何修復這個插入函數，以便在所有情況下都可以添加節點？

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

    def __str__(self): 
     return str(self.data) 

    def getData(self): 
     return self.data 

    def getNext(self): 
     return self.next 

    def getPrev(self): 
     return self.prev 

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

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

    def setPrev(self, new_prev): 
     self.prev = new_prev 

class DLL: 
    """ Class representing a doubly-linked list. """ 

    def __init__(self): 
     """ Constructs an empty doubly-linked list. """ 
     self.head = None 
     self.size = 0 

    def __str__(self): 
     """ Converts the list into a string representation. """ 
     current = self.head 
     rep = "" 
     while current != None: 
      rep += str(current) + " " 
      current = current.getNext() 

     return rep 

    def isEmpty(self): 
     """ Checks if the doubly-linked list is empty. """ 
     return self.size <= 0 

    def insert(self, item, index): 
     """ Inserts a node at the specified index. """ 
     # Construct node. 
     current = self.head 
     n = DLLNode(item) 

     # Check index bounds. 
     if index > self.size: 
      return 'index out of range' 

     # If the list is empty... 
     if self.isEmpty(): 
      self.head = n 
      self.head.setPrev(self.head) 

     # If the index is the first node... 
     if index == 0: 
      n.setNext(self.head) 
      self.head = n 
      if self.size == 0: 
       self.prev = n 
     # If the index is the last node... 
     elif index == self.size: 
      n.next.setPrev(n) 

     # If the index is any other node... 
     else: 
      if current == None: 
       n.setPrev(self.prev) 
       self.prev.setNext(n) 
       self.prev = n 
      else: 
       n.setNext(current) 
       n.getPrev().setNext(n) 
       current.setPrev(n.getPrev()) 
       n.setPrev(n) 

     self.size += 1 

一個TestCase是以下情形：

l = DLL() 
l.insert(88, 0) 
l.insert(99, 1) 
l.insert(77, 2) 
l.insert(55, 3) 
l.insert(34, 1) 
l.insert(3, 0) 
l.insert(15, 6) 
l.insert(100, 8) 
print("list after inserts", l) 

輸出如下：

Index out of range. 
list after inserts 3 88 34 99 77 55 15 """ 

Answer 1

的問題是，n是DLLNode你構建自己。默認情況下，prev和next設置爲Null;因此你不能調用任何方法。

def insert(self, item, index): 
    """ Inserts a node at the specified index. """ 
    # Construct node. 
    current = self.head 
    n = DLLNode(item) 

    # Check index bounds. 
    if index > self.size: 
     return 'index out of range' 

    # If the list is empty... 
    if self.isEmpty(): 
     self.head = n 
     self.head.setPrev(self.head) 
    else : #added else case to prevent overlap 
     for x in range(0,index-1): #Obtain the current 
      current = current.next #move to the next item 
     # If the index is the first node... 
     if index == 0: 
      n.setNext(self.head) 
      self.head = n 
      if self.size == 0: 
       self.prev = n 
     # If the index is the last node... 
     elif index == self.size: 
      current.setNext(n) #set n to be the next of current 
      n.setPrev(current) #set current to be the previous of n 

     # If the index is any other node... 
     else: 
      n.setNext(current.next) 
      n.setPrev(current) 
      if current.next != None : 
       current.next.setPrev(n) 
      current.setNext(n) 

    self.size += 1 

最後一種情況的工作原理如下：

/------\| 
C N X 
|\------/ 

與C的current X the下一個of當前andñtheň(new node). First we set the上一個and下一個of N`：

/------\| 
C <--N-->X 
|\------/ 

現在我們檢查X實際上是否是一個真正的節點（儘管這是嚴格沒有必要的，因爲上面處理「最後的節點」）。如果X不是None，我們設置的X的prev到N：

/------\| 
C <--N-->X 
    |\-/ 

最後，我們不不再需要C指向X（否則根本無法調用X功能），所以我們設置的nextC到N：

/--\| 
C <--N-->X 
    |\-/ 

你能提供的測試數據來測試實施工作正常？

Answer 2

我相信這個問題是在這裏

elif index == self.size: 
    n.next.setPrev(n) 

時插入的最後一個元素，你需要遍歷當前的最後一個元素說last。假設你這樣做，你可以做

elif index == self.size: 
    last.setNext(n) 
    n.setPrev(last) 
    n.setNext(head) #only if this list is also circular 
    self.size++