線形リスト

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

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

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

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

• 

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

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

• 

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

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

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

追加

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

削除

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

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

サンプル

値として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  }
  

mainメソッドでは、変数a,b,cの３つを用いて図のようなリストを作っています。

最後に

• a.dispList();

により、aに対してメソッドdispList()を行っています。

メソッドの動作を追っかけてみましょう。

1. aの値がthisに対応づけられます。
2. x = this; により、thisに入っている値が変数xに代入されます。これはaの値と同じです。
3. 11行目のwhileの条件判定を行います。xには先に作ったリストの参照が入っており、nullではありません。
4. 13行目でx.valすなわちItemインスタンス(値はパン)に対しdisp()を行うことで、この内容を表示します。
5. 14行目でxの値をリンクの値で更新します。この結果xはリストの２番目の項目を指すことになります。
6. 再び11行目のwhileの条件判定を行います。xはリストの２番目の項目を指しており、nullではありません。
7. 13行目でx.valすなわちItemインスタンス(値はコーヒー)に対しdisp()を行うことで、この内容を表示します。
8. 14行目でxの値をリンクの値で更新します。この結果xはリストの３番目の項目を指すことになります。
9. 再び11行目のwhileの条件判定を行います。xはリストの３番目の項目を指しており、nullではありません。
10. 13行目でx.valすなわちItemインスタンス(値はみかん)に対しdisp()を行うことで、この内容を表示します。
11. 14行目でxの値をリンクの値で更新します。リンクの値はnullなのでxの値もnullになります。
12. 再び11行目のwhileの条件判定を行います。xはnullです。
13. whileループを抜け、メソッドの実行も終わります。