連結リスト

リストとは、相互の要素を参照で繋いだデータ構造です。それぞれの要素が、次の要素への参照をもつ事で、要素を繋いで行きます。ちょうど「リンク」でホームページを辿って行くような感覚で、要素を辿って行くわけですね。このようなリストは連結リストと呼ばれ、リストの中でも最も単純な構造になっています。

　　最初の要素　→　２番目の要素　→　３番目の要素　・・・

　リストには、要素の追加・削除を要素間の参照の変更のみで実現できる（配列の場合は、追加・削除のたびに一つずらしたりつめたりしてそこから後方の要素を並べ替える処理が必要）上に、要素の数を自由に増やして行けるという利点があります。

連結リストの構造

　連結リストは、要素の内容、つまりデータと次の要素への参照で構成されます。Javaでリストを作る時には、以下のようなクラスを作ると良いでしょう。

  class slist { // 連結リストクラス

      int data; // データ
      slist next; // 次のリストへの参照

      slist() { // コンストラクタ

          data=0;
          next=null;

      }

  }

　リストを作る時には、まず最初の要素を入れるslist型変数を用意して、後はメンバ変数nextに次の要素を入れて行きます。要素同士は参照でリンクされるので、各要素に変数を割り当てる必要はありません。先頭の要素のみを変数で参照し、後はその要素からの参照（リンク）で各要素を辿って行きます。

  slist lstart=new slist(); // 最初の要素を生成

  lstart.next=new slist();  // 次の要素を生成

　連続して要素を作成しながらリストを繋ぐ時は、まず繋ごうとする要素を示す変数を作成し、nextに要素を作成します。後は、作成した要素を変数に入れ同じ事を繰り返してください。

  llist sl=lstart;

  for (int i=0;i<5;i++) { // ５個の要素を追加

      sl.next=new slist(); // 要素を追加
      sl=sl.next; // 追加した要素をslに代入

  }

　リストの要素を連続して参照する時は、slist型変数を用意してそこに要素を入れて行けば良いでしょう。最後の要素はnextがnullなので、すべての要素を見るなら最初の要素からnextがnullの要素までを見れば良いわけです。

  slist sl=lstart; // これでslは最初の要素を示す

  sl=sl.next; // slは２番目の要素を示す
  sl=sl.next; // slは３番目の要素を示す
  sl=sl.next; // slは４番目の要素を示す
　　　　　　　　　・
　　　　　　　　　・

リストへの追加と削除

　リストへの追加は、追加する要素の前の要素のリンクを追加する要素に付け変えます。後は、元のリンクを追加した要素のリンクに入れればリストの中に要素が追加された事になるわけです。
　例えば、１→２→３というリストで、１と２の間に４という要素を入れるなら、１の後に４をいれて４の後に２を繋げば１→４→２→３というリストを作る事が出来ます。

　ただし、最初に追加する時にはリンクの一方向がないわけですから、多少異なる処理が必要です。具体的には、リンクする前の要素がないので、追加する要素に先頭へのリンクをつける処理になります。最後の場合は、nullになっている最後の要素のリンクを追加する要素へのリンクに変更するので上の場合と同じ処理ですね。
　下のプログラム例は、引数で指定した要素の後に要素を追加する関数です（「後に」追加するので、追加する要素が最初になる事はない）。

  private void insert(slist ss) { // ssの後ろに要素を追加

      slist sw;

      sw=ss.next; // 追加先の次の要素を保存
      ss.next=new slist(); // 要素を追加
      ss.next.next=sw; // 保存しておいた要素にリンク

      repaint();

  }

　リストの削除は、削除しようとする要素を「飛ばす」事で実現できます。具体的には、削除する要素の前と後の要素を削除しようとする要素を飛ばしてリンクします（最後の要素を削除する場合も、削除する要素の次はnullなので同様の処理で良い）。ただし、最初の要素を削除する場合は最初の要素を削除する要素の次の要素とするだけです。

  private void delete(slist ss) { // ssを削除

      slist sl=lstart;

      if (lstart.next==null) // 要素が一つしかなければ中止
          return;

      if (ss==lstart) // 最初の要素
          lstart=lstart.next;
      else {

          while (sl.next!=ss) // 前の要素を取得
              sl=sl.next;

          sl.next=ss.next;

      }

  }

プログラム

　今回のアプレットは、表示されたリストに要素を追加・削除する例です。画面上にリストの状態が表示されているので（一番左が最初の要素）、ボタンとして表示されている要素をクリックして追加・削除してください。Deleteがチェックされているとクリックした要素の削除、チェックしていなければクリックした要素の後ろへの追加となります（ボタンの数字は、その要素が何番目に作成されたかを表す）。ただし、リストの最大要素数は６です。

プログラムソース表示

ソース中で複数のクラスを定義しているので、ご注意ください。