Javaの線形リストの実装と概念（Linear List）

線形リストはデータ構造の一つです。

配列のように連続されている記憶場所に保存します。

連接リスト（Dense List）チュクジャ構造（Sequential Structure）とも呼ばれます。

資料の数が N存在すると仮定します。
データ追加の際に移動回数は、n+1/2であり、削除にはn-1/2になります。

最も簡単で、アクセス速度が速い構造です。
記憶する場所を連続的に割り当てられるため。密度が1で利用効率が最も高い形です。


しかし、データの量が巨大になると、データの移動回数が飛躍的に増える欠点があります。

左から

5と10の間に20を追加すると、後ろの数字が一つずつ下がります。


左は、間のデータを除いてみました。

そうすると後のデータが一つずつ上がります。


これはJavaコードで実装してみました。


まず、UI Classです。

import java.util.Scanner;

import static java.lang.Boolean.FALSE;
import static java.lang.Boolean.TRUE;

public class MyLinerList {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int lengh;
        boolean bool = TRUE;

        MyLiss myLiss = MyLiss.instance();

        System.out.println("線形リスト長さ入力");

        lengh = sc.nextInt();

        myLiss.create(lengh);

        while(bool) {
            System.out.println("1: 追加, 2: 削除, 3:リストを見る, 4: 終了");
            int num = sc.nextInt();

            switch (num) {
                case 1:
                    System.out.println("追加する数字を打って下さい。");
                    int add = sc.nextInt();
                    System.out.printf("何番目に追加しますか？(0 ~ %d)",lengh-1);
                    int ordinal = sc.nextInt();

                    myLiss.insert(add, ordinal);
                    break;
                case 2:
                    System.out.printf("何番目の数字を削除しますか？(0 ~ %d)",lengh-1);
                    int delete = sc.nextInt();

                    myLiss.delete(delete);
                    break;
                case 3:
                    myLiss.displayAll();
                    break;
                default:
                    bool = FALSE;
                    break;
            }
        }
    }



}

Logic Classです。

public class MyLiss {

    int[] myList;
    int end=0;

    public static MyLiss instance(){  
        return new MyLiss();
    }

    public int[] create(int length){  
        myList = new int[length];
        return myList;
    }

    public void insert(int add, int ordinal){         
        if(ordinal<=myList.length && end < myList.length && 0 <= ordinal){ 
            if(myList[ordinal] == 0) {            
                int i;
                for(i = ordinal; myList[i] == 0; i--){  
                    if(i == 0) { 
                        i =- 1; 
                        break;
                    }
                } 
                myList[i+1] = add; 
                end++; 
                System.out.println("end: " + end);

            } else if(myList[ordinal] != 0) {     
                int i;
                for(i = end; ordinal<=i; i--) { 
                    if(i >= myList.length - 1) {
                       
                    } else {
                        myList[i + 1] = myList[i]; 
                    }
                }
                    end++; 
                    myList[i+1] = add; 
                    System.out.println("end: " + end);
            }
        } else {
            System.out.println("List is full or memory overflow, 

                                  or value is nagative number.");
        }
    }

    public void delete(int ordinal){        
        if(ordinal >= 0 && ordinal <= end - 1) {
            int i;
            for(i=ordinal;i<=end - 1;i++){ 
                if(i >= end - 1){ 
                    break;
                } else {
                    myList[i] = myList[i + 1]; 
                }
            }
            myList[i] = 0; 
            end--; 

        } else {
            System.out.println("The delete number might be nagative number 

                                        or space might be empty.");
        }
    }

    public void displayAll(){
        System.out.println("length: " + myList.length);
        for(int i=0; i<=myList.length-1;i++){
            System.out.println(myList[i]);
        }
    }

}

テストなので自分はこいう形ですけど、元はメッセージもUIに返すのがいいです。

int配列のデフォルトデータは0のため

ゼロを空白に扱いました。