1

具有两个类 Node 和 LinkedList 的单链表很容易实现。但是我的问题是当涉及到一个只有第一个节点访问的单链表时（没有存储长度，没有最后一个节点访问，并且没有使用虚拟节点）。我无法绕开或在网上找到太多关于的特殊方法类似于具有O（1）复杂度的pythons内置列表操作，例如：

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)

任何形式的领导、帮助、指导将不胜感激。出于某种原因，如果没有虚拟节点或存储长度和迭代器，我无法将 python 的内置列表运算符解释为我自己在 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)
4

2 回答 2

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()，您必须跳过第一项，然后遍历列表的其余部分。要在列表中迈出一步，您基本上会跟踪您当前的位置并进行迭代。要返回 list[1:]，我想最简单的方法是创建一个新列表，然后迭代，将所有项目从 1 添加到末尾。

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

您不一定要从rest()and中返回新列表cons(...)，这仅取决于您要如何实现它。我会留下插入供您考虑。

如果 aLinkedList只有一个指向 的指针，head除了添加到列表的前面或访问第一项之外，您不会得到 O(1)，其他所有内容都将大约为 O(N)。

我希望这会有所帮助！

于 2012-04-17T02:03:13.220 回答
0

@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是. 我通常编写要使用的函数，例如：LinkedListmyListreprself.__class__.__name__

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

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

于 2012-04-17T04:41:24.863 回答