[Java] Vector vs ArrayList vs LinkedList
결론은 자바에서는 vector는 절대 쓰면 안된다그냥 ArrayList 냐 LinkedList냐 둘 중 하나인데
만약 삽입 삭제가 많은 경우이면 삽입 삭제가 O(1)인 LinkedList를 쓰고
검색 및 자료조작이 많은 경우이면direct access가 가능하여 검색 성능이 O(1)인 ArrayList를 쓰자
[Vector]
필요에 따라 크기를 동적으로 조절할 수 있는 동적배열을 구현(c++과 동일)
c++ vector와 마찬가지로 index를 이용하여 direct-access 가능
동기화(thread-safe) 되어있으며 한번에 하나의 스레드만 벡터의 메소드를 호출 할 수 있음
멀티쓰레드 환경이 아닐 때 Vector 클래스를 사용하게 되면 성능이 떨어지게 된다는 얘기다
cf) java로 ps할때 vector쓰면 안되는 이유
이건 ps에 좀 동떨어진 얘긴데
동기화를 지원한다는건 양날의 검이다
이게 왜냐하면 동기화를 지원한다는건
매번 어떤 작업이 실행될때마다 동기화 설정 처리를 한다는건데
이게 현업에서는 안정성 문제를 줄여줘도
오직 쓰레드를 하나만 쓰는 ps에서는 괜한 시간만 소비한다는 것이다
즉 처리할때 동기화 작업때문에 불필요한 오버헤드가 더 걸린다는 소리
따라서 얘는 ps에서는 굉장히 부적절한 stl이다
쓰지말자
[ArrayList]
고정 크기 배열에 기반한 리스트
index번호로 접근할 수 있는 random access가 가능해서 접근 시간복잡도가 O(1)이다
하지만 INSERT 시 배열 크기가 꽉 차면 더 큰 배열을 할당한 다음 기존 값을 복사하는 크기 조정 작업을 거쳐야함
그리고 DELETE 시 앞으로 땅겨주는 작업이 필요함
따라서
1. 크기가 정해져 있는 작업
2. INSERT DELETE 가 빈번하지 않은 작업
3. RANDOM ACCESS만 빈번한 작업
에 쓰는게 좋음
기본 데이터 타입(int, char 등)에 대해 만들수 없기때문에 Integer, Character, Object 등의 객체에 대해 참조해서 사용
[LinkedList]
내부적으로 doubled linked list를 이용하여 요소를 저장한다.
그래서 삽입 삭제가 O(1)이다
하지만 검색은 느림 random access를 지원안하기 때문 ㅇㅇ
head부터 노드 따라가면서 찾아야함
[Vector vs ArrayList]
1. 동기화(Synchronization)
Vector 는 한번에 하나의 쓰레드만 접근 가능하다.
ArrayList는 동시에 여러 쓰레드가 작업할 수 있다.
2. 쓰레드 안전(thread-safe)
== 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 동시에 접근이 이루어져도 프로그램 실행에 문제가 없음을 의미
Vector 는 동기화를 지원하기 때문에 한번에 하나의 쓰레드만 접근할 수 있으므로 thread-safe
ArrayList는 동기화를 지원하지 않기 때문에 동기화가 필요하면 명시적으로 동기화를 해줘야함
3. 성능
당연히 동기화(Synchronization)을 지원하지 않는 ArrayList가 더 빠르다
[ArrayList vs LinkedList]
ArrayList
direct access가 가능한 index 기반의 자료구조이기 때문에 get(int index)를 통해 접근 가능 O(1)
삽입, 삭제시 다 당기거나 뒤로 미뤄야하기 때문에 O(N)
LinkedList
처음노드부터 찾으려는 노드까지 순차적으로 탐색해야하므로 검색 최대 O(N)
삽입, 삭제시 이전노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 O(1)