[Chapter 11] 컬렉션 프레임웍

컬렉션 프레임웍(Collections Framework)

'데이터 군을 저장하는 클래스들을 표준화한 설계'를 뜻한다.

컬렉션 : 다수의 데이터, 즉 데이터 그룹

프레임웍 : 표준화된 프로그래밍 방식

인터페이스	특징
List	순서가 있는 데이터의 집합. 데이터의 중복을 허용한다. 예) 대기자 명단 구현클래스 : ArrayList, LinkedList, Stack, Vector 등
Set	순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않는다. 예) 양의 정수집합. 소수의 집합 구현클래스 : HashSet, TreeSet 등
Map	키와 값의 쌍으로 이루어진 데이터의 집합 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. 예) 우편번호, 지역번호(전화번호) 구현클래스 : HashMap, TreeMap, Hashtable, Properties 등

개발 시 다루고자 하는 컬렉션의 특징을 파악하고 어떤 인터페이스를 구현한 컬렉션 클래스를 사용해야 하는지 결정해야하므로 위의 표에 적힌 각 인터페이스의 특징과 차이를 잘 이해하고 있어야 한다.

컬렉션 프레임웍의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스의 이름에 포함되어 있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있다.

 

Collection 인터페이스

컬렉션 클래스에 저장된 데이터를 읽고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의.

 

List 인터페이스

중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용

 

Set 인터페이스

중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용

HashSet, TreeSet

 

Map 인터페이스

키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용

Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap

 

Map.Entry 인터페이스

Map 인터페이스의 내부 인터페이스이다. 내부 클래스와 같이 인터페이스도 인터페이스 안에 인터페이스를 정의하는 내부 인터페이스를 정의하는 것이 가능

 

 

ArrayList

컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스일 것이다.

List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.

import java.util.*;

public class ArrayListEx1 {
    public static void main(String[] args) {
        ArrayList list1 = new ArrayList(10);
        list1.add(new Integer(5));
        list1.add(new Integer(4));
        list1.add(new Integer(2));
        list1.add(new Integer(0));
        list1.add(new Integer(1));
        list1.add(new Integer(3));

        ArrayList list2 = new ArrayList(list1.subList(1, 4));
        print(list1, list2);

        Collections.sort(list1);
        Collections.sort(list2);
        print(list1, list2);

        System.out.println("list1.containsAll(list2):" + list1.containsAll(list2));

        list2.add("B");
        list2.add("C");
        list2.add("A");
        print(list1, list2);

        list2.set(3, "AA");
        print(list1, list2);

        System.out.println("list1.retainAll(list2):" + list1.retainAll(list2));

        print(list1, list2);

        for (int i = list2.size()-1; i>=0; i--) {
            if(list1.contains(list2.get(i)))
                list2.remove(i);
        }
        print(list1, list2);
    }

    static void print(ArrayList list1, ArrayList list2) {
        System.out.println("list1:" + list1);
        System.out.println("list2:" + list2);
        System.out.println();
    }
}

/* 실행결과
list1:[5, 4, 2, 0, 1, 3]
list2:[4, 2, 0]

list1:[0, 1, 2, 3, 4, 5]
list2:[0, 2, 4]

list1.containsAll(list2):true
list1:[0, 1, 2, 3, 4, 5]
list2:[0, 2, 4, B, C, A]

list1:[0, 1, 2, 3, 4, 5]
list2:[0, 2, 4, AA, C, A]

list1.retainAll(list2):true
list1:[0, 2, 4]
list2:[0, 2, 4, AA, C, A]

list1:[0, 2, 4]
list2:[AA, C, A]
*/

 

 

LinkedList

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고있지만, 크기를 변경할 수 없고, 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 단점이 있다. 

이러한 배열의 단점을 보완하기 위해서 LinkedList라는 자료구조가 고안되었다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 현태로 구성되어 있다.

 

class Node {
	Node next;	// 다음 요소의 주소를 저장
    Object obj;		// 데이터를 저장
}

 

링크드 리스트에서의 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면된다.

배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

 

링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.

이 점을 보완한 것이 더블 링크드 리스트(이중 연결리스트, doubly linked list)이다.

더블 링크드 리스트는 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.

class Node {
	Node next;	// 다음 요소의 주소를 저장
    Node previous;	// 이전 요소의 주소를 저장
    Object obj;		// 데이터를 저장
}

 

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름. 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

다루고자 하는 데이터의 개수가 변하지 않는 경우라면, ArrayList가 최상의 선택

데이터 개수의 변경이 잦다면 LinkedList를 사용하는것이 더 나은 선택

 

 

 

Stack과 Queue

스택

LIFO : 마지막에 저장한 데이터를 가장 먼저 꺼내는 구조

 

큐

FIFO : 처음에 저장한 데이터를 가장 먼저 꺼내는 구조

 

스택에 0, 1, 2 순서로 데이터를 넣으면 꺼낼 때는 2, 1, 0의 순서로 꺼내진다.

큐에 0, 1, 2 순서로 데이터를 넣으면 꺼낼 때는 0, 1, 2의 순서로 꺼내진다.

 

스택은 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합,

큐는 LinkedList가 적합.

import java.util.*;

public class StackQueueEx {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList(); // Queue 인터페이스의 구현체인 LinkedList를 사용

        st.push("0");
        st.push("1");
        st.push("2");

        q.offer("0");
        q.offer("1");
        q.offer("2");

        System.out.println("= Stack =");
        while(!st.isEmpty()) {
            System.out.println(st.pop());
        }

        System.out.println("= Queue =");
        while(!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
}

/* 실행 결과
= Stack =
2
1
0
= Queue =
0
1
2
*/

 

스택과 큐의 활용

스택의 활용 예 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

큐의 활용 예 - 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

 

PriorityQueue

Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. 그리고 null은 저장할 수 없고 저장하면 NullPointerException이 발생한다.

PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙이라는 자료구조의 형태로 저장한다.

import java.util.*;

public class PriorityQueueEx {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();
        pq.add(3);
        pq.add(5);
        pq.add(7);
        pq.add(1);
        pq.add(4);
        pq.add(6);
        System.out.println(pq);

        Object obj = null;

        while((obj = pq.poll()) != null)
            System.out.println(obj);

    }
}

/* 결과
[1, 3, 6, 5, 4, 7]
1
3
4
5
6
7
*/

 

 

Deque(Double-Ended Queue)

Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque(덱, 또는 디큐)은 양쪽 끝에 추가/삭제가 가능하다.

 

 

Comparator와 Comparable

public interface Comparator {
	int compare(Object o1, Object o2);
    boolean equals(Object obj);
}

public interface Comparable {
	public int compareTo(Object o);
}

 

Comparable - 기본 정렬기준을 구현하는데 사용

Comparator - 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용

 

 

 

HashSet

Set 인터페이스를 구현한 가장 대표적인 컬렉션이며, Set 인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다.

새로운 요소를 추가할 때는 add 메서드나 addAll 메서드를 사용, 만일 HashSet에 이미 저장되어 잇는 요소가 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다.

 

이러한 특징을 이용하면, 컬렉션 내의 중복 요소들을 쉽게 제거할 수 있다.

 

 

TreeSet

이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다.

그리고 Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

 

이진 검색 트리는

- 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.

- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식 노드의 값은 부모노드의 값보다 커야한다.

- 노드의 추가 삭제에 시간이 걸린다. (순차적으로 저장하지 않으므로)

- 검색(범위검색)과 정렬에 유리하다.

- 중복된 값을 저장하지 못한다.

 

 

HashMap

HashMap은 Map을 구현했으므로 앞에서 살펴본 Map의 특징, 키와 값을 묶어서 하나의 데이터로 저장한다는 특징을 갖는다. 그리고 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

 

 

TreeMap

이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다. 그래서 검색과 정렬에 적합한 컬렉션 클래스이다.

검색에 관한한 대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 다만 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용하자.

 

 

Collections

Arrays가 배열과 관련된 메서드를 제공하는 것처럼, Collections는 컬렉션과 관련된 메서드를 사용한다. fill(), copy(), sort(), binarySearch() 등의 메서드는 두 클래스에 모두 포함되어 있으며 같은 기능을 한다.