welcome: please sign in
location: "線形リスト"の差分
24と30のリビジョン間の差分 (その間の編集: 6回)
⇤ ← 2009-11-05 12:46:47時点のリビジョン24 →
サイズ: 4321
編集者: masahiko
コメント:
← 2010-11-23 12:22:13時点のリビジョン30 → ⇥
サイズ: 746
編集者: masahiko
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 1: 行 1:
## page was renamed from リスト処理 #acl All:
行 3: 行 3:
線形リストは同じ形式のデータが一列に並んだものです。<<BR>> 同じ形式のデータが一列に並んでおり、
前から順にたどりながら参照できる形のものを'''線形リスト'''といいます。
行 5: 行 6:
データの追加や削除が配列と比べて楽に行えます。<<BR>>
真ん中あたりにデータを追加する場合を考えると分かります。		 これも'''線形リスト'''の１種です。
 . {{attachment:chain42.png}}
行 8: 行 9:
Javaで記述してみましょう。 線形リストの特徴
 1. 前から順にすべてのデータをたどることができます。
 1. データの追加や削除が配列と比べて楽に行えます。
行 10: 行 14:
このようなインスタンスを使います。
 . {{attachment:list1.png}}
 . １つ目の変数には値を保存します
 . ２つ目の変数には次の項目へのリンクを記入します。
３つのインスタンスをつないだ例を示します。
 . {{attachment:list2.png}}
 . これより先につながっていないことを、'''null'''という値で表します。		 === 線形リストの修正 ===
次のような処理を考えましょう。
行 18: 行 17:
'''null'''はシステムで用意されている'''定数'''です。
 * 参照型の変数はnullで初期化されます。
 * nullはどこも参照していないことを表します。
----
=== 追加 ===
途中にデータを追加するには、リンク２箇所を修正すればよい。
 . {{attachment:list3.png}}
----
=== 削除 ===
途中のデータを削除するには、リンク１箇所を修正すればよい。
 . {{attachment:list4.png}}
削除されたデータからのリンクが残っていますが、リストをたどってこのデータにたどり着くことはできません。
----
=== サンプル ===
値としてItemクラスのインスタンスを使った例です。

クラス名は List1 としました。
 . {{attachment:list1.png}}
属性（インスタンス変数）の型は
 . 値にはItemクラスのインスタンスが入るので Item
 . リンクには次のデータを記憶するためのオブジェクトすなわち List1のインスタンスが入りますから List1
となります。

 {{{#!java
 public class List1
 {
  Item val;
  List1 link;
  
  void dispList()
  {
   List1 x;
   
   x = this;
   while(x != null)
   {
    x.val.disp();
    x = x.link;
   }
  }
  
  public static void main(String[] args)
  {
   List1 a;
   List1 b;
   List1 c;
   
   a = new List1();
   a.val = new Food("パン", 150, 200.0, 200.0);
   b = new List1();
   a.link = b;
   b.val = new Drink("コーヒー", 120, 250);
   c = new List1();
   b.link = c;
   c.val = new Food("みかん", 100, 150.0, 200.0);
   
   a.dispList();
  }
 }
 }}}
mainメソッドでは、変数a,b,cの３つを用いて図のようなリストを作っています。
 . {{attachment:list5.png}}
最後に
 . a.dispList();
により、aに対してメソッドdispList()を行っています。

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

線形リスト

同じ形式のデータが一列に並んでおり、 前から順にたどりながら参照できる形のものを線形リストといいます。

これも線形リストの１種です。

  • chain42.png

線形リストの特徴

  1. 前から順にすべてのデータをたどることができます。
  2. データの追加や削除が配列と比べて楽に行えます。

線形リストの修正

次のような処理を考えましょう。

  • リストの先頭に追加
  • リストの途中に追加
  • リストの最後に追加
  • リストの先頭を削除
  • リストの途中を削除
  • リストの最後を削除

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