자바의 자료구조 Collection Framework (2) - List

Java의 Collection 구현체 중 List 인터페이스는 배열과 비슷한 형태의 자료구조이며 다양한 메소드들을 가지고 있다. List인터페이스를 구현한 자료형 중에는 대표적으로 ArrayList와 LinkedList가 존재하는데 오늘은 중점적으로 이 두 가지 List구현체들을 알아보고자 한다.

참고할 점은 두 구현체 모두 내부적으로 구현만 다를뿐 개발자가 실제 사용하는 메소드 사용법에는 큰 차이가 없다. 그러나 내부적으로 다른 구현으로 인해 각 상황마다 성능 차이가 생길 수 있기 때문에 두 구현체 중 어느 것을 선택할 지는 전적으로 개발자의 몫이다.

1. ArrayList

ArrayList는 내부적으로 배열을 이용해 구현되어있다. 일반 배열과 동일하게 연속된 메모리 공간을 사용한다. 일반 배열과의 차이점은 배열의 크기는 고정이지만 ArrayList는 데이터의 추가/삭제 등으로 인해 가변적으로 변한다. 추가/삭제 등의 작업을 위해선 임시 배열을 생성해 데이터를 복사하는 방법으로 구현되어있다. 배열을 생성하고 데이터를 매번 복사하는 작업을 거쳐야하기 때문에 최악의 경우 O(N)의 성능을 가지게된다. 하지만 데이터 검색 속도는 매우 빠른 편인데 인덱스 기반의 자료구조이기 때문에 배열과 같이 인덱스를 통해 자료를 가져오게 되면 O(1)의 시간 복잡도를 가지게 된다.

2. LinkedList

자바 Collection의 LinkedList는 내부적으로 이중 연결 리스트(Doubly Linked List)로 구현되어 있어 양방향으로 참조할 수 있게 구현되어 있다. LinkedList는 ArrayList에 비해 삽입/삭제가 간단한 편이다. LinkedList가 이중 연결 리스트로 구현되어 있어 노드간 참조 포인터만 변경하면 삽입/삭제 작업이 마무리 된다. 그렇기 때문에 시간 복잡도는 O(1)을 가지게 된다. 하지만 검색 시에는 모든 요소를 탐색해야 하기 때문에 최악의 경우 O(N)의 시간 복잡도를 가지게 된다.

3. 정리

앞서 말했듯 ArrayList와 LinkedList는 구현된 메소드들의 사용법은 같다. 그러나 내부적인 구현의 차이 때문에 담게 될 데이터의 특성에 따라 옳은 선택을 할 필요가 있다. 일반적으로 대량의 삽입/삭제가 빈번하게 일어난다면 LinkedList를 이용하면 될 것이고 삽입/삭제가 빈번하지 않지만 검색 성능에 더 우위를 요하는 데이터라면 ArrayList를 사용하면 될 것이다. 

References

Oracle Java SE8 공식 Document

https://www.holaxprogramming.com/2014/02/12/java-list-interface/

http://tcpschool.com/java/java_collectionFramework_list