Java Collections Framework(JCF)란? - JCF의 계층 구조와 List (JAVA)

안녕하세요? 제이온입니다.

 

오늘은 JCF의 계층 구조와 컬렉션, 그리고 리스트를 중점적으로 살펴보겠습니다.

 

 

JCF의 계층 구조

JCF는 크게 Collection 인터페이스와 Map 인터페이스로 나눌 수 있습니다. 왜 Map만 따로 빼는지는 나중에 설명드리겠습니다.

 

 

 

 

Iterable Interface

컬렉션 인터페이스를 보면, Iterable 인터페이스를 상속받지만, Map 인터페이스는 그렇지 않습니다. 그렇다면, Iterable 인터페이스는 어떠한 메소드를 갖고 있을까요?

 

 

 

 

default 메소드인 forEach(), spliterator()가 있고 상속받은 클래스에서 구체화해주어야 하는 Iterator() 메소드가 있습니다. 여기서 forEach()와 iterator()는 모두 잘 아실 겁니다. 다만, spliterator()는 파이프라이닝 관련 메소드라 이 포스팅에서 설명하지는 않겠습니다.

 

그렇다면, Map 인터페이스에는 forEach()와 iterator()가 없을까요? 나중에 자세히 다룰 것이지만, Map 인터페이스에 forEach()는 있고, iterator()는 없습니다. 그 외에 spliterator()도 존재하지 않습니다.

 

Java를 처음 배우셨을 때, Map에는 iterator()가 없어서 곤란한 경험이 한 번쯤 있으셨을텐데 그 이유가 iterable 인터페이스는 컬렉션 인터페이스만 상속받고, Map은 iterable 인터페이스를 상속받지 않을 뿐아니라 iterator()가 구현되어있지 않기 때문입니다.

 

 

Collection Interface

컬렉션 인터페이스는 List, Set, Queue에 상속을 합니다. 컬렉션 인터페이스의 주요 메소드로는 add(), clear(), contain(), equals(), isEmpty(), iterator(), remove(), stream() 등이 있습니다. 상세 메소드 내역은 오라클 공식 문서를 참고하시길 바랍니다.

 

 

List Interface

순서가 있는 데이터의 집합으로, 데이터의 중복을 허용합니다. List 인터페이스는 ArrayList, LinkedList, Vector에 상속을 합니다.

 

 

ArrayList Class

ArrayList는 크기가 가변적인 선형 리스트로, 인덱스를 이용하여 내부 요소를 관리한다는 점이 일반적인 배열과 유사합니다. 하지만, 한 번 사이즈가 정해지면 바꿀 수 없는 배열과 달리, ArrayList는 저장 용량(capacity)이라는 것이 존재하여 이 용량을 넘어서면 자동으로 용량을 증가함으로써 추가적으로 요소를 넣을 수 있도록 해 줍니다.

 

 

 

 

ArrayList를 생성할 때 인자로 값을 넘겨주는 것으로 초기 용량을 설정할 수 있으며, 인자를 넘기지 않을 경우 초기 용량은 10으로 설정됩니다.

 

 

(1) 요소를 추가

요소를 추가하는 방법은 add(object)와 add(index, object)가 있습니다. 전자는 맨뒤에 요소를 차례차례 추가하는 것이지만, 후자는 원하는 위치에 요소를 끼워넣을 수 있습니다.

 

다만, add(index, object)는 원하는 위치에 요소를 끼워넣기위해서 그 위치를 앞뒤로 비집고 들어가야합니다. 

 

 

 

 

위 그림처럼 3번째 인덱스에 요소를 add(index, object)하고 싶다면, 원래의 3번째 인덱스부터 맨뒤까지 요소를 하나씩 다 밀어야합니다. 그리고 add(index, object)하는 과정에서 용량이 꽉차게 된다면, 새롭게 용량도 늘려줘야하기때문에 add(index, object)는 시간복잡도가 O(N)이 됩니다. add(object)는 시간복잡도가 O(1)인 것에 비해 성능은 떨어집니다.

 

 

(2) 요소를 삭제

요소를 삭제할 때는 remove()를 사용하는데, add(index, object)와 비슷한 원리입니다. i번째 요소를 지우면 그 자리가 비게 되므로 (i + 1)번째부터 마지막 인덱스의 요소를 한 칸씩 왼쪽으로 밀어야합니다. 시간복잡도는 마찬가지로 O(N)입니다.

 

 

(3) 요소를 탐색

요소가 있는지 없는지 탐색할 때는 contains()를 사용합니다. 맨 앞부터 탐색을 하므로 시간복잡도는 O(N)입니다.

 

 

(4) 요소를 반환

특정 요소를 반환할 때는 get()을 사용하는데, 인덱스를 사용하여 해당 위치를 바로 찾아낼 수 있으므로 시간복잡도는 O(1)입니다.

 

 

(5) 비동기 방식

ArrayList는 비동기 방식으로 작동하므로 다양한 쓰레드를 이용하는 멀티 쓰레드 환경에는 어울리지 않습니다. 다시 말하면, 쓰레드에 안전하지 않다고 볼 수 있습니다. 그렇다면, ArrayList는 멀티 쓰레드 환경에서는 절대 못 쓰는 것일까요? 이 부분은 아래 Vector와 함께 다뤄보겠습니다.

 

 

LinkedList Class

LinkedList는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다.

 

Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다.

 

중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.

 

그러므로 탐색 또는 정렬을 자주 하는 경우엔 ArrayList를 사용하고 데이터의 추가/삭제가 많은 경우 LinkedList를 사용하는 것이 좋습니다.

 

 

 

 

(1) 요소를 추가

요소를 추가할 때는 add()를 사용하는데, ArrayList와 마찬가지로 add(obejct)는 맨 뒤에 요소를 추가하는 것이고, add(index, object)는 특정 위치에 요소를 넣습니다.

 

 

 

 

위 사진처럼 먼저, 인자로 받은 값을 가지고 Node를 생성합니다. 그리고 이전 노드는 새로 생성한 노드를 가리키고, 생성한 노드는 이전 노드가 가리키고 있던 곳을 가리키게 합니다.

 

중간 위치에 요소를 삽입할 때의 시간복잡도는 O(N)이 됩니다.

 

 

(2) 요소를 삭제

LinkedList에 요소를 제거하는 방법은 요소를 추가하는것과 비슷합니다. remove(index, value)를 사용하여 특정 index의 값을 제거할 수 있습니다.

 

 

 

 

삭제할 노드의 이전 노드가 가리키는 곳을 다음 노드로 가리키게 하면 해당 노드는 삭제가 됩니다. 이것도 요소 추가와 마찬가지로 시간복잡도가 O(N)이 됩니다.

 

 

(3) 요소를 탐색

요소가 있는지 없는지 탐색할 때는 contains()를 사용합니다. 맨 앞부터 탐색을 하므로 시간복잡도는 O(N)입니다.

 

 

(4) 요소를 반환

특정 요소를 반환할 때는 get()을 사용하는데, 인덱스 없이 맨 앞부터 탐색해야하므로 시간복잡도는 ArrayList와 달리 O(N)입니다.

 

 

(5) 비동기 방식

LinkedList는 ArrayList와 비동기 방식으로 작동하므로 다양한 쓰레드를 이용하는 멀티 쓰레드 환경에는 어울리지 않습니다. 다시 말하면, 쓰레드에 안전하지 않다고 볼 수 있습니다. 

 

 

(6) 주의 사항

LinkedList를 처음 배우면 요소를 추가하는 것과 요소를 삭제하는 것은 시간복잡도가 O(1)이라고 오해할 수 있습니다. 물론, 요소를 추가하고 삭제하는 것 자체는 O(1)이 맞습니다. 하지만, 그 요소가 있는 위치까지 탐색을 해야하므로 최종적으로 O(N)이라고 하는 것입니다. 다만, 맨 앞이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 둘 다 시간복잡도는 O(1)이 됩니다.

 

 

ArrayList와 LinkedList의 시간복잡도 정리

 

 

Vector Class

Java 첫 버전부터 있었던 자료 구조입니다. 지금은 쓰지 않지만, 호환성을 위해 남겨 놓은 레거시 클래스라고 할 수 있습니다. Vector는 ArrayList와 기능 상 거의 동일하지만, 한 가지 다른 점이 있습니다.

 

흔히, Vector는 동기화가 되어 있어서 멀티 쓰레드 환경에서 사용한다고 합니다. 하지만, 정말 Vector는 멀티 쓰레드 환경에서 사용해야하고, ArrayList는 싱글 쓰레드 환경에서만 사용해야할까요?

 

Vector는 특이하게도 동기화는 되어 있지만 쓰레드에 안전하지 않습니다. 참 웃기게도, Vector는 메소드에 대해서는 동기화 처리가 되어있는 것이 맞습니다. 하지만, Vector 인스턴스에 대해서는 동기화 처리가 되어있지 않습니다.

 

직접 인텔리제이에서 Vector 소스를 까 보면, 아래와 같이 addElement()가 synchronized를 사용하여 동기화가 되어있습니다.

 

 

 

 

Vector의 메소드에는 모두 동기화처리가 되어 있는 것은 이해하였습니다. 그러면, Vector 인스턴스에 대해서 동기화 처리 되어있지 않다는 것은 무슨 말일까요?

 

 

if (vector.size() > 0) {
    System.out.println(vector.get(0));
}

 

 

위의 코드는 Vector의 사이즈가 0보다 크다면, 첫 번째 요소를 출력하는 것입니다. 다른 쓰레드가 이 쓰레드에서 쓰인 size()와 get()에는 관여를 할 수 없습니다. 하지만, 다른 쓰레드가 Vector의 요소를 삭제해 버리면 어떨까요? 이 상황에는 race condition이 발생합니다. 쓰레드에 안전하지 못하다는 것이죠.

 

 

synchronized (vector) {
    if (vector.size() > 0) {
        System.out.println(vector.get(0));
    }
}

 

 

위와 같이 따로 synchronized 처리를 해야 race condition이 발생하지 않습니다.

 

 

그리고 ArrayList는 Collections.synchronizedlist()을 통해 ArrayList도 동기화된 리스트로 만들어줄 수 있습니다. 결과적으로, 싱글 쓰레드 환경에서는 동기화가 덕지덕지 붙어 있는 느린 Vector를 쓸 이유가 없고, 멀티 쓰레드 환경에서도 쓰레드에 안전하지 않기 때문에 Vector를 쓸 이유가 없습니다.

 

그 외에, Vector는 Stack을 상속하고 있습니다.

 

 

Stack Class

우리가 흔히 알고 있는 LIFO 방식의 Stack입니다. 메소드로는 push(), pop(), empty() 등이 있는데, 굳이 설명하지는 않고 이것도 쓰지말라는 것만 알려드리겠습니다. 왜냐하면, 위에서 언급한 구데기(?) Vector의 상속을 받기때문이죠. 즉, Stack은 Vector와 다름이 없습니다.

 

 

 

 

그리고 놀랍게도 오라클 문서에도 Stack을 사용할 때는 Deque를 사용하여 구현하라고 나와있습니다. Deque는 정말 간단히 말하면 Stack과 Queue의 짬뽕인데, Stack을 사용하기 위해서 Deque를 이용하라는 것은 아이러니합니다.

 

 

정리

지금까지 Collection 인터페이스를 상속받는 List 인터페이스에 대해 알아 보았습니다. 다음 시간에는 Queue와 Deque를 설명하도록 하겠습니다.

 

 

출처

Collections Framework in java - Testingpool

 

 

 

 

Why Vector class is obsolete in Java? – Techie Delight

 

 

Performance Analysis of ArrayList and LinkedList in Java - DZone Performance

 

 

자바에서 Vector와 Stack 컬렉션이 쓰이지 않는 이유?

 

 

Java Vector Thread safety