如何在双链表中实现insert方法？

Question

我需要在我的双链接列表中实现这个insert函数，但是我很难让它在给定的索引处正确地插入元素。我可以将元素添加到空列表对象中，但当我尝试在最后一个节点添加新节点时，我收到一个错误消息：

'NoneType' object has no attribute '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

测试用例是以下场景：

^{pr2}$

输出如下：

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

Answer 1

问题是n是你自己构造的DLLNode。默认情况下，prev和{}被设置为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

最后一种情况如下：

^{pr2}$

与C下一个currentXthe下一个of当前andNtheN(new node). First we set the上一个and下一个{}N`：

 /   \|
C < N >X
|\   /

现在我们检查X是否真的是一个真正的节点（尽管这是严格不必要的，因为上面处理了“最后一个节点”）。如果X不是None，我们将X的prev设置为N：

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

最后，我们不再需要C来指向X（否则我们无法调用X的函数），因此我们将C的next设置为N：

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

你能提供测试数据来测试实现是否正常工作吗？在

Answer 2

我相信问题就在这里

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

在最后一个元素插入时，需要遍历到当前的最后一个元素，比如last。假设你做了你能做的

^{pr2}$