자바 선형 리스트 구현과 개념 (Linear List)

선형 리스트는 자료구조의 기본이 되는 구조이다.

배열과 같이 연속되는 기억장소에 저장한다.

연접리스트(Dense List) 축자 구조(Sequential Structure) 라고도 한다.

자료의 개수가 n개일 때 자료 추가시 이동 횟수는 n+1/2 이고, 삭제시에는 n-1/2 이다,.

가장 간단하고, 접근 속도가 빠르다. 기억장소를 연속적으로 배정받기에 밀도가 1로서 이용효율은 가장 좋다.

하지만 자료의 양이 거대해질 때, 자료의 이동 횟수가 기하급수적으로 늘어나는 단점이 있다.

그림으로 보자

그림판 편집이라 볼품없지만

가장 왼쪽에서

5와 10 사이에 20을 추가하면

뒤의 숫자들이 한칸 씩 밀린다.

두번째 블록에서는 값을 빼는데 중간에 값을 빼면

뒤의 값들이 한 칸 씩 당겨진다.

이를 자바 코드로 구현해 봤다.

먼저 UI 클래스

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;
            }
        }
    }



}

로직 클래스

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){         // 숫자 추가, add: 추가할 숫자, 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번째가 0 이면 멈추어야 한다.
                        i =- 1; // 나중에 +1 을 할 것이니 -1이 되어도 무방하다.
                        break;
                    }
                } // i 처리. i는 값이 들어가있는 리스트의 마지막 번호이다.
                myList[i+1] = add; // i까지 값이 들어있으니 i+1 에 값을 넣는다.
                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("리스트 꽉 차거나, 오버플로우거나, 추가할 리스트 번호가 음수값입니다.");
        }
    }

    public void delete(int ordinal){         // 숫자 지움, 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("삭제 범위가 음수이거나, 빈공간 입니다.");
        }
    }

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

}

원래 메시지도 돌려주는 게 좋지만.. 테스트니 그냥 sysout으로 뽑았다.

int 배열 디폴트 값이 0이라 0이면 그냥 빈공간으로 봤다.

내가 구현하려고 햇던 로직은 이렇다

삽입

1. 값을 넣을 공간이 빈공간이라면, 그 공간의 앞이 빈공간인지 확인 한 후 이동한다. 반복 -> 값이 있으면 그 자리+1에 값을 넣는다.

2. 값을 넣을 공간에 값이 있으면 맨 뒤에서부터 차례대로 그 공간까지 한 공간 씩 뒤로 밀어낸다.

제거

1. 지울 공간이 빈 공간이라면 작업하지 않는다

2. 지울 공간에 값이 있으면 바로 뒷공간부터 끝까지 한 공간씩 앞으로 당긴다.

남들은 쉽게한다는데.. 생각보다 오래걸렸다.

혹시나 나중에 잊어버릴까 주석을 자세하게 달았다.

로직은 나름 잘 된거같은데 효율성 측면에서

더 좋은 코드가 있을 거 같다