Javaプログラミング

リスト（連結リスト:linked list）は配列同様、複数のデータを扱うデータ構造で以下の性質を持つ。
• 連結リストの要素はノード（節：node）とも呼ばれる
• 隣接する連続したノードはリンク情報（ポインタ：pointer）で接続される
• 連結リストの終端ノードは接続なしを示すリンク情報（null）をもつ
• 可変長でメモリが許す限り、必要な大きさに設定できる
• リンク情報が必要であることを除けば、ノード単位で管理できるのでメモリ空間を効率的に利用できる
• 各ノードが独立したデータ構造なので、追加、挿入、削除の操作がしやすい
• リスト構造（単一連結リスト）

• ノード


          class ListNode{
            int data;
            ListNode next;
          }
  			

• リストの操作
リスト構造に対する操作は以下の3つである。
• 横断（traverse）


            ListNode p;
            ListNode n1=new ListNode();
            ListNode n2=new ListNode();
            ListNode n3=new ListNode();
        
            n1.data=3;
            n1.next=n2;
            n2.data=4;
            n2.next=n3;
            n3.data=2;
            n3.next=null;
        
            //ポインタをn1にセット
            p=n1;
        
            //横断
            while(p!=null){
              System.out.println(p.data);
              p=p.next;
            }
          

• 挿入（insert）


            ListNode p;
            ListNode n1=new ListNode();
            ListNode n2=new ListNode();
            ListNode n3=new ListNode();
        
            n1.data=3;
            n1.next=n2;
            n2.data=2;
            n2.next=null;
        
            //ポインタをn1にセット
            p=n1;
        
            //横断
            while(p!=null){
              System.out.println(p.data);
              p=p.next;
            }
            System.out.println();
        
            n3.data=4;
            n3.next=null;

            //挿入
            n1.next=n3;
            n3.next=n2;
        
            //ポインタをn1にセット
            p=n1;
        
            //横断
            while(p!=null){
              System.out.println(p.data);
              p=p.next;
            }
          

• 削除（delete）


            ListNode p;
            ListNode n1=new ListNode();
            ListNode n2=new ListNode();
            ListNode n3=new ListNode();
        
            n1.data=3;
            n1.next=n2;
            n2.data=2;
            n2.next=n3;
            n3.data=4;
            n3.next=null;
        
            //ポインタをn1にセット
            p=n1;
        
            //横断
            while(p!=null){
              System.out.println(p.data);
              p=p.next;
            }
            System.out.println();
        
            //削除
            n1.next=n3;
        
        
            //ポインタをn1にセット
            p=n1;
        
            //横断
            while(p!=null){
              System.out.println(p.data);
              p=p.next;
            }
          

          class SingleListNode{
            int data;
            ListNode next;
          }
        

• リストの長さの取得

        public int length() {
          SingleListNode p=this.head;
          int length=0;
          while(p!=null) {
            length++;
            p=p.next;
          }
          return length;
        }
      

• 要素の挿入

        public void insert(int pos,SingleListNode node) {
          if(pos==0) {
            node.next=this.head;
            this.head=node;
          }else {
            int i=1;
            SingleListNode p=this.head;
            while(node!=null && i<pos) {
              i++;
              p=p.next;
            }
            node.next=p.next;
            p.next=node;
          }
        }
      

• 要素の削除

        public void delete(int index) {
          if(this.head==null)return;
          if(index==0) {
            this.head=this.head.next;
          }else{
            int i=1;
            SingleListNode p=this.head;
            SingleListNode q=this.head;
            while(p!=null && i<index) {
              i++;
              p=p.next;
              q=p;
              if(p==null) {
                return;
              }else {
                q=p.next;
                p.next=q.next;
              }
            }
          }
        }
      

• リスト全体の削除

        public void deleteAll() {
          this.head=null;
        }