자바 컬렉션 프레임워크 (Java Collections Framework)

목차

자료구조의 분류

자료구조는 프로그래밍의 가장 기본이기 때문에 많은 언어들에서도 표준 라이브러리로 다양한 자료구조를 지원하고 있다.

이러한 자료구조의 이해를 돕기 위해 자바의 대표적인 자료구조인 Collection을 배워보자. (& 더 효율적인 스프링 개발을 위해선 자바를 공부해야 하기에…)

자료구조 분류법은 많은 분류법이 있지만, 대표적으로 많이 분류되는 방법은 선형 자료구조(Linear Data Structure)과 비선형 자료구조(Nonlinear Data Structure)로 나눌 수 있다. 이러한 분류를 보통 '형태에 따른 자료구조'라고 보고, 각 자료구조에 알맞게 구체화 된 것들을 '구현된 자료구조'이라고 한다.

선형 자료구조(Linear Data Structure)

선형 자료구조는 쉽게 데이터가 일렬로 연결된 형태라고 보면 된다. 우리가 흔히 쓰는 int[] 배열같은 것이라 생각하면 쉽다.

•

리스트(List)

•

큐(Queue)

•

덱(Deque)

비선형 자료구조(Nonlinear Data Structure)

선형 자료구조의 반대다. 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결 된 형태를 생각하면 된다. 쉽게 생각해서 거미줄 같다고 보면된다.

•

그래프(Graph)

•

트리(Tree)

그리고 위 두 가지 분류에 해당되지 않는 자료구조가 있는데 집합(Set)이 있다. 보통 기타 자료구조 또는 집합 자료구조로 본다. 집합의 경우는 데이터가 연결 된 형식이 아니다. set은 table에 가까운 자료구조라고 보고 있다.

그리고 파일 자료구조도 있는데, 파일구조는 순차파일, 색인파일, 직접파일이 있다는 정도로만 알아두자.

Java Collections Framework

Java Collections Framework를 단어 그대로 해석하면, 일정 타입의 데이터들이 모여 쉽게 가공할 수 있도록 지원하는 자료구조들의 뼈대(기본 구조)라는 의미이다.

기본 구조라고 하면 바로 떠올라야 할 것이 바로 Interface(인터페이스)다. 인터페이스 자체가 기본 뼈대(추상 구조)만 있지 않은가? 실제로 자바에서 제공하는 Collection은 크게 3가지 인터페이스로 나뉘어있다. 크게 List(리스트), Queue(큐), Set(집합)으로 나뉘어 있다. 앞서 설명한 '형태에 따른 자료구조'라고 보면 된다. 그리고 각 분야별로 '구현' 된 것들이 있다.

아래 이미지를 보자.

점선은 구현 관계이고, 실선은 확장 관계다. (인터페이스끼리는 다중 상속이 가능하다) 또한 Collection을 구현한 클래스 및 인터페이스들은 모두 java.util 패키지에 있다.

List, Queue, Set 이 3가지의 형태에 따른 자료구조들이 있다. 그리고 Queue와 Set에는 조금 더 구체화 되어 Deque과 SortedSet이라는 형태에 따른 자료구조가 있는 것이다. 그리고 이 형태에 따른 자료구조들은 각각 '구현'이 되어 class로 제공된다. 바로 녹색 부분이 '구현된 자료구조'라고 보면 된다. 자바에서 Interface를 class파일에서 쓰면 보통 '구현한다'라고 한다. 이러한 메커니즘에 기반하여 이해하면 된다.

그럼 왜 Collection Interface 상위에 Iterable 이 있는가? 저기서 제공하고 있는 class 들은 모두 객체형태로 내부 구현 또한 대개 Object[] 배열 형태가 아니라 각각의 객체를 갖고 움직인다. 그래서 객체의 데이터들을 모두 순회하면서 출력하려면 사용자들이 각각의 데이터 순회 방법을 알거나 하나씩 get() 같은 메소드를 통해 데이터를 하나씩 꺼내와야 한다.

하지만 Iterable 에서는 인터페이스를 보면 알겠지만 for-each 제공한다. 즉, Iterable 인터페이스를 쓰는 모든 클래스들은 기본적으로 for-each 문법을 쉽게 사용할 수 있다. 한마디로 반복자로 구현되어 나오게 하는 것이다.

컬렉션 프레임워크 장점

자바만의 컬렉션 프레임워크의 장점은 다음과 같다.

•

인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에, 사용법을 익히기에도 편리하고 재사용성이 높다.

•

데이터 구조 및 알고리즘의 고성능 구현을 제공하여 프로그램의 성능과 품질을 향상시킨다.

•

관련 없는 API 간의 상호 운용성을 제공한다. (상위 인터페이스 타입으로 업캐스팅하여 사용)

•

이미 구현되어있는 API를 사용하면 되기에, 새로운 API를 익히고 설계하는 시간이 줄어든다.

•

소프트웨어 재사용을 촉진한다. 만일 자바에서 지원하지 않는 새로운 자료구조가 필요하다면, 컬렉션들을 재활용하여 새로운 알고리즘을 만들어낼 수 있다.

Collection Interface

이제 Collection에서 List, Queue, Set에 대해 간략히 알아보자.

List Interface

List Interface(리스트 인터페이스)는 대표적인 선형 자료구조로 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스다.

좀 더 쉽게 얘기하면 우리가 배열에서 쓸 때 int[] array = new int[10]; 처럼 쓴다. 하지만, 이 처럼 선언한 배열의 경우 10개의 공간 외에는 더이상 사용하지 못한다. 즉, array[13] = 32; 라고 해주더라도 할당된 크기(범위) 밖이기 때문에 IndexOutofBoundsException 라는 에러가 발생한다.

이러한 단점을 보완하여 List를 통해 구현된 클래스들은 '동적 크기'를 가지며 배열처럼 사용할 수 있게 되어있다.

한마디로 배열의 기능 + 동적 크기 할당이 합쳐져 있다고 보면 된다.

List Interface를 구현하는 클래스

1. ArrayList

2. LinkedList

3. Vector (+ Vector를 상속받은 Stack)

List Interface에 선언된 대표적인 메소드

•

ArrayList는 Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리를 한다. 흔히 쓰는 primitive 배열(ex int[])과 유사한 형태라고 보면 된다. 

즉, 최상위 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근(access elements)에서는 탁월한 성능을 보이나, 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적인 모습을 보인다.

•

LinkedList는 데이터(item)와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다. 데이터와 주소로 이루어진 클래스를 Node(노드)라고 하는데, 각 노드는 이전의 노드와 다음 노드를 연결하는 방식인 것이다.(이중 연결 리스트라고도 한다.) 즉, 객체끼리 연결한 방식이다. 

이렇다 보니 요소를 검색해야 할 경우 처음 노드부터 찾으려는 노드가 나올 때 까지 연결된 노드들을 모두 방문해야 한다는 점에서 성능이 떨어지나, 해당 노드를 삭제, 삽입해야 할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 매우 좋은 효율을 보인다.

•

Vector는 자바를 배울 때 그리 자주 보이지는 않는 클래스인데, 기본적으로 ArrayList와 거의 같다고 보면 된다. Object[] 배열을 사용하며 요소 접근에서 빠른 성능을 보인다. 근데 왜 Vector가 있는 것이냐?라고 한다면, 원래 Vector는 Collection Framwork가 도입되기 전부터 지원하던 클래스였다. 

그리고 Vector의 경우 항상 '동기화'를 지원한다. (쉽게 말하면 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 한다.) 그렇다보니 멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다.

•

Stack은 우리가 흔히 생각하는 것처럼 쌓아 올리는 것이다. 전문 용어로 말하면 LIFO(Last in First out) 또는 후입선출이라고 하는데, 쉽게 생각하면 우리가 짐을 쌓는다고 생각하면 쉽다. 짐을 쌓아올릴 때 가장 마지막에 쌓은 짐이 가장 위에 있을 것이다. 그리고 짐을 뺄 때도 가장 위에 있는 짐부터 빼게 될 것이다. 

가장 대표적인 예시로는 웹페이지 '뒤로가기'가 있다. 우리가 새로운 페이지로 넘어갈 때마다 넘어가기 전 페이지를 스텍에 쌓고, 만약 뒤로가기를 누른다면 가장 위에 있는 페이지부터 꺼내오는 방식이다.

참고로 Stack의 경우 Vector클래스를 상속받고 있고, java에서 지원하는 Stack 클래스의 메소드들도 뜯어보면 알겠지만, 모두 Vector에 있는 메소드를 이용하여 구현되고 있어 크게 다를 것은 없다.

각각의 객체 생성 방법은 다음과 같다.

/* 
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
ex) LinkedList<Integer> list = new LinkedList<>();
primitive type은 불가능하다.
*/
 
// 방법 1
ArrayList<T> arraylist = new ArrayList<>();
LinkedList<T> linkedlist = new LinkedList<>();
Vector<T> vector = new Vector<>();
Stack<T> stack = new Stack<>();
 
// 방법 2
List<T> arraylist = new ArrayList<>();
List<T> linkedlist = new LinkedList<>();
List<T> vector = new Vector<>();
List<T> stack = new Stack<>();
 
// Stack은 Vector를 상속하기 때문에 아래와 같이 생성할 수 있다.
Vector<T> stack = new Stack<>();
Java
복사

방법 1을 사용하는 것을 권장.

Queue Interface

Queue Interface(큐 인터페이스)는 선형 자료구조로 주로 순서가 있는 데이터를 기반으로 '선입선출(FIFO : First-in First-out)'을 위해 만들어진 인터페이스다. 흔히 Stack(스택)과 많이 비교를 하는 자료구조다.

큐에 대해 간단하게 말하자면 10, 20, 30, 40 순으로 데이터를 넣고, 데이터를 꺼낼 때(poll) 넣은 순서 그대로 10, 20, 30, 40이 나오는 구조라는 것이다. 이 때 가장 앞쪽에 있는 위치를 head(헤드)라고 부르고, 가장 후위(뒤)에 있는 위치를 tail(꼬리)라고 부른다. 예로 들면, 놀이기구를 타기 위해 줄 서있는 모습을 상상하면 된다.

Collection 구조를 보면 알겠지만, Queue를 상속하고 있는 Deque(덱) 이라는 Interface도 있다. 둘 다 같은 부류인데 Queue는 한쪽 방향으로만(단방향) 삽입 삭제가 가능한 반면, Deque는 Double ended Queue라는 의미로 양쪽에서 삽입, 삭제가 가능한 자료구조라 보면 된다. 즉, head에서도 접근 가능하며, tail에서도 접근 가능한 양방향 큐라고 보면 된다.(Queue에서 확장된 형태)

Queue/Deque Interface를 구현하는 클래스

1. LinkedList

2. ArrayDeque

3. PriorityQueue

Queue/Deque Interface에 선언된 대표적인 메소드

LinkedList가 또 나왔는데, 처음 그림을 보면 알겠지만 LinkedList는 List(리스트)를 구현하기도 하지만, Deque(덱)도 구현한다. 그리고 Deque Interface는 Queue Interface를 상속받는다.

즉, LinkedList는 사실상 3가지 용도로 쓸 수 있다.

1. List

2. Deque

3. Queue

실제로도 LinkedList class를 보면 다음과 같이 List와 Deque를 모두 구현한다.

public class LinkedList<E>
	extends AbstractSequentialList<E>
	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	transient int size = 0;
	
	/**
	* Pointer to first node.
	*/
	transient Node<E> first;
	
	/**
	* Pointer to last node.
	*/
	transient Node<E> last;
Java
복사

왜 LinkedList를 받을까? 이를 설명하기에는 조금 길어지니 간단하게 말하자면, 앞서 List를 설명할 때도 말했지만, ArrayList와 LinkedList의 차이점은 Object[] 배열로 관리하느냐, Node라는 객체를 연결하여 관리하느냐의 차이였다.

마찬가지다. Deque 또는 Queue를 LinkedList 처럼 Node 객체로 연결해서 관리하길 원한다면 LinkedList를 쓰면 된다. 원리 자체는 크게 다르지 않기 때문에 LinkedList 하나에 다중 인터페이스를 포함하고 있는 것이다.

반대로 ArrayList처럼 Object[] 배열로 구현되어 있는 것은 ArrayDeque 이다. 물론 LinkedList와 ArrayDeque 둘 다 Deque을 구현하고 있고, Deque은 Queue를 상속받기 때문에 Queue로도 쓰일 수 있다.

만약 자바에서 지원하는 컬렉션에서 '일반적인 큐'를 사용하고자 한다면 LinkedList로 생성하여 Queue로 선언하면 된다. 쉽게 말해서 아래와 같이 선언하면 된다.

Queue<T> queue = new LinkedList<>();
Java
복사

Deque도 마찬가지다.

Deque<T> queue = new LinkedList<>();
Java
복사

•

PriorityQueue는 단어 해석 그대로 '우선순위 큐'다. LinkedList는 Queue로 사용할 수 있다고 했다. 다만 큐의 원리가 선입선출이라는 전제 아래 짜여있다. 하지만 PriorityQueue는 '데이터 우선순위'에 기반하여 우선순위가 높은 데이터가 먼저 나오는 원리다. 

따로 정렬방식을 지정하지 않는다면 낮은 숫자가 높은 우선순위를 갖는다. 쉽게 생각하면 정렬 메소드인 sort()와 같은 순서로 데이터 우선순위를 갖는다는 의미다.

PriorityQueue는 주어진 데이터들 중 최댓값, 혹은 최솟값을 꺼내올 때 매우 유용하게 사용될 수 있다. 다만, 사용자가 정의한 객체를 타입으로 쓸 경우 반드시 Comparator 또는 Comparable을 통해 정렬 방식을 구현해주어야 한다.

각 클래스별 객체 생성 방법은 다음과 같다.

/* 
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
단, primitive type은 불가능하다.
*/
 
ArrayDeque<T> arraydeque = new ArrayDeque<>();
PriorityQueue<T> priorityqueue = new PriorityQueue<>();
 
Deque<T> arraydeque = new ArrayDeque<>();
Deque<T> linkedlistdeque = new LinkedList<>();
 
Queue<T> arraydeque = new ArrayDeque<>();
Queue<T> linkedlistdeque = new LinkedList<>();
Queue<T> priorityqueue = new PriorityQueue<>();
Java
복사

Set Interface

Set(세트)는 말 그대로 '집합'이다. Set의 가장 큰 특징이라 하면 크게 두 가지가 있다. 첫 번째로 '데이터를 중복해서 저장할 수 없음'이다. 두 번째는 '입력 순서대로의 저장 순서를 보장하지 않는다'이다.

(다만 LinkedHashSet은 Set임에도 불구하고 입력 순서대로의 저장순서를 보장하고 있다. 그러나 데이터를 중복해서 저장할 수 없는 것은 같다.)

그리고 Queue와 유사하게 Set을 상속받고 있는 SortedSet Interface도 있다.

Set/SortedSet Interface를 구성하는 클래스

1. HashSet

2. LinkedHashSet

3. TreeSet

Set/ Interface에 선언된 대표적인 메소드

•

HashSet은가장 기본적인 Set 컬렉션의 클래스인데, 입력 순서를 보장하지 않고, 인덱싱 순서도 마찬가지로 보장되지 않는다. 그러면 어디에 쓰이냐는 생각이 들 수도 있다.

가장 쉽게 이해할 수 있는 예로는 여러분이 게임에서 '닉네임'을 만든다거나 아이디를 생성할 때 '중복확인'을 눌러 중복된 닉네임 또는 아이디인지 확인하는 것이다. 이는 데이터가 정렬되어있을 필요도 없고, 빠르게 중복되는 값인지만 찾으면 되기 때문에 유용한 방법이 될 수 있다.

좀 더 상세하게 말하자면 hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다. 즉, Hash 기능과 Set컬렉션이 합쳐진 것이 HashSet이다. 그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나다.

•

LinkedHashSet의 경우 이름에서 볼 수 있듯이 Link + Hash + Set 이 결합된 형태다. LinkedList에서 보면 add() 메소드를 통해 요소들을 넣은 순서대로 연결한다. 즉, LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미다.

Set의 경우 기본적으로 입력 순서대로의 저장 순서를 보장하지 않아 '중복은 허용하지 않으면서 순서를 보장받고 싶은 경우'에는 불편할 수밖에 없다. 이를 보완하기 위해 존재하는 것이 바로 LinkedHashSet인 것이다.

•

TreeSet은 HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다. 다만 특별한 점이 있다면 SortedSet Interface의 이름을 보면 알 수 있듯 이를 구현한 TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 보장한다는 것이다. 

앞서 PriorityQueue를 생각해보자. 데이터들이 입력한 순서대로가 아닌 값에 따라 정렬되어 Queue에 담아진다. 마찬가지로 TreeSet은 '중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다. 정렬된 형태로 있다보니 특정 구간의 집합 요소들을 탐색할 때 매우 유용하다.

(Tree 라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것이다.)

각 클래스별 객 생성방법은 다음과 같다.

/* 
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
단, primitive type은 불가능하다.
*/
 
HashSet<T> hashset = new HashSet<>();
LinkedHashSet<T> linkedhashset = new LinkedHashSet<>();
TreeSet<T> treeset = new TreeSet<>();
 
SortedSet<T> treeset = new TreeSet<>();
 
Set<T> hashset = new HashSet<>();
Set<T> linkedhashset = new LinkedHashSet<>();
Set<T> treeset = new TreeSet<>();
Java
복사