データ構造の選択次第で天国と地獄の差：コーディングに役立つ！アルゴリズムの基本（2）（2/3 ページ）

» 2008年09月01日 00時00分公開

[山下寛人，オイシックス株式会社]

先入れ先出し、キュー

　キューはスタックと逆の動作をします。つまり、データの集合からデータを取り出したときに、最初に追加されたデータが出てきます。キューへのデータの追加はエンキュー（enqueue）、データの取り出しはデキュー（dequeue）と呼びます。図にすると以下のようになります。

図2　エンキューとデキュー

　キューのような動作はFIFO（First-In First-Out）と呼ばれます。ファイフォやフィーフォと読まれます。日本語では先入れ先出しといいます。サンプルプログラムを提示します。

<html>
<body> 
<script type="text/javascript">
  function Queue() {
    this.elements = new Array();
    this.length = 0;
  }
  Queue.prototype.enqueue = function(value) {
    this.elements[this.length] = value;
    this.length++;
  }
  Queue.prototype.dequeue = function() {
    var value = this.elements[0];
    for (i in this.elements) {
      if (i == 0) {
        continue;
      }
      this.elements[i - 1] = this.elements[i];
    }
    delete this.elements[this.length];
    this.length--;
    return value;
  }
 
  var queue = new Queue();
  queue.enqueue(3);
  queue.enqueue(8);
  queue.enqueue(7);
  queue.enqueue(5);
  document.write("1回目のdequeue = " + queue.dequeue() + "<br/>");
  document.write("2回目のdequeue = " + queue.dequeue() + "<br/>");
</script>
</body>
</html>

sample2-2.html

・Queueクラス

4～7行目：

クラスQueueとコンストラクタを定義しています。ここでも内部では配列を利用します。

・enqueueメソッド

8～11行目：

enqueueメソッドを定義しています。スタックのpushと同じです。

・dequeueメソッド

12～13行目：

dequeueメソッドを定義しています。初めに最初の値を取り出します。

14～19行目：

2番目以降のデータを1つずつ前にずらしています。

20～21行目：

最後のデータが重複してしまうので最後のデータを削除します。

ポインタで次から次へ、リンクリスト

　順序を持って並んでいるデータの集合をリストまたは線形リストと呼びます。集合の中の1つのデータが次のデータの位置を持っているようなリストがリンクリストです。リンクリストは連結リストとも呼ばれます。リスト上のデータはノードまたは要素（エレメント）、次のノードの位置を指し示すものをポインタと呼びます。

図3　リンクリスト

　ポインタは次のノードを指し示すやり方もありますし、前のノードを指し示すようにしてもよいです。次のノードと前のノードの両方を指し示すようにするやり方もあります。それではリンクリストを実装してみましょう。

<html>
<body> 
<script type="text/javascript">
  function Node(value) {
    this.value = value;
    this.nextNode = null;
  }
  function LinkedList() {
    this.firstNode = null;
  }
  LinkedList.prototype.getLastNode = function() {
    if (this.firstNode == null) {
      return null;
    }
    var node = this.firstNode;
    while (node.nextNode != null) {
      node = node.nextNode;
    }
    return node;
  }
  LinkedList.prototype.add = function(value) {
    var node = new Node(value);
    if (this.firstNode == null) {
      this.firstNode = node;
      return;
    }
    var lastNode = this.getLastNode();
    lastNode.nextNode = node;
  }
  LinkedList.prototype.toString = function() {
    if (this.firstNode == null) {
      return "";
    }
    var node = this.firstNode;
    var str = node.value.toString();
    while (node.nextNode != null) {
      node = node.nextNode;
      str = str + ", " + node.value.toString();
    }
    return str;
  }
 
  var list = new LinkedList();
  list.add(3);
  list.add(8);
  list.add(2);
  document.write(list.toString());
</script>
</body>
</html>

sample2-3.html

4～7行目：

Nodeクラスを定義しています。1つのノードは値valueと次のノードへのポインタnextNodeを持ちます。

8～10行目：

LinkedListクラスを定義しています。LinkedListは最初のノードへのポインタを持っています。

11行目：

最後のノードを取得するgetLastNodeメソッドを定義しています。リストの末尾に要素を追加する際に必要になります。

12～14行目：

最初のノードがnullの場合はnullを返します。

15～19行目：

最初のノードから、次のノードがnullになるまで次のノードをたどっていきます。次のノードがなくなるとそれが最後のノードなので、returnで返します。

21～22行目：

末尾に値を追加するaddメソッドを定義します。ノードを新しく作成します。

23～26行目：

最初の要素がnullの場合には新規に作成したノードを最初の要素としてメソッドの実行を終わります。

27～29行目：

末尾のノードを取得します。末尾のノードの次のノードを新規に作成したノードとします。

30～41行目：

リンクリスト全体を文字列にした結果を返すメソッドです。最初のノードから順にたどってカンマ区切りで文字を追加していきます。

配列とリンクリスト、どっちを使う？

　たいていのことは配列を使えば実現できます。しかし、リンクリストを使った方が効率よく実行できる場合があります。

　リストの先頭にデータを挿入する処理を実装してみましょう。配列とリンクリストの両方で実装して実行時間を計測してみます。sample2-3.htmlの47行目と48行目の間に以下のコードを追加してください。

  LinkedList.prototype.addFirst = function(value) {
    var node = new Node(value);
    node.nextNode = this.firstNode;
    this.firstNode = node;
  }
  document.write("<hr/>");
  var start = Number(new Date());
  var hairetsu = new Array();
  for (i = 0; i < 1000; i++) {
    for (j = i; j > 0; j--) {
      hairetsu[j] = hairetsu[j - 1];
    }
    hairetsu[0] = Math.random();
  }
  var end = Number(new Date());
  document.write("配列の場合の実行時間：" + (end - start) + "ミリ秒<br/>");
  start = Number(new Date());
  list = new LinkedList();
  for (i = 0; i < 1000; i++) {
    list.addFirst(Math.random());
  }
  end = Number(new Date());
  document.write("リンクリストの場合の実行時間：" + (end - start) + "ミリ秒<br/>");

　あらためてsample2-3.htmlをWebブラウザで実行してみてください。筆者の環境（Windows XP、Internet Explorer 6）では配列の場合で1219ミリ秒、リンクリストの場合で31ミリ秒でした。

　配列の場合だと、先頭にデータを挿入するために、すべてのデータを1つずつずらす必要があります。データの個数分だけループするので個数が多くなれば多くなるほど時間がかかります。それに対して、リンクリストの場合は最初の要素のポインタを入れ替えるだけです。そのため非常に短時間で処理が終わります。

この木何の木、木構造

前のページへ 1|2|3 次のページへ

SpecialPR