在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__爲派生類（從派生類的一點點的援助有時）工作。