無序雙鏈表Python

Question

我正在研究DoublyLinkedList類中名爲insertAt的函數。正如你從我的代碼中可以看到的，我已經獲得了一點點頭，但是由於我無法弄清楚在插入新節點後如何將節點向右移動，卡住了。我的輸出目前是 6 9 7 -4 雖然它應該是 6 9 7 25 -4
如果有人可以指出我在正確的方向我真的很感謝幫助！

__author__ = 'admin' 


class DoublyLinkedNode: 
""" A single node in a doubly-linked list. 
    Contains 3 instance variables: 
     data: The value stored at the node. 
     prev: A pointer to the previous node in the linked list. 
     next: A pointer to the next node in the linked list. 
""" 

    def __init__(self, value): 
     """ 
     Initializes a node by setting its data to value and 
     prev and next to None. 
     :return: The reference for self. 
     """ 
     self.data = value 
     self.prev = None 
     self.next = None 


class DoublyLinkedList: 
""" 
The doubly-linked list class has 3 instance variables: 
    head: The first node in the list. 
    tail: The last node in the list. 
    size: How many nodes are in the list. 
""" 

    def __init__(self): 
     """ 
     The constructor sets head and tail to None and the size to zero. 
     :return: The reference for self. 
     """ 
     self.head = None 
     self.tail = None 
     self.size = 0 

    def addFront(self, value): 
     """ 
     Creates a new node (with data = value) and puts it in the 
     front of the list. 
     :return: None 
     """ 
     newNode = DoublyLinkedNode(value) 
      if (self.size == 0): 
      self.head = newNode 
      self.tail = newNode 
      self.size = 1 
     else: 
      newNode.next = self.head 
      self.head.prev = newNode 
      self.head = newNode 
      self.size += 1 

    def addRear(self, value): 
     """ 
     Creates a new node (with data = value) and puts it in the 
     rear of the list. 
     :return: None 
     """ 
     newNode = DoublyLinkedNode(value) 
     if (self.size == 0): 
      self.head = newNode 
      self.tail = newNode 
      self.size = 1 
     else: 
      newNode.prev = self.tail 
      self.tail.next = newNode 
      self.tail = newNode 
      self.size += 1 

    def removeFront(self): 
     """ 
     Removes the node in the front of the list. 
     :return: The data in the deleted node. 
     """ 
     value = self.head.data 
     self.head = self.head.next 
     if self.head != None: 
      self.head.prev = None 
     self.size -= 1 
     return value 

    def removeRear(self): 
     """ 
     Removes the node in the rear of the list. 
     :return: The data in the deleted node. 
     """ 
     value = self.tail.data 
     self.tail = self.tail.prev 
     if self.tail != None: 
      self.tail.next = None 
     self.size -= 1 
     return value 

    def printItOut(self): 
     """ 
     Prints out the list from head to tail all on one line. 
     :return: None 
     """ 
     temp = self.head 
     while temp != None: 
      print(temp.data, end=" ") 
      temp = temp.next 
     print() 

    def printInReverse(self): 
     """ 
     Prints out the list from tail to head all on one line. 
     :return: None 
     """ 
     temp = self.tail 
     while temp != None: 
      print(temp.data, end=" ") 
      temp = temp.prev 
     print() 


    def indexOf(self, value): 
     counter = 0 
     current = self.head 
     while current.data != None: 
      if current.data == value: 
       return counter 
      else: 
       current = current.next 
      counter += 1 
     return -1 


    def insertAt(self, index, value): 
     newNode = DoublyLinkedNode(value) 
     counter = 0 
     current = self.head 
     while counter != self.size: 


      if counter == index: 
       self.size += 1 
       current.data = current.next 
       current.data = newNode.data 

      else: 

       current = current.next 
      counter += 1 



    def main(): 
     dll = DoublyLinkedList() 
     dll.addRear(6) 
     dll.addRear(9) 
     dll.addRear(25) 
     dll.addRear(-4) 

     dll.insertAt(2,7) 
     dll.printItOut() 

if __name__ == '__main__': 
    main() 

Answer 1

除了縮進之外，在insertAt（）函數中還有一些問題。

你的確無法分配DoublyLinkedNode到current.data，所以這行肯定是錯誤的：

current.data = current.next 

而且因爲你的列表密切相關，必須保留以前的節點之間的聯繫，您要添加的節點，下一節點

這是給你insertAt（）函數的一個潛在的解決方案（我依然古色古香它靠近你的代碼的目的），它輸出6 9 7 25 -4：

def insertAt(self, index, value): 
    newNode = DoublyLinkedNode(value) 
    counter = 0 
    current = self.head 
    while counter != self.size: 
     if counter == index: 
      newNode.prev = current.prev 
      newNode.next = current 
      current.prev.next = newNode 
      current.prev = newNode 
     else: 
      current = current.next 
     counter += 1  
    self.size += 1