29

タグ wiki の抜粋から:

リンクされたリストは、要素が次の (オプションで前の) 要素への参照を含むデータ構造です。リンクされたリストは、任意の位置での O(1) の挿入と削除、O(1) リストの連結、および O(1) の次の要素へのアクセスと同様に、前方 (およびオプションで後方) の位置での O(1) アクセスを提供します。ランダム アクセスは O(N) の複雑さを持ち、通常は実装されていません。

(私のものを強調)

私はこれを読んで驚きました – 単純にそのインデックスを読み取るよりも複雑さの少ないランダムなインデックスにリストを挿入するにはどうすればよいでしょうか?

ということで、のソースコードjava.util.LinkedListを見てみました。add(int, E)メソッドは次のとおりです。

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

addBefore(E, Entry<E>メソッドは単純なポインターの再割り当てですが、次のメソッドもありentry(int)ます。

if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

ハーフサイズの最適化を行っても、ここのループ (どちらか一方) は、このメソッド (したがって) が O(n) 時間の最小の最悪のシナリオで動作し、確かに一定ではないforという完全なプレゼントのように思えます。add(int, E)時間。

私は何が欠けていますか？big-O表記を誤解していますか?

4

4 に答える 4

21

これは、あなたが読んでいる記事が「そのインデックスにアクセスする」ことを別の操作と見なしているためです。この記事では、add(int, E) を実行したいインデックスに既にいることを前提としています。

結論として：

挿入または削除操作 = O(1)

n番目のインデックスでノードを見つける= O(n)

于 2013-03-31T17:40:27.267 に答える
5

まあ、それらは任意の位置での一定時間の挿入をサポートしていますが、何かを挿入したい後または前のリストエントリへのポインタがある場合に限ります. もちろん、これはインデックスだけでは機能しませんが、最適化されたコードで通常行うことではありません。

Java でもこれを行うことができますが、リスト iterator を使用する必要があります。

リンクされたリストのこのプロパティは、配列リストなどと比較して最大の利点です。たとえば、チャットルームのユーザーリストからユーザーを削除する場合、ユーザーのユーザーリスト内のユーザーの位置へのポインターを保存できるため、 、彼が部屋を出たいとき、それはO(1)操作として実装できます。

于 2013-03-31T17:35:16.143 に答える
4

新しいノードを任意のノードにリンクする操作は O(1) ですが、関係するインデックスを見つける(ループを助ける) 操作は間違いなく O(n) です。

魔法はありません;）

于 2013-03-31T17:42:35.127 に答える
2

あなたが引用したウィキページには次のように書かれています：

O(1) 任意の位置での挿入と削除

次に、次のように尋ねます。

これを読んで驚いた - リストをランダムなインデックスに挿入するにはどうすればよいですか

ここに混乱があります。位置とインデックスという用語は、同じ意味で使用されていません。ウィキは、インデックスについてではなく、イテレータまたはポインタについて話します。

于 2013-03-31T17:42:36.510 に答える