Java - ArrayList, LinkedList, Vector 차이

지난 포스팅에서 Array는 읽기는 좋지만 추가, 삭제 사이즈를 변경하는 연산이 상대적으로 비용이 비싸다는 것을 확인했다. 이런 단점을 보완하기 위해서 자바에서는 ArrayList, Vector, LinkedList라는 자료구조를 제공한다. 3개의 자료구조는 모두 List 인터페이스를 implement한 구현체이다. 겉으로 보기에는 List가 모두 같아보인다. 또 주로 사용하는 데이터구조는 ArrayList가 아닐까 싶다. 실무에서 사용하는 비중으로는 ArrayList 95%, LinkedList 5% 정도라고 생각된다. 이제 각각의 자료 구조의 특징에 대해서 알아보도록하자

 

ArrayList

가장 많이 쓰이는 자료구조이다. ArrayList는 이름에서도 알 수 있듯이 Array와 List의 장점만을 짬뽕시켜서 만들어 놓은 자료구조이다. 원래 List에는 index가 없어서 자료를 찾기 위해서는 Array보다 오랜 시간이 걸린다. 하지만 ArrayList는 index가 있어서 조회도 빠르게 할 수 있다. ArrayList는 크기를 자동으로 조절해주기 때문에 메모리 낭비를 막을 수 있다. ArrayList는 삽입, 삭제 연산은 다른 자료구조들에 비해서 성능이 많이 떨어지는 편이다. 특히나 중간에 삽입하게 되면 기존에 있던 데이터들을 한칸씩 미루는 연산이 필요하기 때문에 상당히 성능이 떨어질 수가 있다. 고로 삽입, 삭제가 많은 경우에는 다른 자료구조를 쓰는 것이 좋다.

 

LinkedList

LinkedList는 대학교때 배운 그 LinkedList와 같다고 생각하면 되는데 양뱡향으로 Link를 가지고 있다. 그렇기 때문에 삽입에 있어서 n(1)의 complexity를 가진다. 원소를 새로 추가하고 link만 앞뒤로 연결해주면 되기 때문이다. 삭제에 있어서도 마찬가지로 원소를 제거하고 앞 뒤 link를 수정해주면 되기 때문에 빠르다. 반면에 조회에서는 index가 없기 때문에 처음부터 link를 타고 원소를 찾아가야 해서 다른 자료구조에 비해 성능이 떨어진다. 마찬가지로 수정도 조회처럼 찾아가야하기 때문에 성능이 떨어진다. 고로 LinkedList는 삽입, 삭제는 많고 조회는 적은 상황에 사용하면 좋다.

 

Vector

Vector는 거의 쓰지 않는 자료구조라고 보면 된다. Java 1에서부터 있었던 자료구조인데 ArrayList와 거의 동일한 기능을 가지고 있는데 한 가지 큰 차이점이 있다면 동기화를 한다는 점이다. 동기화를 해주면 공유 자원, 사용자가 여러명일 때 안정성을 보장하지만 싱글스레드 일때도 이런 작업들을 하기 때문에 성능이 떨어지는 단점이 있다. 동기화가 필요할 때도 Vector를 잘 쓰지 않고 ArrayList를 쓰게되는데 ArrayList를 사용해서 개발자가 직접 동기화를 할 수 있다.

 

 

위와 같이 List 자료구조들에 대해서 알아보았다. 알고리즘 문제처럼 데이터를 순차적으로 입력 받아서 조회해서 쓰는 문제에서는 ArrayList가 좋을 것 같다. 데이터가 많아질수록 순차적으로 삽입하는 속도의 차이보다 조회하는 속도의 차이가 훨씬 크기 때문이다.

소량의 데이터일 때는 크게 차이가 없지만 데이터가 많아질수록 차이가 심해지기 때문에 상황에 따라 맞는 자료구조를 잘 사용해보자.