8

だから私はJSでリンクされたリストをいじっていて、次の質問を思いつきました:

5000 要素の配列と連結リストがあるとします。インデックス 10 に新しい要素を挿入します。配列の方法は非常に単純です。指定されたインデックスに新しい要素を挿入し、残りの要素を 1 インデックス前に移動します。だから私はリンクされたリストでこれをやろうとしましたが、次のようになりました:

Nicholas Zakasから連結リストの実装を取得し、 メソッド addOnPosition(data,index) を追加します。最後にコードは次のとおりです。

function LinkedList() {
this._head = null;
this._length = 0;
}

LinkedList.prototype = {

constructor: LinkedList,

add: function(data) {

    var node = {
            data: data,
            next: null
        },
        current;

    if (this._head === null) {
        this._head = node;
    }
    else {
        current = this._head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }
    this._length++;
},

remove: function(index) {

    if (index > -1 && index < this._length) {

        var current = this._head,
            previous,
            i = 0;


        if (index === 0) {
            this._head = current.next;
        }
        else {
            while (i++ < index) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }

        this._length--;
        return current.data;
    }
    else {
        return null;
    }
},

item: function(index) {

    var current = this._head,
        i = 0;

    if (index > - 1 && index < this._length) {

        while (i++ < index) {
            current = current.next;
        }
        return current.data;

    }
    else {
        return null;
    }
},

addOnPosition: function(data,index) {

    if (index > -1 && index <= this._length) {
        var node = {
                data: data,
                next: null
            },
            current = this._head,
            i = 0,
            temp,
            previous;

        if (this._head === null) {
            this._head = node;
        }
        else {
            if (index === 0) {
                this._head = node;
                node.next = current;
            }
            else {
                while (i++ < index) {
                    previous = current;
                    current = current.next;
                }
                previous.next = node;
                node.next = current;
            }
        }
        this._length++;
    }
    else {
        return null;
    }
},

toArray: function() {
    var result = [],
        current = this._head;

    while (current) {
        result.push(current.data);
        current = current.next;
    }
    return result;
},
toString: function() {
    return this.toArray().toString();
}
}

最後に、私の質問は次のとおりです。この方法は、配列でこれをすべて行うよりも高速ですか?もしそうなら、両方の複雑さは何ですか? そしておそらくもっと重要なのは、adOnPosition メソッドの実装で何かを見逃していませんか?

4

2 に答える 2

6

実際には、リンクされたリストの途中への挿入は O(n) 時間の複雑さです。つまり、平均でかかる時間、または最悪の場合、リストに既に存在する要素の数 (つまり n) に比例します。「O(index)」はリアルタイムの複雑さではありません。

配列の途中に挿入するための時間計算量も O(n) です。「O(長さ - インデックス)」もリアルタイムの複雑さではありません。平均または最悪の場合のリスト内の要素のシフトに含まれる操作の数は、リスト内の項目の数 (つまり n) に比例します。

配列よりもリンクされたリストの利点は、リストの前後に要素を前後に追加することは O(1) 時間の複雑さですが、配列の場合は O(n) です。

リンク リストに対する配列の利点は、配列から要素をインデックスで取得するのが O(1) であるのに対して、リンク リストの場合は O(n) であることです。

リンクされたリストと配列のどちらを使用するかを決定する最も簡単な方法は、データの高速な追加/先頭追加またはインデックス ベースの高速検索が必要かどうかを判断することです。両方が必要な場合は、これらのデータ構造にいくつかのバリエーションがあり、両方の領域で優れたパフォーマンス/妥協を提供します。

于 2014-01-04T08:29:19.787 に答える