@blog.justoneplanet.info

日々勉強

単一方向リストと双方向リスト（singly linked list and doubly linked list）

JavaScriptを使って連結リスト（単一方向リストと双方向リスト）を考える。

■一般的なリスト

以下の例を考える。

function Person(name){
    this.name = name;
}
function List(){
    this._ary = new Array();
}
List.prototype = {
    "push" : function(name){
        var person = new Person(name);
        this._ary.push(person);
        return person;
    },
    "insertAfter" : function(personRef, name){
        var person = new Person(name);
        var counter = this._ary.length;
        while(counter > 0 && this._ary[counter] != personRef){
            this._ary[counter] = this._ary[counter - 1];
            counter--;
        }
        this._ary[counter + 1] = person;
        return person;
    },
    "toString" : function(){
        var str = '';
        for(var i = 0; i < this._ary.length; i++){
            str += this._ary[i].name + ', ';
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

ここに新しいPersonインスタンスを配列の特定の位置に挿入する。

var list = new List();
var john = list.push('John');
var mike = list.push('Mike');
alert(list.toString());//[John, Mike]
var nick = list.insertAfter(john, 'Nick');
alert(list.toString());//[John, Nick, Mike]

■単一方向リスト

配列で特定の位置pに挿入した場合、p以降の要素を全て+1側にコピーする必要がある。これは配列が大きくなったとき、コピーのコストも比例して大きくなる事を意味する。そこで以下の単一方向リストを考える。

function Person(name, personRef){
    this.name = name;
    this.next = personRef;
}
function List(){
    this._size = 0;
    this._first = null;
    this._last  = null;
}
List.prototype = {
    "push" : function(name){
        var person;
        if(this._size === 0){
            person = new Person(name, null);
            this._first = person;
            this._last  = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, null);
            this._last.next = person;
            this._last = person;
            this._size++;
            return person;
        }
    },
    "insertAfter" : function(personRef, name){
        if(personRef === this._last){
            personRef.next = new Person(name, null);
            this._last = personRef.next;
            this._size++;
            return personRef.next;
        }
        else{
            personRef.next = new Person(name, personRef.next);
            this._size++;
            return personRef.next;
        }
    },
    "toString" : function(){
        var r1 = '';
        var str = '';
        r1 = this._first;
        while(r1 != null && r1 != r){
            str += r1.name + ', ';
            r1 = r1.next;
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

Personクラス（のインスタンス）に次の順序のPerson（クラスのインスタンスのリファレンス）を保持している事で結果的にリストが完成するというものである。

var list = new List();
var john = list.push('John');
var mike = list.push('Mike');
alert(list.toString());//[John, Mike]
var nick = list.insertAfter(john, 'Nick');
alert(list.toString());//[John, Nick, Mike]

挿入部分だけ操作すれば良いので計算コストが下がる。重要なポイントは以下の2点だ。

任意のPersonインスタンスの後に挿入する場合で、それがリストの最後だった場合

Personインスタンス(A)のプロパティnextに新しいPersonオブジェクト(B)を挿入する。その時、Personオブジェクト(B)のプロパティnextは何もないのでnullとなる。listの最後の要素を表す_lastを書き換えるのを忘れないように。

personRef.next = new Person(name, null);
this._last = personRef.next;

任意のPersonインスタンスの後に挿入する場合で、それがリストの最後ではない場合

最後ではない任意のPersonインスタンス(A)のプロパティnextに新しいPersonオブジェクト(B)を挿入する。その時、現在の(A)のプロパティnextをPersonオブジェクト(B)のプロパティnextに保持する。結果的にリストに挿入した事になる。

personRef.next = new Person(name, personRef.next);

参考

連結リスト

コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。

ふむふむ

配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。

ふぇー

ここで一つ前の要素を得るメソッドgetPrevを考える。

■通常のリスト

function Person(name){
    this.name = name;
}
function List(){
    this._ary = new Array();
}
List.prototype = {
    "push" : function(name){
        var person = new Person(name);
        this._ary.push(person);
        return person;
    },
    "insertAfter" : function(position, name){
        var person = new Person(name);
        for(var i = this._ary.length; i >position + 1; i--){
            this._ary[i] = this._ary[i - 1];
        }
        this._ary[position + 1] = person;
        return person;
    },
    "getPrev" : function(position){
        return this._ary[position -1];
    },
    "toString" : function(){
        var str = '';
        for(var i = 0; i < this._ary.length; i++){
            str += this._ary[i].name + ', ';
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

■単一方向リスト

function Person(name, personRef){
    this.name = name;
    this.next = personRef;
}
function List(){
    this._size = 0;
    this._first = null;
    this._last  = null;
}
List.prototype = {
    "push" : function(name){
        var person;
        if(this._size === 0){
            person = new Person(name, null);
            this._first = person;
            this._last  = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, null);
            this._last.next = person;
            this._last = person;
            this._size++;
            return person;
        }
    },
    "insertAfter" : function(personRef, name){
        if(personRef === this._last){
            personRef.next = new Person(name, null);
            this._last = personRef.next;
            this._size++;
            return personRef.next;
        }
        else{
            personRef.next = new Person(name, personRef.next);
            this._size++;
            return personRef.next;
        }
    },
    "getPrev" : function(personRef){
        var r0 = null;
        var r1 = this._first;
        while(r1 != null){
            if(r1 == personRef){
                return r0;
            }
            r0 = r1;
            r1 = r1.next;
        }
        return null;
    },
    "toString" : function(){
        var r1 = '';
        var str = '';
        r1 = this._first;
        while(r1 != null && r1 != r){
            str += r1.name + ', ';
            r1 = r1.next;
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}
var list = new List();

getPrevの計算コストがO(n)に増えてしまった。これは単一方向リストが要素の前への参照を持たないためである。

■双方向リスト

前後の参照を保持することによりgetPrevの計算コストがO(1)に下がる。

function Person(name, personRefPrev, personRefNext){
    this.name = name;
    this.prev = personRefPrev;
    this.next = personRefNext;
}
function List(){
    this._size = 0;
    this._first = null;
    this._last  = null;
}
List.prototype = {
    "push" : function(name){
        var person;
        if(this._size === 0){
            person = new Person(name, null, null);
            this._first = person;
            this._last  = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, this._last, null);
            this._last.next = person;
            this._last = person;
            this._size++;
            return person;
        }
    },
    "insertAfter" : function(personRef, name){
        var person;
        if(personRef === this._last){
            person = new Person(name, this._last, null);
            personRef.next = person;
            this._last = person;
            this._size++;
            return personRef.next;
        }
        else{
            person = new Person(name, personRef, personRef.next);
            personRef.next.prev = person;
            personRef.next = person;
            this._size++;
            return person;
        }
    },
    "insertBefore" : function(personRef, name){
        var person;
        if(personRef === this._first){
            person = new Person(name, null, this._first)
            personRef.prev = person;
            this._first = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, personRef.prev, personRef);
            personRef.prev.next = person;
            personRef.prev = person;
            this._size++;
            return person;
        }
    },
    "getPrev" : function(personRef){
        return personRef.prev;
    },
    "getNext" : function(personRef){
        return personRef.next;
    },
    "toString" : function(){
        var r1 = '';
        var str = '';
        r1 = this._first;
        while(r1 != null && r1 != r){
            str += r1.name + ', ';
            r1 = r1.next;
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

var list = new List();
var john = list.push('John');
var mike = list.push('Mike');
alert(list.toString());//[John, Mike]
var nick = list.insertAfter(john, 'Nick');
var jack = list.insertBefore(nick, 'Jack');
alert(list.toString());//[John, Jack, Nick, Mike]

コメントはまだありません»

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment