如何在双向链表中实现插入方法？

Question

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

'NoneType' object has no attribute 'setPrev'

我明白这个错误的含义，并尝试改变我的函数来避免这个错误并获得正确的输出，但无济于事。

问题：如何修复这个insert函数，让它在所有情况下都能添加节点？

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

一个测试用例是以下场景：

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 currentXthenextofcurrentandNthen(new node). First we set theprevand下一个ofn`:

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

现在我们检查 X 是否真的是一个真正的节点（虽然这完全没有必要，因为 "last nodes" 上面已经处理过了）。如果X不是None，我们将X的prev设置为N：

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

终于不需要C指向X（否则无法调用X的函数），所以我们设置next的C 到 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++

如何在双向链表中实现插入方法？

How to implement insert method in a doubly linked list?

python

algorithm

class

list

insert