[Java] Collection Framework 의 개념과 Collection 종류

Collection Framework란 ?

컬렉션 프레임워크(Collection Framework) 란 다양한 컬렉션(데이터의 집합)을 다루기 쉽게 클래스/인터페이스로 표준화 한 것을 말한다.

 

컬렉션을 다루는 다양한 클래스를 정의해놓아서 사용자는 데이터를 다루는 기능을 별도로 구현할 필요가 없고, 

다형성이 보장되어 있어서 구현체가 변경되어도 기존 기능을 문제 없이 사용할 수 있다 (ex) ArrayList -> LinkedList)

 

컬렉션 프레임워크의 대표적인 인터페이스로는 List, Set, Map, Queue가 있고 각각을 구현하는 여려 클래스가 존재한다.

 

List, Set, Queue는 공통 기능을 추출한 Collection 인터페이스를 상속하고 있지만, Map은 구조적 특성으로 인해 독립적으로 정의되어 있다. 

 

List 인터페이스

List 인터페이스는 저장되는 객체들의 순서를 보장하고 중복을 허용한다는 특징이 있다.(ex) 대기자 명단)

 

구현 클래스로는 ArrayList, LinkedList, Stack, Vector 가 있고 인터페이스의 주요 메서드는 다음과 같다.

https://velog.io/@oyeon/11-36-Collection-List-Set-Map-%EC%9D%B8%ED%84%B0%ED%8E%98%EC%9D%B4%EC%8A%A4

 

ArrayList<E>

https://chunsubyeong.tistory.com/81

 

ArrayList는 List 인터페이스의 대표적인 구현 클래스로, 배열에 다양한 타입의 객체를 저장하고 관리할 수 있는 기능을 제공한다.

 

단방향 포인터 구조로 각 데이터의 인덱스를 가지고 있어서 조회 성능이 뛰어나다는 장점을 가지고 있다. 

 

하지만 메모리에 연속적으로 저장되는 구조여서, 배열 중간에 요소를 추가/삭제하는 경우 나머지 요소를 옮기는 과정으로 인해 시간이 많이 소요된다.

 

그리고 ArrayList는 멀티 스레드 환경에서 Thread-Safe하지 않아서 주의해야 한다는 특징이 있다.

 

LinkedList<E>

LinkedList는 메모리 주소값 참조를 통해 데이터를 연결하는 이중 연결 리스트(Doubly Linked List) 구조의 클래스이다.

 

각 노드(Node) 객체 내에 이전 노드(Node)와 다음 노드(Node)의 참조 값을 가지고 있다. 

https://velog.io/@sweet_sumin/LinkedHashMap-%EB%82%B4%EB%B6%80-%EA%B5%AC%EC%A1%B0-%EC%82%B4%ED%8E%B4%EB%B4%A4%EC%96%B4

 

LinkedList는 데이터를 추가 / 삭제 시 인접한 두개의 노드의 참조값만 변경하면 되기 때문에 ArrayList에 비해 데이터의 추가 / 삭제가 빠르다는 장점이 있다. 

 

다만, ArrayList에 비해 각 데이터가 메모리상에 불연속적으로 저장되어 있기 때문에 조회가 느리다는 단점이 있다.

 

ArrayList와 LinkedList 비교

컬렉션 종류	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가/삭제는 LinkedList 보다 더 빠르다
LinkedList	느리다	빠르다	데이터가 많아질수록 데이터 접근성이 하락한다.

 

요약하자면 ArrayList는 조회 속도가 빠르고 LinkedList는 추가/삭제 속도가 상대적으로 빠르다.

• 순차적인 추가 및 삭제 : ArrayList가 LinkedList보다 조금 빠름
• 중간 위치에 추가/삭제 : ArrayList보다 LinkedList가 훨씬 빠름
• 요소에 대한 접근시간 : ArrayList가 LinkedList보다 훨씬 빠름

 

Vector<E>

Vector 클래스는 기본적으로 ArrayList와 동일한 자료 구조 및 기능을 가지고 있다.

 

ArrayList와 유일하게 다른 부분은 Synchronized 메서드를 사용해서 Thread-Safe하다는 점인데, 싱글 스레드인 경우에도 동기화를 위한 작업이 추가로 수행되기 때문에 ArrayList보다 성능이 조금 떨어진다.

 

Stack<E>

Vector 클래스를 상속받은 컬렉션 클래스로 전형적인 Stack 기능을 제공한다.

한 방향으로만 저장(Push) 과 추출(Pop)을 할 수 있는 LIFO(Last-In-First-Out) 구조를 가진다.

 

Stack 클래스는 Vector 클래스와 마찬가지로 Thread-Safe 하지만 느리다는 단점이 있다. 

https://beenii.tistory.com/161

 

Set 인터페이스

Set 인터페이스는 저장되는 객체들의 순서를 보장하지 않고 중복을 허용하지 않는다는 특징이 있다.(ex) 양의 정수 집합)

 

대표적인 구현 클래스로는 HashSet, TreeSet, LinkedHashSet이 있고 주요 메서드는 다음과 같다.

https://st-lab.tistory.com/238

 

HashSet<E>

HashSet은 Set 인터페이스를 구현한 대표적인 클래스로 순서를 보장하지 않고, 데이터 중복을 허용하지 않는다.

만약 데이터 순서를 유지하고 싶다면 LinkedHashSet을 사용해야 한다.

 

HashSet은 HashMap을 사용되어 구현되어 있고, 데이터 추가/삭제 시 중복 체크 과정을 수행해서 List 보다 느리다. (중복 체크 시 equals()와 hashCode()를 사용함)

 

TreeSet<E>

TreeSet은 HashSet과 동일하게 순서를 보장하지 않고, 동일한 객체를 중복해서 저장할 수 없는 클래스이다. 

 

HashSet과 다른점으로는 이진 탐색 트리 (Binary Search Tree) 구조로 되어 있어서, 데이터 추가/삭제 성능은 조금 더 안좋지만 정렬 및 검색에는 높은 성능을 보인다.

 

 

 

TreeSet은 이진 탐색 트리 중에서도 성능을 향상 시킨 레드-블랙 트리(Red-Black Tree)로 구현되어 있다. 

 

일반적인 이진 탐색 트리는 데이터가 편향되게 들어오는 경우 트리의 높이만큼 시간이 걸리는 문제가 있는데,

레드-블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치해서 데이터 추가 및 삭제 시 트리가 한쪽으로 치우치지 않게 균형을 맞춰서 해당 문제를 해결한다.

 

Queue 인터페이스

Queue 인터페이스는 데이터를 일시적으로 쌓아두기 위한 자료 구조로 일반적인 Queue를 구현하기 위해 사용된다.

 

Stack 컬렉션과 다르게 FIFO(First-In-First-Out) 형태를 가지고, 양방향으로 데이터를 저장(Enqueue)하고 추출(Dequeue)할 수 있는 구조이다.

 

Queue를 구현하는 클래스는 PriorityQueue가 있고 주요 메서드는 다음과 같다 

 

 

PriorityQueue<E>

PriorityQueue(우선순위 큐)는 데이터의 우선순위를 두어서 가장 높은 요소가 먼저 나가도록 하는 자료구조이다.

 

PriorityQueue는 내부적으로 힙으로 구성되어 있는데, 우선순위를 기준으로 최대힙(MaxHeap) 또는 최소힙(MinHeap)으로 구성되어 있다. (Heap으로 구성되어 있다는 것은 이진트리 구조라는 뜻이다)

// 최소 힙
PriorityQueue<Person> priorityQueueLowest = new PriorityQueue<>();

//최대 힙
PriorityQueue<Person> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

PriorityQueue는 객체 내부에 Comparable 인터페이스를 구현하거나, Comparator 클래스를 매개변수로 전달해서 정렬 조건을 따로 지정해줄 수 있다. 

1. Comparable 인터페이스 구현

compareTo 메서드에 해당 객체의 우선순위 조건을 지정하면 PriorityQueue 내부에서 compareTo 메서드를 참조해서 우선순위가 높은 객체를 추출한다.

@Getter
@Setter
public class Person implements Comparable<Person> {
    private String name;
    private int age;

    @Override
    public int compareTo(Person person) {
        if(this.age >= person.getAge()) {
            return 1;
        }
        return -1;
    }
}

2. Comparator 클래스 구현

Comparator 클래스의 compare() 클래스를 재정의 한 뒤 PriorityQueue 생성자 매개변수로 전달한다.

PriorityQueue<Person> reversedPriorityQueue = new PriorityQueue<>(
        (Person p1, Person p2) -> p1.getAge() >= p2.getAge() ? 1 : -1);

 

Deque

Deque 인터페이스는 Queue 인터페이스를 확장한 인터페이스로, 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있어서 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 구조를 가진다.

 

Deque 인터페이스를 구현한 클래스는 ArrayDeque, LinkedList 등이 있고 주요 메서드는 다음과 같다.

 

Special Value 라인에 있는 메서드들은 비어있거나 꽉 차있는 경우 false 또는 Null을 리턴하지만 Throws Exception 라인에 있는 메서드들은 예외를 발생시킨다는 차이가 있다.

https://st-lab.tistory.com/185

 

ArrayDeque<E>

ArrayDeque는 Deque 인터페이스를 구현하는 클래스로, Stack으로 사용할 때는 아래와 같은 Stack 클래스의 단점을 보완하고 Queue로 사용할 때는 Queue 클래스보다 빠르다는 장점을 가지는 컬렉션이다.

Stack의 단점 3가지
- 모든 메서드에 Synchronized를 통해 동기화 되어 있어서, 단일 스레드에서는 성능 저하 발생
- Vector 클래스를 상속받아서, 중간에 데이터를 삭제 및 삽입이 가능하다 (완벽한 LIFO 구조가 아님)
- Stack 클래스를 만들 때 초기 용량을 설정할 수 없다. 

 

단, ArrayDeque은 성능을 높이기 위해 Synchronized 를 사용하지 않기 때문에 Thread-Safe 하지 않아서 멀티 스레드 환경에서는 별도의 조치가 필요하다는 단점이 있고

 

내부 공간의 용량을 초과하는 경우 기존 배열의 크기에서 두배씩 늘려서 새로운 배열을 생성하기 때문에 메모리 효율성이 떨어질 수 있다는 문제가 있다.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    transient Object[] elements; 

    transient int head;

    transient int tail;

    public ArrayDeque() {
        elements = new Object[16];
    }

    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }  
}

 

위의 코드는 ArrayDeque의 내부 코드로, 생성자를 통해 기본 용량을 16으로 설정한 뒤 용량이 초과된 경우 doubleCapacity() 메서드가 호출되어 기존 크기에 2배만큼 큰 새로운 배열로 확장하는 것을 볼수 있다.

 

Map 인터페이스

Map 인터페이스는 키와 값의 쌍으로 이루어진 데이터 집합으로 순서를 보장하지 않고 키의 중복을 허용하지 않는다.

https://reakwon.tistory.com/151

 

주요 구현 클래스로는 HashMap, TreeMap, LinkedHashMap, HashTable 등이 있고 주요 메서드는 다음과 같다.

https://ssdragon.tistory.com/70

 

HashMap<K, V>

HashMap은 Map 인터페이스의 대표적인 구현 클래스로 해시 테이블 자료구조를 사용하는 클래스이다.

키와 값의 쌍(Entry 객체)으로 저장되고 키는 중복될 수 없다는 특징을 가진다.

 

삽입 / 삭제 / 조회 연산 시 O(1) 시간복잡도를 보장하며 매우 빠르다는 장점이 있지만, 순서를 보장하지 않고 멀티스레드 환경에서 Thread-Safe 하지 않다는 문제가 있다.

 

 

TreeMap<K, V>

TreeMap은 Map 인터페이스의 구현 클래스 중 하나로, 이진 검색 트리를 기반으로 구현되어있고 키를 기준으로 정렬해서 저장하는 특징을 가진다. (Comparable 인터페이스 또는 Comparator 클래스를 통해 정렬 기준을 지정할 수 있다)

 

TreeMap은 삽입,삭제, 조회 시 매번 내부적으로 정렬하는 과정이 수행되기 때문에 HashMap 보다 느리다는 단점이 있다. (O(logN) 시간 복잡도를 가진다.)

 

키 기준으로 정렬 해주지만 들어오는 순서는 보장하지 않고, 키의 중복을 허용하지 않는다.

 

LinkedHashMap<K, V>

LinkedHashMap은 HashMap을 상속받는 클래스로 HashMap과 LinkedList의 결합체 구조로 되어있다.

 

LinkedList와 동일하게 이중 연결 리스트(Doubly Linked List) 자료구조로 되어 있어서, Entry 내부에 이전 / 이후 Entry 참조를 저장해서 데이터의 순서를 보장한다는 특징을 가진다.

https://velog.io/@sweet_sumin/LinkedHashMap-%EB%82%B4%EB%B6%80-%EA%B5%AC%EC%A1%B0-%EC%82%B4%ED%8E%B4%EB%B4%A4%EC%96%B4

 

HashTable<K, V>

HashTable은 Map 인터페이스를 구현한 클래스 중 하나로, HashMap과 거의 기능이 동일한 컬렉션이다.

 

차이점으로는 HashTable은 동기화가 걸려있어서 Thread-Safe 하다는 점인데, 멀티스레드 환경에서 안전하게 컬렉션을 다룰 수 있다는 장점이 있지만 HashMap보다는 느리다는 단점이 있다.

 

 

참고

• https://soft.plusblog.co.kr/24
• https://www.youtube.com/watch?v=uPSkCKB4Kuo&list=PLlTylS8uB2fA5PevGI6ARN6v-VQWmqaix&index=16&ab_channel=%EC%96%B4%EB%9D%BC%EC%9A%B4%EB%93%9C%ED%97%88%EB%B8%8C%EC%8A%A4%ED%8A%9C%EB%94%94%EC%98%A4-AroundHubStudio
• https://coding-factory.tistory.com/555
• https://st-lab.tistory.com/185
• https://devlog-wjdrbs96.tistory.com/245