[JAVA] 컬렉션 프레임워크(Collection Framework)

컬렉션 프레임워크(Collection Framework)

자바에서 컬레션 프레임워크이란, 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미한다. 다시 말해 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것이다.

JDK 1.2 이전까지는 Vector, Hashtable, Properties와 같은 컬렉션 클래스들을 서로 각자 다른 방식으로 처리해야 했으나 JDK 1.2부터 컬렉션 프레임웍이 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다.

이러한 컬렉션 프레임워크은 자바의 인터페이스(interface)를 사용하여 구현된다.

컬렉션 프레임워크의 핵심 인터페이스

컬렉션 프레임워크에서는 크게 컬렉션을 3가지 타입으로 나누어 핵심이 되는 주요 인터페이스를 정의했다.

1. List 인터페이스

2. Set 인터페이스

3. Map 인터페이스

여기서 List와 Set 인터페이스의 공통점을 뽑아내어 새로운 인터페이스인 Collection을 추가로 정의하였다. Map 인터페이스는 구조상의 차이로 인해 별도로 정의된다. 후에 컬렉션 프레임워크의 실세 소스를 분석해보면 객체지향적인 설계능력을 향상시키는데 많은 도움이 될 것이다.

자바에서 컬렉션 프레임워크를 구성하고 있는 인터페이스 간의 상속 관계는 다음 그림과 같다.

주요 인터페이스 간의 상속 관계

 위의 그림에서 <E>나 <K, V>는 컬렉션 프레임워크를 구성하는 모든 클래스가 제네릭으로 표현되어 있다는 것을 알려준다.

주요 인터페이스의 간략한 특징

인터페이스	설명	구현 클래스
List<E>	순서가 있는 데이터의 집합으로, 데이터의 중복을 허용한다.  예) 대기자 명단	Vector, ArrayList, LinkedList, Stack, Queue 등
Set<E>	순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않는다.  예) 양의 정수집합, 소수의 집합	HashSet, TreeSet 등
Map<K, V>	키(Key)와 값(Value)의 한 쌍으로 이루어진 데이터의 집합으로 순서가 없다. 키는 중복을 허용하지 않지만 값은 중복될 수 있다. 예) 우편번호, 지역번호(전화번호)	HashMap, TreeMap, Hashtable, Properties

컬렉션 프레임워크에 속하는 인터페이스를 구현한 클래스를 컬렉션 클래스(Collection Class)라고 한다. (즉 위의 List, Set, Map 3가지 중에 하나를 구현하고 있음.) 구현한 인터페이스의 이름이 클래스의 이름에  포함되어 있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있도록 되어있다.

(Vector, Stack, Hashtable, Properties와 같은 클래스들은 컬레션 프레임워크가 만들어지기 전에 존재하던 것이기 때문에 컬렉션 프레임워크의 명명법을 따르지 않음, Vector나 Hashtable과 같은 기존의 컬렉션 클래스들은 호환을 위해서 남겨두었지만 가능하면 사용하지 않는 것이 좋다. 그 대신 새로 추가된 ArrayList와  HashMap을 사용하자)

간단한 예시

import java.util.*;
 
public class Collection01 {
    public static void main(String[] args) {
        // 리스트 생성
        ArrayList<String> arrList = new ArrayList<String>();
 
        // 리스트에 요소의 저장
        arrList.add("넷");
        arrList.add("둘");
        arrList.add("셋");
        arrList.add("하나");
 
 
        // 리스트 요소의 출력
        for(int i = 0; i < arrList.size(); i++) {
            System.out.println(arrList.get(i));
        }
    }
}

[실행 결과]

넷

둘

셋

하나

Collection 인터페이스

List와 Set의 조상인 Collection 인터페이스에서 제공하는 주요 메서드는 다음과 같다.

메소드	설명
boolean add(Object o)  boolean addAll(Collection c)	해당 컬렉션에 전달된 요소를 추가함
void clear()	해당 컬렉션의 모든 요소를 제거함
boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체(o) 또는 컬렉션의 객체들이 컬렉션에 포함되어 있는지 확인함
boolean equals(Object o)	동일한 컬렉션인지 비교함
boolean isEmpty()	컬렉션이 비어있는지 확인함
Iterator<E> iterator()	해당 컬렉션의 반복자(iterator)를 반환함
boolean remove(Object o)	지정된 객체를 삭제함
int size()	해당 컬렉션의 요소의 총 개수를 반환함
Object[] toArray()	해당 컬렉션의 모든 요소를 Object 타입의 배열로 반환함

(JDK 1.8부터 추가된 parallelStream, removeIf, stream, forEach 등은 뒤의 람다와 스트림에서 설명)

JAVA API 링크

· Collection

List 인터페이스

List 인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다. 대표적인 List 컬렉션 클래스에 속하는 클래스는 다음과 같다.

1. ArrayList<E>

2. LinkedList<E>

3. Vector<E>

4. Stack<E>

ArrayList<E> 클래스

ArrayList클래스는 가장 많이 사용되는 컬렉션 클래스 중 하나이다. JDK 1.2부터 제공되었고 내부적으로 Object 배열을 이용하여 요소를 저장한다. 인덱스 0번째부터 차레대로 채워나가며 꽉 찬 경우에는 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다. 이 과정은 자동으로 수행되지만, 요소의 추가 및 삭제 작업이 걸린느 시간이 매우 길어지는 단점을 가지게 된다. 단방향 포인터 구조로 자료에 대한 순차적인 접근에 강점이 있다. (단방향 포인터이기 때문에 Iterator를 사용하면 좋을 것 같음)

ArrayList 예시

ArrayList<Integer> arrList = new ArrayList<Integer>();
 
// add() 메소드를 이용한 요소의 저장
arrList.add(40);
arrList.add(20);
arrList.add(30);
arrList.add(10);
 
// for 문과 get() 메소드를 이용한 요소의 출력
for (int i = 0; i < arrList.size(); i++) {
    System.out.print(arrList.get(i) + " ");
}
 
// remove() 메소드를 이용한 요소의 제거
arrList.remove(1);
 
// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
for (int e : arrList) {
    System.out.print(e + " ");
}
 
// Collections.sort() 메소드를 이용한 요소의 정렬
Collections.sort(arrList);
 
// iterator() 메소드와 get() 메소드를 이용한 요소의 출력
Iterator<Integer> iter = arrList.iterator();
 
while (iter.hasNext()) {
    System.out.print(iter.next() + " ");
}
 
// set() 메소드를 이용한 요소의 변경
arrList.set(0, 20);
 
for (int e : arrList) {
    System.out.print(e + " ");
}
 
// size() 메소드를 이용한 요소의 총 개수
System.out.println("리스트의 크기 : " + arrList.size());

실행결과

40 20 30 10 

40 30 10

10 30 40 

20 30 40

리스트의 크기 : 3

위 예제처럼 컬렉션 클래스의 요소를 출력하는 방법에는 for 문과 enhanced for 문, iterator() 메소드를 이용한 방법 등 다양한 방법을 사용할 수 있다. 

JAVA API 링크

· ArrayList

LinkedList<E> 클래스

LinkedList 클래스는 ArrayList 클래스가 배열을 이용하여 데이터를 저장함으로써 발생하는 단점을 극복하기 위해 탄생했다. JDK 1.2부터 제공된 LinkedList 클래스는 내부적으로 연결 리스트 (linked list)를 이용하여 요소를 저장한다. 배열은 순차적으로 저장되지만 연결 리스트는 저장된 요소가 비순차적으로 분포되며, 이러한 요소들 사이를 링크(link)로 연결하여 구성한다.

연결 리스트에는 단일 연결 리스트(singly linked list)와 이중 연결 리스트(doubly linked list)가 있다.

단일 연결 리스트

단일 연결 리스트는 저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경하면 되므로, 아주 빠르다. 하지만 이전 요소로 접근하기가 매우 어렵기 때문에 이를 개선한 것이 바로 이중 연결 리스트(doubly linked list)이다.

이중 연결 리스트

LinkedList 클래스도 이중 연결 리스트를 내부적으로 구현한 것이다. 또한, LinkedList 클래스 역시 List 인터페이스를 구현하므로, ArrayList 클래스와 사용할 수 있는 메서드가 거의 같다. ArrayList와 LinkedList의 차이는 사용 방법이 아닌, 내부적으로 요소를 저장하는 방법에 있다.

Vector<E> 클래스

Vector 클래스는 JDK.1.0부터 사용해온 ArrayList와 같은 동작을 수행하는 클래스이다. 하지만 현재에는 기존 코드와의 호환성을 위해서만 남아있으므로, Vector 클래스보다는 ArrayList 클래스를 사용하는 것이 좋다.

JAVA API 링크

· Vector

Stack과 Queue

Stack<E> 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다. 스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 원리를 따르는 자료구조다. (나중에 저장[push]된 데이터가 가장 먼저 인출[pop]되는 구조)

Stack 클래스 구조

Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메서드를 5개만 상속받아 사용한다.

메서드	설명
boolean empty()	해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
E peek()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
E pop()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
E push(E item)	해당 스택의 제일 상단에 전달된 요소를 삽입함.
int search(Object o)	해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.

(더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 된다.)

Stack 에제

Stack<Integer> st = new Stack<Integer>(); // 스택의 생성
//Deque<Integer> st = new ArrayDeque<Integer>(); // search 메서드를 지원하지 않음.
 
// push() 메소드를 이용한 요소의 저장
st.push(4);
st.push(2);
st.push(3);
st.push(1);
 
// peek() 메소드를 이용한 요소의 반환
System.out.println(st.peek());
System.out.println(st);
 
// pop() 메소드를 이용한 요소의 반환 및 제거
System.out.println(st.pop());
System.out.println(st);
 
// search() 메소드를 이용한 요소의 위치 검색
System.out.println(st.search(4));
System.out.println(st.search(3));

실행 결과

1

[4, 2, 3, 1]

1

[4, 2, 3]

3

1

JAVA API 링크

· Stack

Queue<E> 인터페이스

클래스로 구현된 스택과는 달리 자바에서 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다. 이러한 Queue 인터페이스를 상속받는 하위 인터페이스는 다음과 같다.

1. Deque<E>

2. BlockingDeque<E>

3. BlockingQueue<E>

4. TransferQueue<E>

Queue 인터페이스를 직간접적으로 구현한 클래스는 상당히 많다. 그와중에서도 Deque인터페이스를 구현한 LinkedList클래스가 큐 메모리 구조를 구현하는 데 가장 많이 사용된다.

Queue 인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection 인터페이스 메소드만을 상속받아 사용한다.

메서드	설명
boolean add	해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴.
E element()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
boolean offer(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함.
E peek()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함. 만약 큐가 비어있으면 null을 반환함.
E poll()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함. 만약 큐가 비어있으면 null을 반환함.
E remove()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.

(Java SE 6부터 지원되는 ArrayDeque 클래스는 스택과 큐 메모리 구조를 모두 구현하는데 가장 적합한 클래스다.)

(스택과 큐를 사용하여 undo / redo 같은 기능을 만들 수 있다.)

JAVA API 링크

· Queue

Set 인터페이스

Set 인터페이스를 구현한 Set 컬렉션 클래스는 요소의 저장 순서를 유지하지 않고, 같은 요소의 중복저장을 허용하지 않는다. 대표적으로는 HashSet<E>과 TreeSet<E>이 있다.

Set 인터페이스는 Collection 인터페이스를 상속받으므로, Collection 인터페이스에서 정의한 메소드도 모두 사용할 수 있다.

Set 인터페이스에서 제공하는 주요 메소드는 다음과 같다.

메서드	설명
boolean add(E e)	해당 집합(set)에 전달된 요소를 추가함.
void clear()	해당 집합의 모든 요소를 제거함.
boolean contains(Object o)	해당 집합이 전달된 객체를 포함하고 있는지를 확인함.
boolean equals(Object o)	해당 집합과 전달된 객체가 같은지를 확인함.
boolean isEmpty()	해당 집합이 비어있는지를 확인함.
Iterator<E> iterator()	해당 집합의 반복자(iterator)를 반환함.
boolean remove(Object o)	해당 집합에서 전달된 객체를 제거함.
int size()	해당 집합의 요소의 총 개수를 반환함.
Object[] toArray()	해당 집합의 모든 요소를 Object 타입의 배열로 반환함.

HashSet<E> 클래스

HashSet 클래스는 Set 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나. JDK 1.2부터 제공된 HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다. 이러한 HashSet 클래스는 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다. HashSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않습니다. 만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 됩니다.

HashSet<String> hs01 = new HashSet<String>();
HashSet<String> hs02 = new HashSet<String>();
 
// add() 메소드를 이용한 요소의 저장
hs01.add("홍길동");
hs01.add("이순신");
System.out.println(hs01.add("임꺽정"));
System.out.println(hs01.add("임꺽정")); // 중복된 요소의 저장
 
// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
for (String e : hs01) {
    System.out.print(e + " ");
}
 
// add() 메소드를 이용한 요소의 저장
hs02.add("임꺽정");
hs02.add("홍길동");
hs02.add("이순신");
 
// iterator() 메소드를 이용한 요소의 출력
Iterator<String> iter02 = hs02.iterator();
 
while (iter02.hasNext()) {
    System.out.print(iter02.next() + " ");
}
 
// size() 메소드를 이용한 요소의 총 개수
System.out.println("집합의 크기 : " + hs02.size());

실행결과

true

false

홍길동 이순신 임꺽정

홍길동 이순신 임꺽정

집합의 크기 : 3

위의 예제에서 요소의 저장 순서를 바꿔도 저장되는 순서에는 영향을 미치지 않는 것을 확인할 수 있다.

또한, add() 메소드를 사용하여 해당 HashSet에 이미 존재하는 요소를 추가하려고 하면, 해당 요소를 저장하지 않고 false를 반환하는 것을 볼 수 있다.

이때 해당 HashSet에 이미 존재하는 요소인지를 파악하기 위해서는 내부적으로 다음과 같은 과정을 거치게 된다.

1. 해당 요소에서 hashCode() 메소드를 호출하여 반환된 해시값으로 검색할 범위를 결정한다.

2. 해당 범위 내의 요소들을 equals() 메소드로 비교한다.

따라서 HashSet에서 add() 메소드를 사용하여 중복 없이 새로운 요소를 추가하기 위해서는 hashCode()와 equals() 메소드를 상황에 맞게 오버라이딩해야 한다.

자바 API 링크

· HashSet

TreeSet<E> 클래스

TreeSet클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장한다. 이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다. JDK 1.2부터 제공되는 TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현합니다. TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.

 

TreeSet

TreeSet<Integer> ts = new TreeSet<Integer>();
 
// add() 메소드를 이용한 요소의 저장
ts.add(30);
ts.add(40);
ts.add(20);
ts.add(10);
 
// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
for (int e : ts) {
    System.out.print(e + " ");
}
 
// remove() 메소드를 이용한 요소의 제거
ts.remove(40);
 
// iterator() 메소드를 이용한 요소의 출력
Iterator<Integer> iter = ts.iterator();
while (iter.hasNext()) {
    System.out.print(iter.next() + " ");
}
 
// size() 메소드를 이용한 요소의 총 개수
System.out.println("이진 검색 트리의 크기 : " + ts.size());
 
// subSet() 메소드를 이용한 부분 집합의 출력
① System.out.println(ts.subSet(10, 20));
② System.out.println(ts.subSet(10, true, 20, true));

실행 결과

10 20 30 40 

10 20 30 

이진 검색 트리의 크기 : 3

[10]

[10, 20]

위의 예제처럼 TreeSet 인스턴스에 저장되는 요소들은 모두 정렬된 상태로 저장된다.

또한, 위의 예제에서 사용된 subSet() 메소드는 TreeSet 인스턴스에 저장되는 요소가 모두 정렬된 상태이기에 동작이 가능한 해당 트리의 부분 집합만을 보여주는 메소드입니다.

1. public NavigableSet<E> subSet(E fromElement, E toElement)
 
2. public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

①번 라인에서 사용된 subSet() 메소드는 첫 번째 매개변수로 전달된 값에 해당하는 요소부터 시작하여 두 번째 매개변수로 전달된 값에 해당하는 요소의 바로 직전 요소까지를 반환.

②번 라인에서 사용된 subSet() 메소드는 두 번째와 네 번째 매개변수로 각각 첫 번째와 세 번째 매개변수로 전달된 값에 해당하는 요소를 포함할 것인지 아닌지를 명시할 수 있다.

즉, ②번 라인에서 네 번째 매개변수를 false로 변경하면 20을 포함하지 않게 되므로, ①번 라인과 같은 결과를 출력할 것이다.

JAVA API 링크

· TreeSet

컬렉션 클래스 정리 & 요약

각 컬렉션 클래스마다 장단점이 있으므로 구현원리와 특징을 잘 이해해서 상황에 가장 적합한 것을 선택하여 사용하는것이 바람직하다.

컬렉션	특징
ArrayList	배열 기반, 데이터의 추가와 삭제에 불리, 순차적인 추가삭제는 제일 빠름.  임의의 요소에 대한 접근성이 뛰어남.
LinkedList	연결기반, 데이터의 추가와 삭제에 유리, 임의이 요소에 대한 접근성이 좋지 않다.
HashMap	배열과 연결이 결합된 형태, 추가, 삭제, 검색, 접근성이 모두 뛰어남. 검색에는 최고.
TreeMap	연결기반, 정렬과 검색(특히 범위검색)에 적합. 검색 성능은 HashMap보다 떨어짐
Stack	Vector를 상속받아 구현
Queue	LinkedList가 Queue인터페이스를 구현
Properties	Hashtable을 상속받아 구현
HashSet	HashMap을 이용해서 구현
TreeSet	TreeMap을 이용해서 구현
LinkedHashMap LinkedHashSet	HashMap과 HashSet에 저장순서유지기능을 추가하였음.

참조 : TCPSchool

자바의 정석