単一リンクリスト削除

Question

私はSingly-Linked Listの実装を行っていましたが、Linus Torvaldsがそれについて話していることを覚えていますhere。

ノードを削除するために単一リンクされたリストでは、前のノードにアクセスして、それが現在指しているノードを変更する必要があります。我々は、前のノードへのアクセスを持っている必要があり、この

だから、どのような方法と同様に

。

しかしLinus TorvaldsはCのアドレスの考え方を使って特殊なケースを削除しました。そのヘッドには頭を指している頭のアドレスである「前のもの」もあります。だから彼は特殊なケースを削除するためにCのポインタとアドレスの機能を使用しています。

通常の場合

になってきて、特別なケースで特殊なケースで、通常のコード

コードは、私たちので、単独リンクリスト内の特殊なケースの除去のこの種は、Pythonで行うことができないと思いますポインタの概念を持っていない（したがって私は頭の前に一歩行くことはできません）？私は正しい？

Answer 1

もちろん、これはPythonで行うことができます。彼が言っていることは、リスト自体を表し、リストの先頭を指し示すデータ構造を持っていて、最初のリスト項目を扱っているときにリスト項目のポインタと同じように操作するということです。

今やPythonはCではないので、実装は異なるでしょうが、原則が適用されます。リスト自体は最初の項目と同じオブジェクトではなく、リスト項目はリスト全体と同じメソッドを持つべきではないため、別々の種類のオブジェクトを使用するのが理にかなっています。

しかし、どちらも同じ名前の属性（たとえばnext）を使用して次の項目を指すことができます。したがって、リストを繰り返し、最初の項目にある場合、「前の」項目はリストそのものであり、最初の項目を削除する必要がある場合は、その項目のnextを操作しています。

実際には、エクササイズ以外はPythonリンクリストクラスを書くことは決してありません。内蔵のlistがより効率的です。

Answer 2

あなたがよく知っているように、Pythonにポインタ（そのような）やアドレス演算子がないため、Linusの特定のトリックをPythonで使用することはできません。しかし、リストにダミーヘッドノードを付けることによって、リストヘッドの特殊なケースを排除することはできます。これをリストの設計の本質的な部分として行うこともできますし、余分なノードを作成し、最初のデータ保持ノードを次のノードとして参照することで、即座に実行することもできます。いずれにしても、削除したいノードはすべて特別ノードではなく内部ノードです。

Answer 3

あなたの質問を読んで私が最初に思ったのは、なぜPythonで単独でリンクされたリストを作成したいのですか？ Pythonは豊富なコレクション型を提供しています。これらは、単一リンクリスト、ダブルリンクリスト、または非再帰的なデータ構造（通常は扱いやすい）として実装されているかどうかを心配することなく使用できます。

しかし、あなたの質問に対する答えは、Pythonは単なるリンクリストを作成することができます。たとえば、次のコードはまさにそれを行います。

class Node: 
    def __init__(self, x, next): 
     self.x = x 
     self.next = next 

    def __str__(self): 
     return "<{}, {!s}>".format(self.x, self.next) 

n = Node(1, None) 
n = Node(2, n) 
n = Node(3, n) 
print(n) # output: <3, <2, <1, None>>> 

n.next.next = n.next.next.next 
print(n) # output: <3, <2, None>> 

Cに差がある：私たちはmalloc()に持っているか、Pythonが私たちのためにメモリを処理するためのポインタでは動作しませんでした。 Pythonにはポインタの代わりに参照がありますが、それらは似ていますが、はるかに安全で使いやすいものです。

ただし、リンクされたリストを実装する前に、コレクションに関する要件を検討し、組み込み関数またはコレクションモジュールから適切なものを選ぶことができます。

Answer 4

Linusが示唆しているように間接参照を行うには、2つのレベルの間接指定が必要ですが、おそらくオブジェクトへの参照を格納しているPythonで行うこともできます。インデックス？）。つまり、私はそれが非常にエレガントに、または効率的にPythonにマップされているとは思えません。リンクされた構造内の単一のリンクを表すためにオブジェクトを使用するのはおそらくかなり無駄でしょう。

Pythonの場合、私は行方不明のトリックがない限り、頭から取り除いている場合をチェックするために追加の分岐を行うだけです。

リンクリストを自分で実装するためには、実際には標準ライブラリでは十分ではない多くのユースケースがあります。グリッドは、10,000個の細胞を持っているかもしれません

...：ここでは一例です。標準ライブラリで提供されているほとんどのリンクリストは、リンクリストを単独で使用できるようにするインターフェイスを提供しようとしているため、リストごとに32ビットインデックスのサイズで10,000以上のリンクリストを格納するよう最適化されていません。配列のような記憶のための分離したバッキングデータ構造）。通常、リンクリストの最も効率的な使用は、メモリを所有していないか、またはリソースを管理していないリストです。これは、階層の任意のレベルに要素を格納できるn-aryツリー内の128ビット（16バイト）ツリーノードの場合のように、別のデータ構造ですでに割り当てられて管理されている補助的な方法でデータをリンクするだけです。

struct TreeNode 
{ 
    int32 parent;  // parent index or -1 for no parent 
    int32 first_child; // first child of this node or -1 
    int32 next_sibling; // next child for the parent node or -1 
    int32 element;  // element data stored in this node or -1 
         // if no data is associated 
}; 

だから、ユースケースの多くはより狭く、該当するユースケース（グリッドデータ構造、オクトリ、クワッド木、グラフなどのためにはるかに効率的であるあなた自身のリンクリストおよびその他のリンク構造を実現するためにあります）しかし、私はあなたが2つ以上のレベルのポインタ間接指定を容易に利用できないような言語でこのトリックを使用することはできないと思います。 Pythonは本質的にオブジェクト用のものしか持っていません - JavaやC＃でも同じです。オブジェクト ""のようなオブジェクトへの参照への参照 "または"オブジェクトへのインデックスへのインデックス "または"オブジェクトへのオブジェクト参照へのインデックス ""へのインデックス。

また、リンクされたリストは、メモリ内にすべてのものが格納されている場所を管理することができない言語ではあまり役に立ちません。そうしないと、各リストノードが断片化されているGCサイクルの後にしばしば起こるようなメモリ、例えばリンクされたリストがLinuxカーネルの場合のように本当に効率的であるためには、各ノードがメモリ内にある場所を細かく制御できる必要があります。そのため、リストトラバーサルは実際にはほとんどではないにしても、ほとんど連続したチャンクメモリ。それ以外の場合は、線形時間の削除や中間からの挿入を意味していても、通常は小さな配列を使用する方が良いでしょう。