链表和操作

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