線形リスト

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

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

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

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

• 

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

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

• 

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

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

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

追加

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

削除

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

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

サンプル

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

• 

     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  }