자바 컬렉션 프레임워크 - List

컬렉션 프레임워크(Collections Framework)란

데이터 군을 저장하는 클래스들을 표준화한 설계를 뜻한다. 컬렉션은 다수의 데이터, 즉 데이터 그룹을 프레임워크는 표준화된 프로그래밍 방식을 의미한다.

JDK1.2 이전까지는 Vector, Hashtable, Properties와 같은 컬렉션 클래스, 다수의 데이터를 저장할 수 있는 클래스들을 서로 다른 각자의 방식으로 처리해야 했으나 JDK1.2부터 컬렉션 프레임워크가 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다.

컬렉션 프레임워크의 핵심 인터페이스

컬렉션 프레임워크에서 컬렉션데이터 그룹을 크게 3가지로 타입으로 나눴다.

인터페이스 List와 Set을 구현한 컬렉션 클래스들은 서로 많은 공통부분이 있어서, 공통된 부분을 다시 뽑아 Collection인터페이스를 정의할 수 있었지만 Map인터페이스는 이들과는 전혀 다른 형태로 컬렉션을 다루기 때문에 같은 상속계층도 포함되지 못했다.

List인터페이스

List인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.

ArrayList

ArrayList 생성할 때 저장할 요소의 개수를 고려해서 실제 저장할 개수보다 약간 여유 있는 크기로 하는 것이 좋다. 생성할 때 지정한 크기보다 더 많은 객체를 저장하면 자동적으로 크기가 늘어나기는 하지만 이 과정에서 처리시간이 많이 소요되기 때문이다.

• 데이터의 저장순서가 유지
• 데이터 중복을 허용
• 데이터 조회 시 성능이 뛰어남

LinkedList

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근시간, access time)이 가장 빠르다는 장점을 가지고 있지만 아래와 같은 단점도 가지고 있다.

1. 크기를 변경할 수 없다.
   • 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다.
   • 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
   • 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
   • 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

ArrayList와 LinkedList의 장단점

import java.util.*;

public class ArrayListLinkedListTest {
    public static void main(String[] args) {
        //  추가할 데이터의 개수를 고려하여 충분히 잡아야한다.
        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList : " + add1(al));
        System.out.println("LinkedList : " + add1(ll));
        System.out.println();

        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList : " + add2(al));
        System.out.println("LinkedList : " + add2(ll));
        System.out.println();

        System.out.println("= 중간에 삭제하기 =");
        System.out.println("ArrayList : " + remove2(al));
        System.out.println("LinkedList : " + remove2(ll));
        System.out.println();

        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList : " + remove1(al));
        System.out.println("LinkedList : " + remove1(ll));
    }

    public static long add1(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 add2(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 remove1(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 remove2(List list){
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10000; i++) list.remove(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
}

결과
= 순차적으로 추가하기 =
ArrayList : 109
LinkedList : 278

= 중간에 추가하기 =
ArrayList : 3614
LinkedList : 13

= 중간에 삭제하기 =
ArrayList : 2565
LinkedList : 193

= 순차적으로 삭제하기 =
ArrayList : 12
LinkedList : 36

결론1 - 순차적으로 추가 / 삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
단순히 저장하는 시간만을 비교할 수 있도록 하기 위해서 ArrayList를 생성할 때는 저장할 데이터의 개수만큼 충분한 초기용량을 확보해서, 저장공간이 부족해서 새로운 ArrayList를 생성해야하는 상황이 일어나지 않도록 했다. 만일 ArrayList의 크기가 부족하게 되면 새로운 크기의 ArrayList를 생성하고 데이터를 복사하는 일이 발생하게 되므로 순차적으로 데이터를 추가해도 ArrayList보다 LinkedList가 더 빠를 수 있다.

순차적으로 삭제한다는 것은 마지막 데이터부터 역순으로 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다. 단지 마지막 요소의 값을 null로만 바꾸면 되기 때문이다.

결론2 - 중간 데이터를 추가 / 삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다.

예제에서는 ArrayList와 LinkedList의 차이를 비교하기 위해 데이터의 개수를 크게 잡았는데 사실 데이터의 개수가 그리 크지 않다면 어느 것을 사용해도 큰 차이가 나지는 않는다. 그래도 ArrayList와 LinkedList의 장단점을 잘 이해하고 상황에 따라 적합한 것을 선택해서 사용하는 것이 좋다.

ArrayList와 LinkedList 접근시간 차이

import java.util.*;

public class ArrayListLinkedListTest2 {
    public static void main(String[] args) {
        ArrayList al = new ArrayList(1000000);
        LinkedList ll = new LinkedList();
        add(al);
        add(ll);

        System.out.println("= 접근시간 테스트 =");
        System.out.println("ArrayList : " + access(al));
        System.out.println("LinkedList : " + access(ll));
    }

    public static void add(List list){
        for(int i = 0; i < 100000; i++) list.add(i+"");
    }

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

결과

= 접근시간 테스트 =
ArrayList : 4
LinkedList : 9661

배열의 경우 만일 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식을 계산함으로써 해결된다.

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

아래와 같이 Object배열이 선언되었을 때 arr[2]에 저장된 값을 읽으려 한다면 n은 2, 모든 참조형 변수의 크기는 4byte이고 생성된 배열의 주소는 0x100이므로 3번째 데이터가 저장되어 있는 주소는 0x100 + 2 * 4 = 0x108이 된다.

Object[] arr = new Object[5];

배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 이처럼 간단한 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만, LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다.

그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어 오는 시간, 즉 접근시간(access time)이 길어진다는 단점이 있다.

다루고자 하는 데이터의 개수가 변하지 않는 경우라면, ArrayList가 적합할 것으로 보이고, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나을 것으로 보인다.

두 클래스의 장점을 이용해서 두 클래스를 조합해서 사용하는 방법도 생각해 볼 수 있다. 처음에 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용한 다음, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있을 것이다.

ArrayList al = new ArrayList(1000000);
for(int i = 0; i < 1000000; i++) al.add(i+"");

LinkedList ll = new LinkedList(al);
for(int i = 0; i < 1000; i++) ll.add(500, "X");

컬렉션 프레임웍에 속한 대부분의 컬렉션들은 이처럼 서로 변환이 가능한 생성자를 제공하므로 이를 이용하면 간단히 다른 컬렉션 클래스로 데이터를 옮길 수 있다.

※ 참고 문헌
남궁성, 『Java의 정석 3nd Edition』, 도우출판(2016) 책으로 공부하고 정리한 내용 입니다.