我需要为一个项目创建一个双向链表，它应该具备一个addFirst方法，用来在链表开头前置一个元素，以及一个addLast方法，将其追加到链表末尾。addFirst方法看起来工作正常，但addLast只有在链表为空时才起作用。如果链表中已经有至少一个节点，它就不会再添加。

class DoublyLinkedList(LinkedList):
    def __init__(self):
        LinkedList.__init__(self)
        self.tail = None

    def addLast(self, item):
        newNode = Node(item)        # make the given value a node
        newNode.prev = self.tail    # point the new node to the tail of the list
        if self.head is None:       # if it is an empty list just make it the head
            self.head = newNode
        self.tail = newNode         # the tail is now the new node
        self.count += 1             # num of items in the list is updated

    def addFirst(self, item):
        newNode = Node(item)        # make the given value a node
        newNode.next = self.head    # point new node to the head of the list
        """ if self.head is None:   # this part is commented out bc it was redundant
            self.head = newNode """ 
        self.head = newNode         # make the new node the head
        self.count += 1             # num of items in list is updated

下面是它继承自的链表类

class LinkedList():
    """Linked List class implementation"""

    def __init__(self): #Create a linked list
        self.head = None
        self.count = 0

    def is_empty(self): #Is the list empty?
        return self.head is None

    def size(self): #Size of the list
        return self.count

    def __len__(self): #Size of the list
        return self.count

    def __str__(self): #List as a stringE
        list_str = "["
        current = self.head

        while current:
            list_str += str(current)
            if current.next:
                list_str += ", "
            current = current.next
        list_str += "]"
        return list_str

    def add(self, value): #Add a new node
        newNode = Node(value)
        newNode.next = self.head
        if self.count == 0:
            self.tail = newNode
        self.head = newNode
        self.count = self.count + 1

    def append(self, value):
        curr = self.tail
        while curr.next:
            curr = curr.next
        newNode = Node(value)
        curr.next = newNode
        self.count += 1

    def remove(self, value): #Remove a node with a specific value
        curr = self.head
        prev = None
        while curr:
            if curr.data == value:
                if prev is None:
                   self.head = curr.next
                else:
                   prev.next = curr.next
                self.count = self.count -1 #self.count -= 1
                return
            prev = curr
            curr = curr.next
        raise ValueError(f"{value} is not in the list")

    def search(self, value): #Search for a node with a specific value
        curr = self.head

        while curr:
            if curr == value:
                return True
            curr = curr.next

        return False

以及我的节点类，方便参考

class Node: #a node of a linked list

    def __init__(self, node_data): #create new node
        self.data = node_data
        self.next = None
        self.prev = None

    def __str__(self): #overloads string operator
        return str(self.data)

我真的束手无策，调试似乎确实表明问题在于addLast结束时根本没有向列表添加值，因为查看打印方法时，节点的值显示为None。看起来尝试给尾部赋值的任何操作都不会被加入。据我所知，头指针和尾指针在初始时都应为None，它们的行为应该相同。

编辑：打印尾部时发现我添加的值确实在那里，所以我认为问题出在字符串化的方法，而不是尾部。

我在网上也查了很多，但我看到的每一个链表示例似乎都与我要用的实现不同。如果能想到其他选项我就不会来问这里，所以如果需要我再提供更多信息，请告诉我，因为我之前从未在这里提问过。

解决方案

有几个问题。

首先，你的双向链表的 addLast 方法并没有将尾节点的 next 属性设置为指向新创建的节点。它只设置了一个 prev 属性，从未设置 next。

你可能以为继承关系会处理这件事，但基类 LinkedList 的 append 方法和 add 方法都从未被调用。

其次，若你确实调用了基类的方法，仍然会有问题，因为 append 方法不会更新 self.tail 的值，因此 self.tail 并不能保证指向尾节点。

我猜你希望 LinkedList 代码处理 next 属性，而 DoublyLinkedList 代码处理 prev 属性。因此你需要先修正 append 方法中的错误。举例来说，可以这样：

    def append(self, value):
        if self.count == 0:
            return self.add(value)
        # by definition the tail has its next attribute set to None (no loop needed)
        self.tail.next = Node(value)
        self.tail = self.tail.next  # update the reference to the tail
        self.count += 1

在 DoublyLinkedList 类中，依赖上述代码的方法可以通过在 addLast 方法中调用它来实现。可能长成这样：

    def addLast(self, item):
        prev_tail = self.tail
        super().append(item)        # apply the logic from base class
        self.tail.prev = prev_tail

你的 addFirst 也存在类似的问题，因为它只设置 next 属性，而没有设置 prev 属性。你不会在把列表转成字符串时注意到这一点——因为那只是依赖 next 属性——但 prev 属性将无法正确设置。下面给出一种可能的修正方式：

    def addFirst(self, item):
        super().add(item)           # apply the logic from base class
        if self.head.next:
            self.head.next.prev = self.head

其他备注

• 避免在循环中用 += 构造字符串：每次迭代都会创建一个新字符串。
• 两个类在向列表添加值的方法上应使用相同的名称：这样用户就不会误把单向链表的方法用于双向链表。
• 定义 __iter__，这对其他方法（包括 __str__）有用。
• 允许构造函数接收一些值来初始化链表。
• 将对 next（和 prev）的操作集中在一个方法中，所有其他逻辑都依赖它：这样在实现双向链表时，基本上只需要覆盖一个方法。
• 我建议将链表设计成循环的，甚至引入一个哨兵节点（哨兵），这通常会让代码更简洁一些。这些改动只是类内部实现，不必影响用户要使用的接口。
• 你的代码中没有任何方法能够体现双向链表的优势。在你提供的实现里，双向链表只是增加了对 prev 的管理开销，没有带来任何好处。因此我建议添加一些在双向链表中更有效的方法，例如 __reversed__。
• 如果不打算让用户直接使用你的类的属性，或许可以在链表属性前加上前缀 _。

下面演示一个可行的做法：

from typing import override

class LinkedList():
    class Node:  # A node of a singly linked list
        def __init__(self, value, nxt=None):
            self.data = value
            self.makeneighbors(nxt or self)

        # Override this method when needing a doubly linked list
        def makeneighbors(self, nxt):
            self.next = nxt

        def addafter(self, value):
            # Create a node of the same type and link it 
            self.makeneighbors(type(self)(value, self.next))

        def removenext(self):
            self.makeneighbors(self.next.next)

        def __str__(self):
            return str(self.data)


    def __init__(self, *init_data):
        self._sentinel = self.Node(None)
        self._count = 0
        for data in init_data:
            self.addlast(data)

    def isempty(self):
        return not self._count

    def size(self):
        return self._count

    def __len__(self):
        return self._count

    def _iterprevnodes(self):
        node = self._sentinel
        while node.next != self._sentinel:
            yield node
            node = node.next

    def __iter__(self):
        return (node.next.data for node in self._iterprevnodes())

    def __str__(self):
        return str(list(self))

    def addfirst(self, data):
        self._sentinel.addafter(data)
        self._count += 1

    def addlast(self, data):
        self._sentinel.data = data
        self.addfirst(None)
        self._sentinel = self._sentinel.next

    def remove(self, data):
        prevnode = next((node for node in self._iterprevnodes() if node.next.data == data), None)
        if not prevnode:
            raise ValueError(f"{data} is not in the list")
        prevnode.removenext()
        self._count -= 1


class DoublyLinkedList(LinkedList):
    class Node(LinkedList.Node): # A node of a doubly linked list, overriding behaviour
        @override
        def makeneighbors(self, nxt):
            super().makeneighbors(nxt)
            nxt.prev = self

    # Define some methods for which a doubly linked list is better suited
    def _iternodesreversed(self):
        node = self._sentinel.prev
        while node != self._sentinel:
            yield node
            node = node.prev

    def __reversed__(self):
        return (node.data for node in self._iternodesreversed())