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

在没有看到你的代码的情况下，我想我能给出的基本提示是，如果你在基于链表的操作中，这将涉及到大量的迭代。使用aa.cons(item)这样的东西效率低下，而且基于迭代，因为与基于数组的列表不同，您不能跳转到特定索引处的项。在

对于下面的示例，我将假设您的LinkedList类有一个名为first的变量，它指向列表中的第一个项，每个{}都有一个名为next的变量，该变量指向列表中的下一项，以及一个名为data的变量，该变量保存该节点上的数据。在

对于aa.first()，这应该很容易，因为已经有一个变量head指向第一个项。把那个还给我。在

对于其他方法，您需要迭代。这是一个示例，说明如何循环并打印出列表。在

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

对于aa.rest()，您必须跳过第一项，然后遍历列表的其余部分。要在列表中迈出一步，您实际上需要跟踪当前位置并进行迭代。为了返回list[1:]，我想最简单的事情就是创建一个新的list，然后迭代，将从1到末尾的所有项都添加进来。在

aa.rest()实际上只是aa.cons(item)的一个特例。迭代列表，直到当前指针到达item，然后创建一个新列表，其中包含此后的所有内容。在

您不必创建新的列表来从rest()和cons(...)返回，这取决于您希望如何实现它。我留下插页给你考虑。在

对于一个只有一个指向head的指针的LinkedList，除了添加到列表的前面或访问第一个项之外，其他任何内容都将近似于O（N）。在

我希望这能有所帮助！在

Answer 2

@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__为派生类工作（有时在派生类的帮助下）。在