본문 바로가기

신입 개발자 면접 기초

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가 삽입/삭제에서 이 점을 갖는다고 했는데 결국은 어떤 값을 삭제할 때 존재하는지 확인해야한다는 것이다.

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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);
cs

위의 테스트소스 출처는 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를 사용해야 함.

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


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

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

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


Map

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

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

1
2
3
4
5
6
7
8
9
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 : 정렬된 순서대로 저장되어 검색은 빠르지만, 요소 추가/삭제시 성능이 좋지 않음

반응형