在python中使用特殊方法的单链表，被卡住

Question

带有两个类Node和LinkedList的单链表很容易实现。然而，我的问题是，当涉及到一个单一链接列表只有第一个节点访问（没有存储的长度，没有最后一个节点的访问，没有使用虚拟节点）。特殊的方法，我不能绕到我的头或找到很多关于在线类似于内置列表操作与O（1）复杂蟒蛇，比如如下：

aa = LinkedList() -- creates empty list 
aa.first() -- similar to aa[0] 
aa.rest() -- similar to aa[1:] 
aa.cons(item) -- similar to aa[item:] 
[item] + aa -- similar to aa.insert(0, item) 

任何形式的铅，帮助，指导将不胜感激。出于某种原因，我只是不能将Pythons内置列表操作符解释为LinkedList中我自己的方法，而没有虚拟节点或存储长度和迭代器。看着它，它似乎就像我很近，但我没有或找到的东西似乎有所帮助。谢谢。

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

    def getData(self): 
    return self.data 

    def getNext(self): 
    return self.next 

    def setData(self, newdata): 
    self.data = newdata 

    def setNext(self, newnext): 
    self.next = newnext 

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

    def __repr__(self): 
    return "Node(%s, %s)" % (repr(self.data), repr(self.next)) 

    def __eq__(self, other): 
    return self.data == other.data and self.next == other.next 

class myList: 
    def __init__(self): 
    self.first = Node() 

    def add(self, data): 
    newNode = Node() # create a new node 
    newNode.data = data 
    newNode.next = self.first # link the new node to the 'previous' node. 
    self.first = newNode # set the current node to the new one 

    def first(self): 
    return self.first.data 


    def __repr__(self): 
    plist = [] 
    for i in self: 
     plist.append(i) 
    return "LinkedList(%s)" % str(plist) 

Answer 1

没有看到你的代码，我认为基本的提示我可以给的是，如果你在链接的基于列表的操作的时候，它会涉及到很多的迭代。使用诸如aa.cons(item)之类的东西将会效率低下并且基于迭代，因为与基于数组的列表不同，您不能跳转到特定索引处的项目。

对于下面的例子，我要假设你LinkedList类有一个叫做first指向列表中的第一项变量和每个Node有一个名为next变量指向下一个项目在列表中，一个名为data的变量在该节点处保存数据。

对于aa.first()，应该很容易，因为您已经有一个指向第一项的变量head。只需返回即可。

对于其他的方法，你需要迭代。这是你如何循环并打印出列表的例子。

current = list.first 
while current is not None: 
    print current.data 
    current = current.next 

对于aa.rest()，您必须跳过第一项，然后循环访问列表的其余部分。要在列表中迈出一步，您基本上会跟踪您当前的位置并进行迭代。要返回列表[1：]，我想最简单的做法是创建一个新列表，然后迭代，将所有项目从1添加到最后。

aa.rest()真是aa.cons(item)只是一个特例。您遍历列表，直到您的当前指针达到item，然后创建一个包含此后所有内容的新列表。

您不一定必须从rest()和cons(...)中创建新列表才能返回，这取决于您希望如何实现它。我会留下插入让你思考。

LinkedList只有一个指向head的指针，除了添加到列表的前面或访问第一个项目之外，其他任何内容都将不会为O（1）大约O（N）。

我希望能有所帮助！

Answer 2

@sgusc发现一个真正的大问题，你到目前为止：命名一个函数first并命名一个数据属性first以及。后者会覆盖前者（因为函数实际上是在class而不是实例中）。

解决这个问题给了接近工作的东西。我简化了几件事，添加了一个小测试驱动程序，并添加了一个__iter__，它使用一个生成器依次产生每个节点的数据，以便for i in self（在myList.__repr__中）可以工作。 DIFF：

--- a/user1337598.py 
+++ b/user1337598.py 
@@ -1,4 +1,4 @@ 
-class Node: 
+class Node(object): 
    def __init__(self, data=None, next=None): 
    self.data = data 
    self.next = next 
@@ -19,27 +19,36 @@ class Node: 
    return str(self.data) 

    def __repr__(self): 
- return "Node(%s, %s)" % (repr(self.data), repr(self.next)) 
+ return "Node(%r, %r)" % (self.data, self.next) 

    def __eq__(self, other): 
    return self.data == other.data and self.next == other.next 

-class myList: 
+class myList(object): 
    def __init__(self): 
- self.first = Node() 
+ self.first = None 

    def add(self, data): 
- newNode = Node() # create a new node 
- newNode.data = data 
- newNode.next = self.first # link the new node to the 'previous' node. 
+ newNode = Node(data, self.first) # create a new node 
    self.first = newNode # set the current node to the new one 

- def first(self): 
+ def getFirst(self): 
    return self.first.data 

+ def __iter__(self): 
+  node = self.first 
+  while node is not None: 
+   yield node.data 
+   node = node.next 

    def __repr__(self): 
    plist = [] 
    for i in self: 
     plist.append(i) 
    return "LinkedList(%s)" % str(plist) 
+ 
+if __name__ == '__main__': 
+ lst = myList() 
+ lst.add(1) 
+ lst.add(2) 
+ print repr(lst) 

注意repr使用的名称LinkedList即使类名是myList。我通常写我repr功能使用self.__class__.__name__，例如：

def __repr__(self): 
    return '%s(%r, %r)' % (self.__class__.__name__, self.item1, self.item2) 

这也使得一个基类__repr__为派生类（从派生类的一点点的援助有时）工作。