[AS3] 連結リストとVectorによるエレメントの追加と削除 [Edit]

投稿者：野中 文雄 | 投稿日：2010.10.12 | [AS 3][ActionScript][Tips][野中ゼミ]

「連結リスト」(linked list)はObjectとArrayクラスの中間のような仕組みで、エレメントには順序があるもののインデックス番号をもちません。その処理の速さを、Vectorクラスと比べてみます。

連結リストの各エレメントは、その前後のエレメントの参照をもちます。そのため、順序はあってもインデックス番号がないのです。連結リストの仕組みについて詳しくは、「連結リスト(linked list)」をお読みください。

ここでは、エレメントを最後に加える操作と先頭からエレメントを除く操作について、連結リストとVectorクラスを比べてみます。Vectorクラスのメソッドでは、push()とshift()です。テスト用のスクリプトをwonderflに掲げました。エレメントはuint型にしています。

push() and shift() operation of Vector and Linked List - wonderfl build flash online

エレメントを最後に加えていく処理は、連結リストの有利さが感じられず、Vector.push()メソッドより遅い結果になりました。けれど、先頭からエレメントを取出す場合には、インデックスの連番を振り直す必要がありません。単に先頭エレメントの参照を切るだけですから、連結リストの速さが際立ちます。

先頭エレメントの追加や削除、あるいは(インデックスでなく)エレメントの参照から途中に操作を加えるような処理には、連結リストが適しているでしょう。

コメント

この記事へのコメント

  1. ●1.野中 文雄（2011年06月02日 12:15）

    梅原さんがwonderflに、他のメソッドも実装した連結リストのクラスを投稿され、ArrayやVectorクラスと速さを比べています。

    「Array,Vector,LinkedListの速度比較」
    http://wonderfl.net/c/y7dJ

この記事にコメントを書く

記事に対するテクニカルな質問はご遠慮ください（利用規約）。

その他の記事