JAVA 컬렉션 (Vector, ArrayList, LinkedList, Set, Map)

자바 컬렉션(Java Collections)

JAVA에서 대용량의 데이터를 추가/삭제하면서 처리가 필요할 때 자바 컬렉션을 사용한다.

Vector : java 1.0부터 이어져온 List객체, ArrayList가 상위호환(?)이라 잘 안쓴다. 특히 쓰레드의 개수와 상관없이 동기화(synchronize) 처리를 하므로 Thread-safe 하지만 싱글쓰레드 환경이어도 동기화처리를 하므로 성능이 좋지 않아 쓰이지 않는다.

ArrayList : Vector와 같은 추가/삭제 기능을 가지고 있고 자동 동기화처리가 되지 않기 때문에 빠르게 처리 가능,

대신 내부적으로 배열(array) 구조를 이용하기때문에 데이터 추가/제거를 배열을 복사하는 방법으로 처리하기 때문에 추가/제거가 많을 경우 오버헤드가 많이 발생함. 특히 중간에 삽입될 때 데이터들이 뒤로 밀리면서 성능저하가 큼.

대신! 인덱스를 가지로 있어서 조회할 때 한 번에 접근이 가능하기 때문에 대용량 데이터를 한 번에 가져와서 여러번 참조해 사용할 때 최상의 성능을 내는 객체다. (+크기 조절이 마음대로..)

Collections.synchronizedList, Collections.synchronizedMap, Collections.synchronizedCollection 등으로 동기화처리가 되는 컬렉션 생성하면 멀티쓰레드환경에서 쓸 수 있음.

LinkedList : C언어의 연결리스트처럼 다음 자료의 정보만 가지고 있고 내부적으로 인덱스는 없는 컬렉션

(양쪽으로 연결된 리스트를 만들 수도 있다)

연결된 자료의 정보만 담고 있기 때문에 중간 노드에 추가/삭제시 다른 데이터의 위치를 변경시킬 필요없이 간단하게 추가/삭제할 수 있다.

따라서 추가/삭제가 빈번하게 일어나는 대용량 데이터 처리가 필요할 때 사용하면 성능이 좋다.

대신 어디에 어떤 데이터가 있는지는 첫 노드부터 정보를 타고가면서 찾아야 하므로 검색에 있어서 성능이 좋지 않다. (ArrayList와 장단점이 반대다.)

스택, 큐, 양방향 큐등을 만들 때 사용한다.

여기서 질문!

-> 랜덤액세스할 때 ArrayList와 LinkedList 중에 어떤 것이 유리한가?

이에 대답은 ArrayList다. 랜덤 액세스 말 그대로 임의의 값에 접근하는데 ArrayList는 인덱스(0,1,2,...)로 한 번에 접근하기 때문에 유리하다. 반면 노드를 head나 tail부터 이동하며 접근하는 LinkedList는 성능상 불리하다.

-> 만약 추가/삭제도 많고 조회도 많으면 어떤 자료를 써야하나요?

여기서는 정답은 필자도 모른다.

다만 필자의 의견은 둘 중에 굳이 고르자면 ArrayList를 고른다 또는 다른 자료구조(ex. HashMap)을 사용하는 것이다.

첫 번째 근거는 LinkedList가 삽입/삭제에서 이 점을 갖는다고 했는데 결국은 어떤 값을 삭제할 때 존재하는지 확인해야한다는 것이다.

즉, 조회를 해야 삭제가 가능한 것이 아닌가 하는 의문이다. 정확하게 소스를 까서 보면 알 수 있겠지만 정확한 데이터는 아니니까 오해는 안했으면 한다. (개인 의견)

두 번째 근거는 테스트에 있다.

ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
 
// ArrayList add
long startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
    arrayList.add(i); 
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);
 
// LinkedList add
startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);
 
// ArrayList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);
 
// LinkedList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
    linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);
// ArrayList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
    arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);
 
// LinkedList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
    linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

위의 테스트소스 출처는 https://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/ 이다.

결과는 아래와 같다! (openjdk11, 메모리8GB, i5-6200U, win10 기준)

나노초로 찍었으니까 밀리로 환산하면 아래와 같다.

ArrayList add = 약 6ms , LinkedList add = 약 3ms

ArrayList get = 약 0.01ms , LinkedList get = 약 157ms

ArrayList remove = 약 135ms, LinkedList remove = 약 126ms

결과적으로 조회에서는 ArrayList가 압도하지만 취약하다던 add, remove에서는 크게 차이나지 않는다!

---

정리

위의 Vector, ArrayList, LinkedList는 List인터페이스의 구현 클래스다.

공통점 : 순서가 있는 데이터 집합이고 데이터 중복을 허용한다.

Vector : 과거에 사용하던 대용량 처리 컬렉션, 잘 사용 안하고 동기화처리가 자동적으로 내부에서 일어나므로 비교적 성능이 좋지 않고 무겁다.

ArrayList : 배열의 복사에 의한 데이터 저장처리를 내부적으로 수행하므로 많은 데이터의 추가/삭제시에는 성능이 떨어지나 각 데이터에 대한 인덱스를 가지고 있기 때문에 조회(검색)에 있어서 빠르다. (성능이 좋다)

특히 순차 접근이 필요할 때 인덱스가 있으므로 유용하다!

LinkedList : 다음 자료의 위치 정보를 가지며, 인덱스는 가지고 있지 않다. 데이터의 추가/삭제는 다음 데이터 위치정보만 수정하면 되므로 많은 정보의 추가/삭제가 일어날 때 유용하다. 대신 데이터 조회(검색)시 처음 자료부터 찾아 나가야 하므로 느려지는 단점이 있다.

---

Set

순서가 없는 데이터 집합이고 데이터 중복을 허용하지 않는다.

Set은 ArrayList처럼 인덱스가 따로 존재하지 않아 iterator(반복자)를 사용해야한다.

LinkedList도 순서는 있지만 인덱스가 없으므로 iterator를 사용해야 함.

Set<String> set = ...;
 
Iterator<String> iterator = set.iterator();

HashSet : 빠른 접근속도를 가지고 있음 단, 순서를 알 수 없음

LinkedHashSet : 추가된 순서대로 접근 가능

TreeSet : 정렬방법을 지정할 수 있음

---

Map

키(key), 값(value)으로 구성된 데이터 집합으로 key는 중복이 불가하지만 value는 중복 허용.

key를 알고 있다면 get메서드로 값을 가져올 수 있으나 저장된 객체 모두를 가져오고 싶다면 keySet()으로 모든 키를 Set으로 가져온 후 iterator를 통해 get메서드를 부르는 방법이 있음

Map<K, V> map = ...;
 
Set<K> keySet = map.keySet();
Iterator<K> it = keySet.iterator();
 
while (it.hasNext()) {
    K key = it.next();
    V value = map.get(key);
}

HashMap : 중복X, 순서X, null허용

HashTable : HashMap보다 느리지만 동기화 지원, null 불가

TreeMap : 정렬된 순서대로 저장되어 검색은 빠르지만, 요소 추가/삭제시 성능이 좋지 않음