python - 链表和操作

Question

我需要帮助在 python 3.3 中构造一个没有构造函数参数的 LinkedList；导致一个空的 LinkedList 对象。我希望能够在列表的前面和末尾添加和删除元素。到目前为止，我只能在前面添加和添加东西。我对其他一切如何运作有点不确定。这是我到目前为止所拥有的：

class Node:
    def __init__(self, d, n):
        self.data = d
        self.next = n


class LinkedList:
    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        return self._size

    def append(self, item):
        pass

    def prepend(self, item):
        self._head = Node(item, self._head)
        self._size += 1

    def remove_first(self):
        pass

    def remove_last(self):
        pass

有人有线索吗？非常感谢！

Answer 1

您可以使用标准库中集合模块中的deque对象。您的 prepend 方法在 deque 对象中称为 appendLeft。

以另一种方式，您可以通过引用列表的最后一个节点来修改您的 LinkedList 类：

class LinkedList:
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def append(self, item):
        if self._tail is None:
            self.prepend(item)
        else:
            self._tail.next = Node(item, None)
            self._tail = self._tail.next

    def prepend(self, item):
        if self._head is None:
            self._tail = Node(item, None)
            self._head = self._tail
        else:
            self._head = Node(item, self._head)
        self._size += 1