サイトトップ
Director Flash 書籍 業務内容 プロフィール

Adobe Flash非公式テクニカルノート

連結リスト(linked list)

ID: FN1010001 Product: Flash CS3 and above Platform: All Version: 9 and above/ActionScript 3.0

連結リスト(linked list)は、値の容れ物として用いられるObjectとArrayクラスの中間のような仕組みです。Objectインスタンスと違って、納められた値には順序があります。けれど配列と異なり、それぞれはインデックス番号をもちません。そのつくり方と使い方をご説明しましょう。


01 前後のエレメントへの参照をもたせる
「連結リスト」(linked list)は、ひとつひとつのエレメントがその前後のエレメントの参照をもちます[*1]。したがって、順序があるものの、インデックス番号はもちません。まずは基本となる仕組みを、Objectクラスでご説明しましょう。実際に連結リストを用いる場合には、クラスとして定義します。

// フレームアクション
// エレメントとなるObjectインスタンスを作成
var element1:Object = {data:1};
var element2:Object = {data:2};
var element3:Object = {data:3};
// 前後のエレメントへの参照を設定
element1.next = element2;
element2.prev = element1;
element2.next = element3;
element3.prev = element2;

エレメントにする各Objectインスタンスには、dataというプロパティに値を納めます。そして、さらにprevおよびnextというプロパティに、それぞれの前後のエレメントへの参照を設定しました。配列の内部処理と比べた場合、たとえば先頭にエレメントを追加する処理は軽く済みます[*2]。配列であれば、後のエレメントのインデックス番号をすべて1ずつ繰下げなければならないからです。

// 前記フレームアクションに追加
var element0:Object = {data:0};
element0.next = element1;
element1.prev = element0;

エレメントの値をすべて取出すには、先頭から順に参照をたどります。たとえば、whileループを用いて、つぎのように処理すればよいでしょう(図001)。

// 前記フレームアクションに追加
var myElement:Object = element0;
while (myElement) {
  trace(myElement.data);
  myElement = myElement.next;
}

図001■Objectの連結リストからすべてのエレメントの値を順に取出す
図001左図 図001右図

[*1] 連結リストにはいくつかの種類があります。詳しくは、Wikipedia「連結リスト」をご参照ください。また、JavaにはLinkedListというクラスが備わっています。

[*2] F-site「連結リストとVectorによるエレメントの追加と削除」で簡単に処理の速さを比べています。

02 連結リストをクラス定義する
連結リストを使うには、クラスとして定義した方がよいでしょう。まず、エレメントをつくるクラスElementの定義は、つぎのスクリプト001のようになります。前項で採上げたObjectが果たしたエレメントの役割をクラスにしただけです。エレメントの値は、コンストラクタメソッド(スクリプト001第6〜8行目)に引数として渡します。

スクリプト001■連結リストのエレメントを生成するクラスElement
    // ActionScript 3.0クラス定義ファイル: Element.as
    // 連結リストのエレメントを生成
  1. package {
  2.   public class Element {
  3.     public var prev:Element;
  4.     public var next:Element;
  5.     public var data:Object;
  6.     public function Element(myData:Object) {
  7.       data = myData;
  8.     }
  9.   }
  10. }

エレメントをひとつひとつ変数に入れるのでは面倒です。そこで、エレメントをまとめ、追加や削除の操作をするためのクラスMyLinkedListを、スクリプト002のように定義します。エレメントを操作するメソッドは、必要に応じて備えなければなりません。このサンプルでは、エレメントを最後に加えるpush()と、最初のエレメントを取除くshift()のふたつのメソッドのみ定義しました。

スクリプト002■連結リストのエレメントを納めて操作するクラスMyLinkedList
    // ActionScript 3.0クラス定義ファイル: MyLinkedList.as
    // 連結リストのエレメントを納めて操作する
  1. package {
  2.   public class MyLinkedList {
  3.     public var first:Element;
  4.     public var last:Element;
  5.     public function MyLinkedList() {}
  6.     public function push(myData:Object):void {
  7.       var newData:Element = new Element(myData);
  8.       if (last) {
  9.         last.next = newData;
  10.         newData.prev = last;
  11.         last = newData;
  12.       } else {
  13.         first = last = newData;
  14.       }
  15.     }
  16.     public function shift():Object {
  17.       if (first) {
  18.         var removingElement:Element = first;
  19.         first = removingElement.next;
  20.         if (first) {
  21.           first.prev = null;
  22.         } else {
  23.           last = null;
  24.         }
  25.         return removingElement.data;
  26.       } else {
  27.         return null;
  28.       }
  29.     }
  30.   }
  31. }

プロパティには、最初と最後のエレメントの参照をもたせます(スクリプト002第3〜4行目)。そして、コンストラクタメソッドは、空のインスタンスを生成します(第5行目)。

push()メソッド(スクリプト002第6〜15行目)は、まず第8行目でプロパティ(last)に最後のエレメントの参照があるかどうかを確かめます。参照がなければ、加えるのは初めてのエレメントですので、第13行目で最初と最後のプロパティにその参照を設定します。最後のエレメントの参照があったら、第9〜10行目でそのエレメントと自身との間に前後のリンクを加えて、第11行目が最後のエレメントを自身に設定し直します。

shift()メソッド(スクリプト002第16〜29行目)は、第17行目でプロパティ(first)に最初のエレメントの参照があるかどうかを確かめます。なければ連結リストは空ですので、第27行目はnullを返します。最初のエレメントの参照があったら、第18〜19行目でそれをローカル変数に取り、プロパティはつぎのエレメントの参照で書替えます。第20〜24行目はさらに、つぎのエレメントがあるかを確かめ、あればその参照がもつ前の連結(リンク)を消し、なければ連結リストは空になりますので最後のエレメントのプロパティ(last)をnullにしています。そして、第25行目が取除いたエレメントを返します。

ひとつ注意として、MyLinkedListインスタンスは、プロパティとして最初と最後のエレメントの参照しかもちません。それでも、エレメントが互いに(prevおよびnextプロパティで)参照をもちあうため、メモリからは消えません。逆に、エレメントを消し去るには、それに対する参照を切ればよいということです。スクリプト002では、第21行目が参照を除いています。

MyLinkedListインスタンスを生成して、エレメントを追加および削除し、連結リストのすべてのエレメントを取出すテスト用のフレームアクションはつぎのとおりです(図002)。

// フレームアクション
// 連結リストのMyLinkedListインスタンス生成
var list:MyLinkedList = new MyLinkedList();
// エレメントの追加
list.push(0);
list.push(1);
list.push(2);
list.push(3);
// 最初のエレメントを削除して[出力]
trace("removing:", list.shift());
// エレメントをすべて取出す
var myElement:Element = list.first;
while (myElement) {
  trace(myElement.data);
  myElement = myElement.next;
}

図002■連結リストに対してエレメントの追加・削除およびすべての取出しを試す
図002左図 図002右図

連結リストにかぎらず、複数のデータを順番に納めるクラスについては、すべてのデータを順に取出すという処理がもれなくついてきます。その場合の処理方法、具体的には用いるプロパティやメソッドが統一されていると、クラスの使い回しがしやすくなります。

デザインパターンには、まさにすべてのエレメントを取出すためのIteratorというパターンがあります。詳しくは、「Iterator(イテレータ)パターン」をお読みください。

作成者: 野中文雄
更新日: 2010年10月12日 テクニカルノート「Iterator(イテレータ)パターン」へのリンクおよび注[*2]を追加。
作成日: 2010年10月6日
Copyright © 2001-2010 Fumio Nonaka.  All rights reserved.