python中的单链表及其特殊方法

Question

一个包含两个类Node和LinkedList的单链链表很容易实现。然而，我的问题是，当涉及到只有第一个节点访问权的单链链表时（没有存储长度，没有最后一个节点访问权，并且没有使用虚拟节点）。在网上我找不到或找不到太多关于在线的特殊方法类似于pythons内置的具有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内置的list操作符解释为我自己在LinkedList中的方法。看着它，似乎我离得太近了，但我做的或找到的似乎都没有帮助。谢谢您。在

^{pr2}$

Answer 1

@sgusc发现了一个非常大的问题：命名一个函数first和命名一个数据属性first。后者最终会覆盖前者（因为函数实际上在class中，而不是实例中）。在

解决这个问题会让你的工作更接近实际。我简化了一些事情，添加了一个小的测试驱动程序，并添加了一个__iter__，它使用一个生成器依次生成每个节点的数据，这样for i in self（in myList.__repr__）可以工作。差异：

 - 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__，例如：

^{pr2}$

它还允许基类__repr__为派生类工作（有时在派生类的帮助下）。在