線形リスト：データ構造

1. 線形リスト

   複数のデータ（セル）を接続して、任意の個数のデータを記録するデータ構造です。個数が不定のデータを記録する基本的なデータ構造です。ここでは、Javaでリスト構造を表現する方法を紹介します。
   　線形リストは要素の数が多くなると、検索やデータの追加に時間がかかります。この問題は、ハッシュや木構造を用いて解決します。
   
   

2. データ構造

   1. セルクラス

      Javaでは、Cの構造体もクラスで定義します。ここでは、線形リストの単位セルを定義します。整数keyをキーとして、文字列dataを記録します。nextで次のCellクラスを指示します。コンストラクタで、keyとdataを初期設定できます。
      
      

      public class Cell
      {
      　int key;
      　String data;
      　Cell next;
      
      Cell(int pkey,String pdata){
      　key=pkey;
      　data=pdata;
      　}
      }//Cell

      
      

   2. 手法

      1. 挿入
         keyとdataの値を記録し、topに始まるリストの先頭に接続します。skeyはキーの値を記録した文字列、sdataはdataに記録する文字列です。ここでの目的は新しいデータを作成し、リストtopの先頭につなぐことです。最初に、new　でcellを作成し、コンストラクタでcｅｌｌのdataを設定します。
         　cell.next=top;
         で、nextにtopに接続するリストを記録します。
         　次に、topの値をcelにすれば、cellをリストtopの先頭につなぐことが出来ます。Integer.parseInt(skey)はskeyを数値に変換する処理です。cellをnewで動的に確保していますが、言語Cとは異なり、cellのメンバーであるnextの参照はcell.nextです。Javaの場合、すべて、newで確保しますから、C言語のように　cell.next　とcell->next（(*cell).next）　の区別は不要です。
         

         Cell cell=new Cell(Integer.parseInt(skey),sdata);
         　cell.next=top;
         　top=cell;

         
         
      2. 検索
         keyの値を元にリストを検索し、同じkeyの値をもつ先頭のセルのdataの値を表示します。検索したい値をfind.keyに記録しておきます。検索したい値をikeyとします、
         まず、findをtopとして検索を始めます。find.keyがikeyとなるまで順にセルを調べます。find.nextがnull（空）になったら終了します。
         

         Cell find=top;
         while(find.key!=ikey){
         　if (find.next==null) {
         　　textField2.setText("not found");//見つからない
         　　return ;
         　}
         　else
         　find=find.next;//次のセルを調べる
         }
         textField2.setText(find.data);//見つかった

         
         
      3. 削除
         指定したキーのセルを削除します。各自、考えてください。
         
         

3. プロジェクト

   
   
   1. デザイン
      keyとdataを記録するtextfFeldを用意します。insertとserchボタンを用意します。
      
      
   2. 変数
      top：リストの先頭を記録します。
      
      
   3. メソッド
      1. 挿入
         keyとdataの値をリストの先頭に接続します。dispList()で、結果を表示します。
         

           void insert_actionPerformed(ActionEvent e) {
             //挿入
             String skey=textField1.getText();
             String sdata=textField2.getText();
             Cell cell=new Cell(Integer.parseInt(skey),sdata);
             cell.next=top.next;
             top.next=cell;
             dispList();
           }

      2. 検索
         文字ボックスkeyの値をもつcellをtopリストからさがし、あれば、その値を文字ボックスdataに表示します。ない場合、not found　を表示します。
         

           void serch_actionPerformed(ActionEvent e) {
             //検索
             Cell find=top.next;
             String skey=textField1.getText();
             int ikey=Integer.parseInt(skey);
             if (find ==null) return;
             while(find.key!=ikey){
               if (find.next==null) {
                 textField2.setText("not found");
                 return ;
                 }
               else
                find=find.next;
             }
             textField2.setText(find.data);
           }

         
         
      3. 削除
         指定されたキーをもつセルをリストから削除します。同じキーがない場合、何もしません。dispList()で、結果を表示します。

      4.   void delete_actionPerformed(ActionEvent e) {
             String skey=textField1.getText();
             delete(Integer.parseInt(skey));
           }
         
          void delete(int ikey){
            Cell current,prev;
            prev=top;
            current=top.next;
            if(current==null) return;
            while(current.key !=ikey){
              if(current.next==null) return;
              else {
                prev=current;
                current=current.next;
              }
            }
            prev.next=current.next;
            dispList();
          }
         

      5. 表示
         リストの内容をtextAreaに表示します。

          void dispList(){
            Cell find=top.next;
            String str="";
            while(find != null){
             str += Integer.toString(find.key)+":"+find.data+"\n";
              find=find.next;
            }
            textArea1.setText(str);
          }

         
         

4. 実行

   左にキーとなる数字、右に文字列を入力し、insertボタンを押すとリストに記録します。キーの数字を入力し、serchボタンを押すと、キーの値で検索し、対応する文字列を表示します。見つからない場合、notfoundを表示します。deleteボタンで現在表示しているデータを削除します。
   
   　　　
   
   

5. ダウンロード

   このプロジェクトをダウンロードできます。
   次の行をクリックして、list.exeファイルを適当なフォルダに保存します。
   ダウンロード開始
   このファイルは自己解凍型の圧縮ファイルです。このファイルを実行すると指定したフォルダに必要なファイルが生成されます。
   
   

6. Cのプログラム

   同様なリスト処理のC言語版がこちらにあります。C言語版では、リスト操作を図解していますから、Javaプログラムの動作が理解しにくい人は、参照してください。