python - 如何从双向链表的末尾弹出？

Question

我有一个已实现的双向链表，我的测试用例有效，但最后一个我尝试从双向链表的末尾弹出。我已经把东西搬来搬去几个小时了，但似乎仍然无法弄清楚为什么我的 l.pop(1 - l.size) 案例不起作用。我怀疑这也可能与我的插入功能有关，但我仍然无法弄清楚我做错了什么。

问题:如何修复我的代码，以便我的双向链表从列表末尾正确弹出？

from dllnode import DLLNode

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)
        else :
            for x in range(0,index - 1):
                current = current.getNext()

            # 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 - 1:
                current.setNext(n)
                n.setPrev(current)

            # 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




    def pop(self, index):
        """ Removes and returns a node from the specified index. """

        # Check index bounds.
        if index > self.size or index < 0:
            print('index out of range')

        # If the list is empty...
        elif self.isEmpty():
            return None

        # If the index is the first node...
        if index == 0:
            temp = self.head
            new = temp.getNext()
            new.setPrev(temp.getPrev())
            self.head = new

        # If the index is the last node...
        elif index == self.size - 1:
            temp = self.head.getPrev()
            new = temp.getPrev()
            self.head.setPrev(new)
            new.setNext(None)

        # If the index is at any other node...
        else:
            temp = self.head
            for j in range(0, index):
                temp = temp.getNext()
            left = temp.getPrev()
            right = temp.getNext()
            left.setNext(right)
            right.setPrev(left)

        self.size -= 1

        return temp.getData()

"""test"""
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)

l.pop(4)
l.pop(0)
l.pop(l.size - 1) #this returns my error displayed below
print("list after pops", l)

我的输出预计如下:

Index out of range.

list after inserts 3 88 34 99 77 55 15

list after pops 88 34 99

目前我得到:

Traceback (most recent call last):
  File "dll_template.py", line 133, in <module>
list after inserts 3 88 34 99 77 55 15 
    l.pop(l.size - 1)
  File "dll_template.py", line 99, in pop
    new = temp.getPrev()
AttributeError: 'NoneType' object has no attribute 'getPrev'

当我注释掉最后的 pop 时，所有内容都会被弹出并插入，并且它会正确输出我的列表。

编辑: 我已经添加了请求的 dllnode 类。

class DLLNode:
    def __init__(self,initdata):
        """ Constructs a Node from data. """
        self.data = initdata
        self.next = None
        self.prev = None

    def __str__(self):
        """ Converts the Node into a string representation. """
        return str(self.data)

    def getData(self):
        """ Retrieves the data contained in the node. """
        return self.data

    def getNext(self):
        """ Retrieves the 'next' neighbor of this node. """
        return self.next

    def getPrev(self):
        """ Retrieves the 'previous' neighbor of this node. """
        return self.prev

    def setData(self, new_data):
        """ Replaces the data of the node. """
        self.data = new_data

    def setNext(self, new_next):
        """ Replaces the 'next' neighbor of the node. """
        self.next = new_next

    def setPrev(self, new_prev):
        """ Replaces the 'previous' neighbor of the node. """
        self.prev = new_prev

Answer 1

你的问题是这个 block :

elif index == self.size - 1:
    temp = self.head.getPrev()
    new = temp.getPrev()
    self.head.setPrev(new)
    new.setNext(None)

它所做的是从您的头脑中获取前一个(应该是None)。显然 None 没有 getPrev。

您真正想要做的是首先到达列表的末尾(并从那里开始处理)。