带迭代器的双向链表

Question

我正在尝试在这些单链表操作中实现双向链表，但是如何在函数[=14]中正确实现前面的Node（antNode） =] 和 elimNode?

几乎所有在 insNode 中完成的操作都适用于 addNode 函数。

class ListNode:
    def __init__(self, data, nextNode=None):
        self.data = data
        self.nextNode = nextNode
        self.antNode = None

class DoublyLinkedListIterator:
    def __init__(self, firstNode=None):
       self.firstNode = firstNode
       self.lastNode  = firstNode
       self.iterator  = firstNode
       if firstNode:
           self.size = 1
       else:
           self.size = 0

    def addNode(self, data): # Add a Node after the iterator.
        """Pre condition: Iterator defined
           Pos condition: The data is inserted into a node after the
                          iterator. The iterator stands over this node.
        """
        newNode = ListNode(data,None) # treats the empty list
        newNode.nextNode = None
        newNode.antNode = None
        if(self.size == 0):           # treats the empty list
            self.iterator = newNode
            self.firstNode = newNode
            self.lastNode = newNode
        elif self.iterator == self.lastNode:
            self.lastNode.nextNode = newNode
            self.iterator = newNode
            self.lastNode = newNode
        else:
            newNode.nextNode = self.iterator.nextNode
            self.iterator.nextNode = newNode
            self.iterator = newNode
        self.size += 1
        return True

     def elimNode(self): # Eliminates the element over the iterator and
                         # advances the iterator to the next node.
         if(self.iterator == self.firstNode):
             if(self.lastNode == self.firstNode):
                 self.lastNode = None
                 self.firstNode = None
                 self.iterator = None
             else: # more than one node
                 #self.firstNode = self.firstNode.nextNode
                 self.firstNode = self.firstNode.nextNode
                 self.iterator.nextNode = None
                 self.iterator = self.firstNode
         else: # iterator can be under the last or an inner element
             currentNode = self.firstNode
             while currentNode.nextNode != self.iterator:
                 currentNode = currentNode.nextNode
             if self.iterator == self.lastNode:
                 self.lastNode = currentNode
                 self.iterator.nextNode = None
                 self.iterator = None
                 currentNode.nextNode = None
             else:
                 currentNode.nextNode = self.iterator.nextNode
                 currentNode = self.iterator
                 self.iterator = self.iterator.nextNode
                 currentNode.nextNode = None
         self.size = self.size - 1
         return True

在迭代器前插入节点的函数insNode 双向链表是这样的：

def insNode(self, data):  # insert a node before the iterator
    """Pre condition: Iterator defined
       Pos condition: The data is inserted into a node before the iterator.
                      The iterator stands over this node.
    """
    newNode = ListNode(data, None)  # treats the empty list
    newNode.nextNode = None
    newNode.antNode = None
    if (self.size == 0):  # treats the empty list
        self.iterator = newNode
        self.firstNode = newNode
        self.lastNode = newNode
    elif self.iterator == self.firstNode:  # iterator is on the first element
        newNode.nextNode = self.firstNode
        self.iterator.antNode = newNode
        self.firstNode = newNode
        self.iterator = newNode
    else:  # iterator is on an inner element
        newNode.antNode = self.iterator.antNode
        self.iterator.antNode.nextNode = newNode
        self.iterator.antNode = newNode
        self.iterator = newNode
    self.size += 1
    return True

Answer 1

答案是：是的，您应该在 insNode 中进行类似的更改。但是，大部分代码都是相似的，因此我将创建一个辅助函数来执行这两种方法的共同操作。此外，让 ListNode 构造函数也为 antNode 属性采用可选参数。

不是你的问题，而是：

elimNode 方法应该更好地检查 self.iterator 不是 None.
我发现 iterator 这个名字令人困惑，因为 iterator 在 Python 中是一个非常具体的概念，而不是这个.所以我会将其重命名为 cursor 或 currentNode 或其他名称。我可以理解这是在一些模板代码或练习中给出的，但它并不能真正说明教学的质量 material。
我真的不明白主 class 的构造函数中可选节点参数的用途。我要么忽略它，要么让它接受可变数量的 data 值。这样比较实用

这是它的样子：

class ListNode:
    def __init__(self, data, antNode=None, nextNode=None):
        self.data = data
        self.nextNode = nextNode
        self.antNode = antNode


class DoublyLinkedListWithCursor:  
    def __init__(self):
        self.firstNode = self.lastNode = self.currentNode = None
        self.size = 0
        
    def _insertBetween(self, data, before, after):
        # Helper function for common logic in insNode and addNode methods
        self.currentNode = ListNode(data, before, after)
        if after:  
            after.antNode = self.currentNode 
        else:
            self.lastNode = self.currentNode
        if before:  
            before.nextNode = self.currentNode 
        else:
            self.firstNode = self.currentNode
        self.size += 1
    
    def insNode(self, data):
        self._insertBetween(data, self.currentNode.antNode if self.currentNode else self.lastNode, self.currentNode)

    def addNode(self, data):
        self._insertBetween(data, self.currentNode, self.currentNode.nextNode if self.currentNode else self.firstNode)
    
    def elimNode(self):
        if not self.currentNode:  # Sanity check
            return False
        if self.currentNode.antNode:
            self.currentNode.antNode.nextNode = self.currentNode.nextNode
        else:
            self.firstNode = self.currentNode.nextNode
        if self.currentNode.nextNode:
            self.currentNode.nextNode.antNode = self.currentNode.antNode
        else:
            self.lastNode = self.currentNode.antNode
        self.currentNode = self.currentNode.nextNode
        self.size -= 1
        return True

带迭代器的双向链表

Doubly Linked list with iterator

python

doubly-linked-list