線形リスト

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

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

線形リストの特徴

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 }
  

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

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

つながっている個数を返すメソッドlengthを作ります。

返す値はintです。次の修正が必要。

• メソッドの型宣言
• return

処理内容

• showAllではオブジェクト１つずつに対してshowを行っていたので、 ここでカウントを行えばよい。

変数の宣言と初期化を加え、不要な部分を除けば完成。

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

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

つながっている個数を返すメソッドnthを作ります。

• 引数として位置を表す数値(int)を取ります。
• 返す値はChainです。

次の修正が必要。

• メソッドの型宣言
• return

処理内容

• カウントを行い指定の箇所まできたら、そのとき指しているオブジェクトを返せばよい。

条件はwhileの条件に追加。

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

• 

メソッド内でメソッドを使う

メソッド内でメソッドを呼び出すこともできます。

このメソッドは次回使うので追加しておくこと。

•    1 void showContent()
     2 {
     3         next.showAll();
     4 }
  

線形リストを修正する

上で作成したメソッドを使うと、リストの修正が簡単にできます。

例

• aが参照しているリストの３番目のオブジェクトを削除する。

  Chain a, temp;
  ...
  temp = a.nth(2);
  temp.next = temp.next.next;