welcome: please sign in
location: "線形リスト"の差分
19と20のリビジョン間の差分
2009-11-05 12:25:57時点のリビジョン19
サイズ: 2246
編集者: masahiko
コメント:
2009-11-05 12:28:54時点のリビジョン20
サイズ: 2438
編集者: masahiko
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 36: 行 36:
属性(インスタンス変数)は
 . 値はItem
 . List1
属性(インスタンス変数)の型は
 . 値にはItemクラスのインスタンスが入るので Item
 . リンクには次のデータを記憶するためのオブジェクトすなわち List1のインスタンスが入りますから List1

線形リスト

線形リストは同じ形式のデータが一列に並んだものです。

データの追加や削除が配列と比べて楽に行えます。
真ん中あたりにデータを追加する場合を考えると分かります。

Javaで記述してみましょう。


このようなインスタンスを使います。

  • [添付]

  • 1つ目の変数には値を保存します
  • 2つ目の変数には次の項目へのリンクを記入します。

3つのインスタンスをつないだ例を示します。

  • [添付]

  • これより先につながっていないことを、nullという値で表します。

nullはシステムで用意されている定数です。

  • 参照型の変数はnullで初期化されます。
  • nullはどこも参照していないことを表します。


追加

途中にデータを追加するには、リンク2箇所を修正すればよい。

  • [添付]


削除

途中のデータを削除するには、リンク1箇所を修正すればよい。

  • [添付]

削除されたデータからのリンクが残っていますが、リストをたどってこのデータにたどり着くことはできません。


サンプル

値としてItemクラスのインスタンスを使った例です。

クラス名は List1 としました。

  • [添付]

属性(インスタンス変数)の型は

  • 値にはItemクラスのインスタンスが入るので Item
  • リンクには次のデータを記憶するためのオブジェクトすなわち List1のインスタンスが入りますから List1
       1  public class List1
       2  {
       3         Item val;
       4         List1 link;
       5         
       6         void dispList()
       7         {
       8                 List1 x;
       9                 
      10                 x = this;
      11                 while(x != null)
      12                 {
      13                         x.val.disp();
      14                         x = x.link;
      15                 }
      16         }
      17         
      18         public static void main(String[] args)
      19         {
      20                 List1 a;
      21                 List1 b;
      22                 List1 c;
      23                 
      24                 a = new List1();
      25                 a.val = new Food("パン", 150, 200.0, 200.0);
      26                 b = new List1();
      27                 a.link = b;
      28                 b.val = new Drink("コーヒー", 120, 250);
      29                 c = new List1();
      30                 b.link = c;
      31                 c.val = new Food("みかん", 100, 150.0, 200.0);
      32                 
      33                 a.dispList();
      34         }
      35  }
    
  • [添付]

線形リスト (最終更新日時 2010-11-29 13:13:10 更新者 masahiko)