[Java] 스터디 5주차_컬렉션 프레임웍

1. 컬렉션 프레임워크

컬렉션 : 컬렉션은 다수의 데이터, 즉 데이터 그룹을 의미하고 프레임웍은 표준화된 프로그래밍 방식을 의미

서로 다른 각자의 방식으로 처리해야 했던 Vector, Hashtable, Properties와 같은 컬렉션 클래스들을 보완하기 위해서 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다. 

 

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

• List : 순서가 있는 데이터의 집합, 데이터의 중복 허용
• Set : 순서를 유지하지 않는 데이터의 집합, 데이터의 중복 불허
• Map : 키와 값의 쌍으로 이루어진 데이터의 집합. 순서는 유지되지 않으며 키는 중복을 허용하지 않음. 

List와 Set은 서로 많은 공통 부분이 있어서 공통된 부분을 다시 뽑아 Collection 인터페이스를 정의할 수 있었다. 하지만 Map인터페이스는 전혀 다른 형태로 컬렉션을 다루기 때문에 같은 상속계층도에 포함되지 못했다. 

 

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

 

List 인터페이스

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

Set 인터페이스

중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현. 구현한 클래스로는 HashSet, TreeSet 등이 있다. 

Map 인터페이스 

키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현. Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등이 있다. 

Map.Entry 인터페이스

Map 인터페이스의 내부 인터페이스이다. 인터페이스 안에 인터페이스를 정의하는 내부 인터페이스를 정의하는 것이 가능하다. Map에 저장되는 key-value쌍을 다루기 위해 내부적으로 Entry 인터페이스를 정의해 놓았다. 다음은 Map 인터페이스의 소스코드의 일부이다.

public interface Map {
	...
    public static interface Entry {
    	Object getKey();
        Object getValue();
        Object setValue(Object value);
        boolean equals(Object o);
        int hashCode();
        ...
    }
}

 

1.2 ArrayList

List인터페이스를 구현한 것으로 Object 배열을 이용해서 데이터를 순차적으로 저장한다. 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다. 

ArrayList를 생성할 때, 저장할 요소의 개수를 고려해서 실제 저장할 개수보다 약간 여유있는 크기로 하는 것이 좋다. 생성할 때 지정한 크기보다 더 많은 객체를 저장하면 자동적으로 크기가 늘어나기는 하지만 이 과정에서 처리시간이 많이 소요되기 때문이다.

 

ArrayList와 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어진다는 단점을 가지고 있다. 따라서 처음에 인스턴스를 생성할 때 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다. 

 

※List인터페이스의 메서드 중 remove 구현 방법

1. 삭제할 데이터의 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.
2. 데이터가 모두 한 칸씩 위로 이동하였으므로 마지막 데이터는 null로 변경해야 한다.
3. 데이터가 삭제되어 데이터의 개수가 줄었으므로 size의 값을 1 감소시킨다.

 

1.3 LinkedList

배열은 구조가 간단하고 사용하기 쉽고, 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 잇지만 다음과 같은 단점이 있다. 

1. 크기를 변경할 수 없다 -> 새 배열을 생성해서 데이터를 복사해야 함
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다. 차례대로 데이터를 추가하고 마지막에서부터 데이터 삭제는 빠르지만 배열의 중간에 데이터를 추가하려면 다른 데이터들을 복사해서 이동해야 한다. 

이런 단점을 보완하기 위한 것이 링크드 리스트이다. 링크드리스트에서의 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 배열처럼 복사 과정이 없어서 처리속도가 매우 빠르다. 단방향 리스트는 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이를 보완한 것이 더블링크드리스트이다.

그리고 더블 링크드 리스트의 접근성을 보다 향상시킨 것이 double circular linked list'인데, 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 

 

LinkedList 클래스는 더블 링크드 리스트로 구현되어 있다. 이 역시도 List 인터페이스를 구현했기 때문에 ArrayList와 내부 구현 방법만 다르고 제공하는 메서드의 종류와 기능은 거의 같다. 

 

ArrayList와 LinkedList 클래스의 성능 차이는 다음과 같다. 

• 순차적으로 추가, 삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다. (충분한 초기용량을 확보했음을 가정) 마지막 요소의 값을 null로만 바꾸면 되기 때문에 ArrayList가 더 빠르다.
• 중간 데이터를 추가, 삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다. ArrayList는 하나하나 다 복사하여 옮겨줘야 한다. 

다만 데이터의 개수가 그리 크지 않다면 어느 것을 사용해도 큰 차이가 나지는 않는다. 

 

배열의 경우 만일 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식을 계산함으로써 해결된다. 

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

배열은 각 요소들이 연속적으로 메모리 상에 존재하기 때문에 간단한 계산만으로도 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만 LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 따라서 LinkedList는 저장해야 하는 데이터의 개수가 많아질수록 조회하는데 걸리는 시간 (=접근시간)이 길어진다는 단점이 있다. 

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

-> 다루고자 하는 데이터의 개수가 변하지 않는 경우 = ArrayList가 최상의 선택임

-> 데이터 개수의 변경이 잦다면 LinkedList가 최상의 선택

-> 혹은 조합해서 사용. 처음에 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용, 작업할 때는 LinkedList로 데이터를 옮겨서 작업

 

1.4 Stack과 Queue

큐는 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다. (ArrayList 사용 시데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사를 해야 한다) 

Stack st = new Stack();
Queue q = new LinkedList();

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

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

자바에서는 스택을 Stack 클래스로 구현하여 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue 인터페이스를 구현한 클래스들이 있어서 이들 중의 하나를 선택해서 사용하면 된다. 

 

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

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

 

PriorityQueue

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

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

Queue pq = new PriorityQueue();
pq.offer(3);
pq.offer(2);
pq.offer(1);
pq.offer(3);

 

Deque (Double-Ended Queue)

Queue의 변형으로, 한쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, 덱은 양쪽 끝에 추가/삭제가 가능하다. Deque의 조상은 Queue이며 구현체로는 ArrayDeque와 LinkedList 등이 있다. 

 

1.5 Iterator, ListIterator, Enumeration

이 세가지는 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다. Enumeration은 Iterator의 구버전이며 ListIterator는 Iterator의 기능을 향상시킨 것이다.

 

Iterator

컬렉션에 저장된 요소들을 읽어오는 방법을 표준화했다. 컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator 인터페이스를 정의하고 Collection 인터페이스에는 Iterator를 반환하는 iterator()를 정의하고 있다. 

Collection c = new ArrayList(); // 다른 컬레션으로 변경 시 이 부분만 고치면 된다. 
Iterator it = c.iterator();

while (it.hasNext()){
	System.out.println(it.next());
}

 

 

이렇게 코드의 재사용성을 높이는 것이 가능하다. Collection에 없고 ArrayList에만 있는 메서드를 사용하는 게 아니라면, Collection 타입의 참조변수로 선언하는 것이 좋다. 

 

Map 인터페이스를 구현한 컬렉션 클래스는 키와 값을 쌍으로 저장하고 있기 때문에 iterator()를 직접 호출할 수는 없고 그 대신 keySet()이나 entrySet()과 같은 메서드를 통해서 키와 값을 각각 따로 Set 형태로 얻어온 후에 다시 iterator()를 호출해야 한다. 

Enumeration은 더 이상 사용하지 않으니 Iterator를 사용하자. 

 

ListIterator 

Iterator에 양방향 조회기능을 추가한 것이다. List를 구현한 경우(ArrayList or LinkedList)만 사용가능하다. 

 

 

1.6 Arrays

배열의 복사 - copyOf(), copyOfRange()

copyOf()는 배열 전체를, copyOfRange()는 배열의 일부를 복사해서 새로운 배열을 만들어 반환한다. 늘 그렇듯이 copyOfRange()에 지정된 범위의 끝은 포함되지 않는다.