Java List관련 클래스의 비교

List Class

Java Collection Framework 중 List Class에 대해서 이야기해 보려고 합니다.
List는 기본적으로 중복을 허용하며 순서가 있는 데이터의 집합으로 List interface를 상속받아 사용 중인 아래 세 가지 클래스를 알아보려 합니다.

• 종류
  • ArrayList: 배열과 다르게 생성 시, 크기를 지정해주지 않아도 되는 가변적 크기를 가집니다. 크기를 지정하지 않으면 capacity=10의 크기로 생성됩니다. 인덱스 기반으로 동작하기 때문에 검색에 유리하며 삽입 삭제는 임시 배열을 만들어서 복사하는 과정이 존재합니다.
  • LinkedList: 이중연결리스트 구조이며, 삽입 삭제 시 노드의 각 참조만 변경되므로 ArrayList보다 빠른 성능을 가집니다. 그러나 검색은 처음 노드부터 하나씩 순회하므로 ArrayList보다 성능이 느립니다.
  • Vector: ArrayList 구조와 동일하지만 동기화(synchronized)를 지원하는 것이 특징입니다.

ArrayList, LinkedList 동기화 처리는 개발자가 동기화 처리를 적용해주어야 한다고 명시되어 있습니다.

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, must be synchronized externally

성능 비교

ArrayList, LinkedList 클래스를 비교해봅시다. 상황에 따라 다르게 사용되는 자료구조로 성능 테스트를 한다는 것이 큰 의미가 없는 것 같습니다. 참고만 하시면 될 것 같습니다.
ArrayList와 LinkedList를 데이터가 중복되는지 그리고 삽입과 삭제, 검색 테스트를 진행했습니다. 아래는 성능 테스트에 사용한 코드입니다. 성능 테스트 깃헙 링크

	private static void performanceTest() {
		int size = 300000;
//		List<Integer> arrayList = new ArrayList<>(size);
		List<Integer> arrayList = new ArrayList<>();
		List<Integer> linkedList = new LinkedList<>();

		StopWatch arrayStopWatch = new StopWatch("add arrayList");
		arrayStopWatch.start();
		for (int i = 0; i < size; i++) {
			arrayList.add(i);
		}
		arrayStopWatch.stopAndPrint();

		StopWatch linkedListStopWatch = new StopWatch("add linkedList");
		linkedListStopWatch.start();
		for (int i = 0; i < size; i++) {
			linkedList.add(i);
		}
		linkedListStopWatch.stopAndPrint();

		System.out.println(String.format("--- search performance test[index: %s]", size / 2));
		arrayStopWatch.start();
		arrayList.get(size / 2);
		arrayList.add(0, 1);
		arrayStopWatch.stopAndPrint();

		StopWatch linkedListStopWatch2 = new StopWatch("search linkedList");
		linkedListStopWatch2.start();
		linkedList.get(size / 2);
		linkedList.add(0, 1);
		linkedListStopWatch2.stopAndPrint();

		System.out.println(String.format("--- remove performance test[data size: %s]", size));
		StopWatch arrayStopWatch2 = new StopWatch("remove arrayList");
		arrayStopWatch2.start();

		removeAll(arrayList, arrayList.iterator());
		arrayStopWatch2.stopAndPrint();

		StopWatch linkedListStopWatch3 = new StopWatch("remove linkedList");
		linkedListStopWatch3.start();

		removeAll(linkedList, linkedList.iterator());
		linkedListStopWatch3.stopAndPrint();
	}

테스트 결과

{1, 1, 2, 2, 3, 3} 배열을 삽입해보았는데, ArrayList, LinkedList 모두 중복을 허용합니다.

삽입, 검색, 삭제 테스트는 30만개의 정수를 사용했습니다. 아래 그림은 삽입에 대한 테스트 결과입니다. ArrayList는 삽입할 때, 가득찬 상태에서 삽입이 들어오면 배열 크기를 늘리며 복사 과정이 존재하기 때문에 LinkedList보다 느립니다.

ArrayList 생성 시, 배열의 크기를 명시적으로 지정해주면 어떻게 될까요? 배열 크기 보정을 해주지 않아도 되기에 LinkedList와 비슷한 성능이 나옵니다. 아래는 List<Integer> arrayList = new ArrayList(size); 선언 후 결과입니다.

검색은 이중연결리스트인 LinkedList는 처음 노드부터 순회하면서 데이터를 조회한다고 했습니다. ArrayList의 인덱싱이 빠른 것을 확인 할 수 있습니다.

ArrayList의 삭제는 임시 배열을 만든 뒤, 복사 과정이 존재하므로 LinkedList보다 성능이 떨어지는 것을 볼 수 있습니다.

결론

공통적으로 중복이 필요하고 순서가 있는 집합에 사용합니다. ArrayList, LinkedList를 사용하기 전에 현재 상황이 데이터의 삽입. 삭제가 자주 일어나는가? 데이터의 조회는 자주 일어나지만 삽입 및 삭제는 빈도가 적다등 여러 상황을 고려하여 결정을 해야합니다. Vector는 동기화를 위해 synchronized 메소드 방식으로 사용하고 있어 ArrayList, LinkedList를 사용하면서 필요에 따라 synchronized 블락 방식으로 사용하는 것은 어떨까 싶습니다.