Pythonで特殊なメソッドを単独でリンクしたリスト

Question

NodeとLinkedListの2つのクラスを持つ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) 

リードの任意の並べ替え、助けて、次のような特別な方法は、私は、周りに私の頭をラップまたはオンラインについて多くの組み込みのリスト操作O（1）複雑でニシキヘビと類似している見つけることができません指導は非常に高く評価されるだろう。何らかの理由で私はピットトン組み込みのリスト演算子を、ダミーノードや記憶された長さとイテレータを持たない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クラスは、リストの最初の項目をポイントすると、各Nodeは、リスト内の次の項目を指すnextという変数を持っていfirstという変数を持っていると仮定するつもりだとそのノードでデータを保持するdataという変数。

aa.first()の場合、変数headが最初の項目を指しているので、これは簡単です。ただそれを返す。

他の方法については、繰り返しが必要です。これは、リストをループして印刷する方法の例です。

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

はaa.rest()ためには、リストの残りの部分を介して第1のアイテムと、ループをスキップする必要があります。リスト内の一歩を踏み出すためには、基本的にあなたの現在の位置を追跡し、繰り返します。リスト[1：]を返すには、新しいリストを作成してから反復し、すべてのアイテムを1から最後まで追加するのが最も簡単な作業であると思います。

aa.rest()は実際にはaa.cons(item)の特別な場合です。現在のポインタがitemに達するまでリストを反復処理し、それ以降のすべてを含む新しいリストを作成します。

rest()とcons(...)から返される新しいリストを必ずしも作成する必要はありません。実装する方法によって異なります。私はあなたのことを考えるために挿入を残します。

へのポインタしかないLinkedListでは、リストの先頭に追加したり、最初のアイテムにアクセスする以外はO（1）を取得しません。他のものはすべておおよそO（N）。

少し助けてくれることを願っています！

Answer 2

@sguscは、これまでに持っているものに大きな問題があることを発見しました。関数名をfirstとし、データ属性をfirstと命名しました。後者は、関数が実際にはインスタンスではなくclassにあるため、前者をオーバーライドします。

これを修正すると、作業に近いものが得られます。私はいくつかを単純化し、少しテストドライバを追加し、for i in self（myList.__repr__）が動作できるように、各ノードのデータを生成するためにジェネレータを使用する__iter__を追加しました。差分：

--- 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は、クラス名がmyListであっても名前LinkedListを使用していること。私は通常例えば、self.__class__.__name__を使用するために私のrepr関数を記述：

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

、派生クラス（時々派生クラスから少し支援を受けて）のために働くことを基本クラス__repr__を可能にします。