ArrayList 와 LinkedList 차이점

ArrayList 

 

1. 기본적으로 배열을 사용

 

2. 일반 배열과는 다르게 크기를 따로 지정을 안하고 동적으로 값을 삽입 및 삭제 가능함.

 

3. index를 가지고 있다.

 

조회 시

 

1. ArrayList는 index를 가지고 있음으로 index로 데이터를 찾아올 수 있다.

 

 

데이터 삽입 및 삭제 시

 

1. 데이터를 삽입 혹은 삭제를 할 때 ArrayList는 위치를 맞춰주어야 한다.

 

예를들어  arrayList 배열에 "안녕" 이라는 데이터를 삭제 했다면, 나머지 뒤의 3개를 앞으로 한칸씩 이동해야한다.

 

배열에 담긴 데이터가 많아질수록 데이터 삽입 및 삭제 시 작업량이 늘어남으로 성능적인 측면에서 비효율적이다.

 

 

LinkedList

 

1. 내부적으로 양방향의 연결 리스트로 구성되어 있다.

 

2. 참조하려는 원소에 따라 정방향 또는 역순으로 조회가 가능하다.

(배열의 단점을 보완하기 위해 나온걸로 알고있음)

 

조회 시

 

1. 순차적으로 데이터를 찾기때문에 ArrayList에 비해 검색 속도가 느리다.

 

데이터 삽입 및 삭제 시

 

1. 데이터를 추가 및 삭제 시 가리키고 있는 주소값만 변경해주면 되기에 ArrayList에 비해 상당히 효율적임.

 

 

                                 출처 : http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html

위에 그림을 보면

 

조회시에는 ArrayList가 우위에 있지만,

삽입 및 삭제 시에는 LinkedList가 뛰어난 성능을 보인다.

 

데이터가 얼마 없는 경우에는 별 차이가 없지만,

 

정적인 데이터를 활용하면서 조회가 빈번이 일어날 경우 ArrayList가 유리하며,

동적으로 추가/삭제 가 많은 경우 LinkedList를 사용하는 것이 좋다.

 

 

 

ArrayList 와 LinkedList 성능 차이 비교

 

 

 public static void main(String[] args) {
        ArrayList arrayList = new ArrayList(2000000);
        LinkedList linkedList = new LinkedList();


        System.out.println("======순차적으로 추가======");
        System.out.println("ArrayList = " + addF(arrayList));
        System.out.println("LinkedList = " + addF(linkedList));
        System.out.println("\n======중간에 추가======");
        System.out.println("ArrayList = " + addM(arrayList));
        System.out.println("LinkedList = " + addM(linkedList));
        System.out.println("\n======중간에 삭제======");
        System.out.println("ArrayList = " + removeM(arrayList));
        System.out.println("LinkedList = " + removeM(linkedList));
        System.out.println("\n======순차적으로 삭제======");
        System.out.println("ArrayList = " + removeF(arrayList));
        System.out.println("LinkedList = " + removeF(linkedList));

    }

    public static long addF(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(i + "");
        }
        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long addM(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list.add(500, "X");
        }
        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long removeF(List list) {
        long start = System.currentTimeMillis();
        for (int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }
        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long removeM(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list.remove(i);
        }
        long end = System.currentTimeMillis();
        return end - start;
    }

 

 

 

결론

 

1. 순차적으로 삽입 및 삭제 하는 경우       ArrayList > LinkedList

 (데이터를 쭉 밀고 다시 추가를 하면 요소들의 재배치가 필요없기에 ArrayList의 처리 속도가 빠름)

 

 

 

2. 중간 데이터(비 순차적)를 삽입 및 삭제 하는 경우 LinkedList > ArrayList

 (LinkedList는 각 노드간 연결만 변경해주면 되기에 처리 속도가 빠름)

 

 

 

상황에 맡게 ArrayList 와 LinkedList 를 적절히 섞어 써주면 성능적인 측면에 대해서 효율적으로 코드를 짤수 있다.

 

 

끝