線形リスト

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

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

線形リストの特徴

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

線形リストの修正

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

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

つぎのことが分かっています。

追加する場合

• 追加したい位置の直前にあるオブジェクトを参照できれば簡単に行える。

削除する場合

• 取り除きたい位置の直前にあるオブジェクトを参照できれば簡単に行える。

つながっているものすべてを表示するメソッド

これは以前に作成したものです。

•    1 void showAll()
     2 {
     3         Chain c;
     4 
     5         c = this;
     6         System.out.println("(");
     7         while (c != null)
     8         {
     9                 c.show();
    10                 c = c.next;
    11         }
    12         System.out.println(")");
    13 }
  

これをもとにして、次の２つのメソッドを作成します。

つながっている個数を返すメソッド

•    1 int length()
     2 {
     3         Chain c;
     4         int cnt;
     5 
     6         c = this;
     7         cnt = 0;
     8         while (c != null)
     9         {
    10                 cnt++;
    11                 c = c.next;
    12         }
    13         return cnt;
    14 }
  

指定された位置にあるオブジェクトを返すメソッド

•    1 Chain nth(int n)
     2 {
     3         Chain c;
     4         int cnt;
     5 
     6         c = this;
     7         cnt = 0;
     8         while (c != null && cnt < n)
     9         {
    10                 c = c.next;
    11         }
    12         return c;
    13 }