엄청난 취업난 속에서 드디어 나에게도 첫 면접의 기회가 생겼다.
너무 떨렸지만, 좋은 경험으로서 받아들이자고 생각하고 마음을 비우기로 했다.
실제 면접에서는 어려운 질문은 많지 않았고 JAVA의 기초적인 질문이 많았는데, Collection Framework에 대한 질문에 제대로 답변하지 못 한 기억이 있다.
그래서 오늘은 Collection Framework에 대해 제대로 공부하고 정리해 보고자 한다.
1. Collection Framwork란
자바에서 컬렉션 프레임워크(collection framework)란 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미합니다
즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것입니다.
여기서 중요한 것은 자료구조와 구현해 놓았다는 것이다.
서론(길어서 안 읽어도 됨ㅋ)
우리가 개발을 하게 되면 0부터 모든 걸 구현하여 개발하지 않는다.
예를 들어, 게임을 만들고 싶다면 기존에 잘 만들어진 Unity나 언리얼 엔진 같은 툴을 사용하지, 캐릭터의 이동을 위한 코드부터 시작해서 하나하나 모두 생으로 코딩하지 않는다는 뜻이다.
심지어 여기서 캐릭터의 이동 이전에 화면에 캐릭터가 보여지기 위한 창부터 구현을 해야하고 창을 구현하기 위해서... 뭐하고... 뭐하고...
이렇게 처음부터 끝까지 구현한다는 것은 엄청난 컴퓨터 지식을 요구하기도 하고 시간은 오래 걸린다.
다음에 같은 일이 발생했을 때 이러한 작업을 다시 반복해서 진행해야 한다면 지금 세계에 출시된 게임은 최소 100배 이상 적었을 것이다.
그렇기 떄문에, 다음에 재사용할 수 있도록 기존에 사용했던 잘 다듬어진 코드들을 어딘가에 정리해 놓거나, 그것들을 모아 툴로 만들어 둘 수도 있다.
우리가 Java JDK를 활용해서 개발을 하는 것도 이와 같은 이치이다. (라이브러리, 프레임워크, 여러 개발 도구 전부)
Java진영에서는 핵고수 개발자들이 이미 만들어 놓은 좋은 코드들을 우리들에게 제공한다.
( 굳이 사용하기 싫다면 안 쓰고 직접 구현해서 써도 된다. 자신이 핵고수 개발자를 뛰어 넘는 더 최고의 개발자라면. )
엄청나게 많은 코드들을 제공하고 있고, 이러한 API 중에는 자료구조 부분도 존재한다.
Collection Framework는 Java가 제공하는 수많은 구현체(미리 만들어진 코드들) 중에서 데이터를 효과적으로 처리하거나 저장할 수 있도록 설계된 자료구조 관련 영역들을 묶어 부르는 말이다.
만약, 누가 Collection Framework가 뭐냐고 묻는다면, 그냥 간단하게 Java에서 제공하는 API중 자료구조와 관련된 특정 영역이다. 라고 설명할 것 같다.
본론
1. 자료구조가 있으면 무엇이 좋을까
특정 자료구조가 없다고 해보자. 다수의 데이터를 처리하거나, 저장하기 위해 사용할 마땅한 구조가 없다.
보통 가장 일반적인 배열을 사용하게 되는데 배열은 한 번 할당한 크기 만큼만 사용이 가능하고 데이터 저장 방식이 한 가지로 너무 정형적인 특징을 갖고 있다.
때문에 더 효율적으로 다수의 데이터를 처리할 수 있고 원하는 형태로 데이터를 추가 삭제하며, 필요한 공간을 동적으로 할당하기 위해서는 적절한 자료구조가 필요하다.
2. Collection Framework를 왜 사용할까
Java에서는 자료구조의 구현체들을 Collection Framework를 통해 제공한다.
이미 잘 구현해 놓았기 때문에, 나 같은 일반 개발자가 직접 개발하는 것 보다 더 성능도 좋고, 무엇 보다 객체지항적으로 잘 설계되었기 때문에 일관된 API로 사용할 수 있다.
Collection Framework를 사용하는 이유
-
일관된 인터페이스(사용법)을 제공한다.
-
자료구조를 개발자가 직접 구현할 필요가 없다.
-
이미 오래동안 검증되고 최적화된 방식이다.
2. 종류
Collection Framework에서 제공하는 자료구조는 크게 List, Queue, Set, Map이 있고 각각 인터페이스로 존재한다.
List, Queue, Set에는 더욱 상위 개념으로 Collection이라는 인터페이스가 존재한다, Map은 List, Queue, Set과 달리 Key-Value 형태를 갖기 때문에 Collection를 상속받지는 않지만, Collection으로 분류된다.
이러한 List, Queue, Set, Map 인터페이스를 구현하여 여러 가지 형태의 자료구조를 구현체를 만들어 두었다.
1. List
List는 순서가 있고 데이터를 인덱스로 관리하며, 중복된 데이터를 허용하는 자료구조를 위한 최상위 인터페이스이다.
구현체에는 ArrayList와 LinkedList, Stack, Vector가 존재한다.
1-1 ArrayList
Java에는 Vector라는 ArrayList와 비슷한 자료구조가 있었는데, 이를 개선하여 더 좋게 만든 것이 ArrayList이다.
( 요즘은 Vetor를 거의 사용하지 않고 호환성을 위해서만 남겨둔 상태이다. 따라서 따로 설명하지 않을 것이다. )
이름에서 알 수 있듯 배열을 이용해 구현하였으며, 순차적으로 데이터가 저장되어 있다.
장점
1. 특정 데이터(index)에 대한 접근이 빠르다.
접근이 빠른 이유는 Java배열의 특징을 생각하면 알 수 있다. Java의 배열은 같은 유형의 데이터들만이 순차적으로 나열되어 있기 때문에 n번째 Index에 있는 데이터의 위치를 구할 때, 가장 첫 번째 메모리 위치로부터 (데이터가 자치하는 메모리 공간) * (n - 1)을 이동하면 원하는 데이터의 시작 메모리 위치를 알 수 있기 때문이다.
쉽게 생각해서 5칸을 차지하는 블록 10개를 배치했다면 5번째에 있는 블록의 시작 위치는 5칸 * (5 - 1)개 = 20으로, 20~25칸을 차지한다. -> 조회 속도 O(1)
2. 데이터의 순서가 유지된다.
배열을 이용하기 때문에 index가 곧 데이터의 순서이다.
단점
1. 저장 공간을 늘리는 과정에서 지연이 발생한다.
배열이 꽉차면, 배열을 복사하여 확장시키기 때문에 그 과정에서 지연이 발생한다.
2. 데이터의 추가 삭제가 오래 걸린다.
배열은 특정 인덱스(맨 뒤 제외)에 데이터를 추가하려면 해당 인덱스와 그 이후에 있는 데이터들을 모조리 이동시키고 그 자리에 데이터를 저장시킨다. 삭제도 비슷한 원리로 동작하기 때문에 시간이 오래 걸린다.
데이터의 정확한 이동 과정은 잘 모르겠지만, 단순히 모든 데이터를 복사해서 한 칸 이동시킨다고만 가정해도 꽤나 많은 비용이 들 것 같다.
사용
위와 같은 특징 때문에 조회가 빈번하고 추가 삭제가 적은 경우에 사용하기 좋다.
1-2 LinkedList
LinkedList는 각 요소(Node, 데이터)가 불연속적으로 저장되며, 각각의 Node끼리 연결되어 있는 구조의 List이다.
"불연속적이다"라는 말은 순서가 없다(물리적으로 랜덤하게 떨어져 있다)는 뜻이고 "연결되어 있다"는 것은 물리적으로는 떨어져 있지만 결국 하나로 이어진 것처럼 동작한다는 있다는 뜻이다.
LinkedList는 Node들이 이전 데이터와 다음 데이터로의 메모리 주소를 갖고 있는 형태로 이어져 있다. 쉽게 생각해서 손을 잡고 있는 사람들을 떠올리면 쉽다.
원래 일반적인 자료구조에서 Linked List는 단방향적인 특징을 띄고 이전 데이터와 다음 데이터 주소를 모두 갖는 형태는 Doubly Linked List라고 한다. JAVA의 LinkedList는 처음부터 Doubly Linked List 형태로 구현했다.
장점
1. 추가 삭제가 빠르다
LinkedList에 데이터를 추가할 때에는 적절한 메모리 위치 어딘가에 대충 만들고 마지막에 들어간 데이터의 다음 데이터를 가리키는 곳에 추가한 데이터의 메모리 위치를 할당하면 된다.
삭제할 때에는 해당 데이터를 찾아서 그냥 삭제를 해버리면 끝이고,
삭제하고 나서 잡고 있던 손이 끊긴 Node들끼리 서로 손을 붙잡게 이어 주면 된다.
2. 낭비되는 메모리가 줄어든다.
배열은 선언한 크기만큼 항상 메모리를 차지하고 있지만, 위와 같은 LinkedList는 추가되는 데이터에 대해 동적으로 메모리를 할당하고 연결만 시키면 되기 때문에 공간이 낭비될 일도 없고 부족할 일도 없다.
단점
1. 특정 데이터의 조회가 느리다.
원하는 데이터를 찾기 위해서는 첫 노드부터 하나하나 순차적으로 찾아야 하기 때문에 탐색하는 데에 시간이 조금 걸린다. -> 조회 속도 O(N)
2. 주소 저장을 위한 추가 메모리를 차지한다.
각 노드들이 이전 노드와 다음 노드의 주소를 가지고 있어야 하기 때문에 노드 하나를 저장하기 위해 추가적인 메모리가 필요해진다.
사용
데이터의 조회가 많이 없고 추가 삭제가 자주 일어나는 경우 사용하면 효율적이다.
굉장히 유연해 보이는 구조를 보이는데, 이러한 특징 때문인지 LinkedList는 Stack, Queue, Deque 자료 구조를 구현하는데 사용된다.
1-3 Stack
Stack은 Vetor를 통해 구현된 FILO(First In Last Out = 선입후출) 자료 구조이다. 쉽게 프링글스를 생각하면 된다.
Vetor를 통해 구현된 것만 봐도 알 수 있지만, 이제 잘 안 쓰인다.
이러한 Stack의 구조는 뒤에서 배울 Deque의 구조에서 한쪽을 막아 버린 형태와 완전히 똑같기 때문에 Stack을 직접 사용하지 않고 Deque를 사용하도록 Oracle에서도 직접 권장하고 있다.
2. Queue
Queue는 FIFO(선입선출)구조의 순서를 갖는 선형 자료 구조이다. 빨대를 떠올리면 쉽다.
Java의 Queue 인터페이스는 이러한 선형 자료 구조의 최상위 인터페이스이다.
구현체로는 PriorityQueue, LinkedList가 있다.
2-1 PriorityQueue
이진 트리 구조 기반의 힙을 이용한 구현체이며, 부모 노드가 자식 노드 보다 높은 우선순위를 갖는 완전 이진 트리 형태이다.
Queue의 특징을 그대로 가져가면서, 우선순위라는 개념을 도입하여 동작한다고 보면 된다.
Queue가 삽입된 순서대로 반환되고 삭제되는 개념이었다면, PriorityQueue는 삽입된 데이터들 중 우선순위가 가장 높은 데이터 순서대로 반환되고 삭제된다.
위에서는 Queue가 FIFO라고 했는데, PriorityQueue라는 구현체를 보면 알 수 있듯이 Queue가 꼭 FIFO로 동작하는 것은 아니다.
다만 FIFO가 일반적인 Queue 특징으로서 사용되는 의미이기 때문에 많이 사용되곤 한다. 그러니 FIFO라는 단어를 사용하는 문서나 글을 본다면 정말로 FIFO로 동작하는 것일 수도 있고, 아닐 수도 있으니 상황에 따라 잘 이해해야 한다.
장점
1. 데이터에 빠르게 접근 가능하다.
PriorityQueue는 데이터가 추가되면 재정렬을 하여 우선순위에 맞게 정렬 상태를 유지한다. 이렇게 정렬된 상태에서 우선순위가 가장 높은 데이터에 바로 접근하여 반환, 삭제하면 되기 때문에 빠르다. -> 시간복잡도 O(1)
2. 우선순위를 직접 지정할 수 있다.
PriorityQueue의 구현체에는 comparator() 메소드를 지원하는데, 메소드를 통해 지정한 기준으로 우선순위가 결정되기 때문에 커스터마이징이 가능하다.
단점
1. 정렬 비용이 든다.
데이터가 추가되면 해당 데이터를 우선순위에 맞게 배치해야 하기 떄문에 정렬에 비용이 든다.
정렬 방식은 가장 마지막 위치에 노드를 삽입하고 부모가 자신 보다 작은 경우 서로의 위치를 변경하고 작을 경우 멈춤. 정렬 시간 복잡도 -> O(logN)
정렬되어 있지 않은 상태에서의 정렬 시간 복잡도는 O(NlogN)이다.
사용
정렬 비용이 들기는 하지만, 우선순위에 맞게 순차적으로 처리를 해야하는 상황이라면 PriorityQueue에 저장해 놓는 게 오히려 더 우수하다.
우선순위가 있는 데이터들을 순서대로 하나하나 찾아 작업한다고 가정해 보자.
LinkedList를 사용할 경우 LinkedList의 특정 데이터를 찾는 시간 복잡도는 O(N)이고 그것을 N번 반복하게 되니 총 시간복잡도는 O(N^2)이다.
PriorityQueue의 경우, 정렬을 위해 사용한 시간들을 모두 더하면 O(NlogN)이고, 데이터가 이미 정렬되어 있으니 데이터를 찾는 데에는 O(1)이다. 즉, 결과적으로는 O(NlogN)만큼만 걸린 게 된다.
( 참고로 PriorityQueue의 iterate()메소드는 정렬된 상태를 보장하지 않는다. 우선순위순으로 순회하려면 While문이나 For문을 사용해 Poll해서 순회해야 한다. )
배열에 담는게 제일 빠른 거 아닌가요
아주 정확하다. 당신이 배열을 이용해서 어떤 경우의 수에도 우선순위에 맞게 데이터가 담길 수 있도록 개발할 수 있다면 말이다.
현실적으로 말이 안 되기 때문에 이러한 자료 구조가 필요한 것이다.
2-2 LinkedList
위에서 LinkedList로 Queue 구현이 가능하다고 했다. 실제로 Queue를 Implement하고 있다.
어떻게 가능하지?
그냥 데이터를 삽입할 때에는 첫번 째 노드와 연결하면 그만이고, 뺄 때에는 마지막 노드를 반환하면 된다.
LinkedList에 대한 내용은 위에서 작성했으니 생략한다.
3. Deque
Deque는 구현체는 아니고, Queue를 상속받는 인터페이스이다.
Queue의 특징이 삽입한 순서대로 나오는 입구와 출구같은 구조였다면, Deque는 양방향에서 모두 삽입 삭제(추출)가 가능한 형태이다.
당연히 Queue로서도 사용이 가능하고, Stack으로도 사용할 수 있다.
구현체로는 ArrayDeque, LinkedList가 있다.
3-1 ArrayDeque
원형 배열을 이용하여 Deque를 구현한 구현체이다.
첫 노드의 인덱스와 마지막 노드의 인덱스만 잘 관리하면, 배열을 이용해서 맨 앞이나 뒤의 데이터를 추가하거나 삭제할 때 기존의 데이터를 이동시킬 필요 없는 원형의 자료구조 구현할 수 있다.
이러한 원형 배열을 이용하여 Deque를 구현하는 것이다.
장점
1. Stack이나 Queue로 사용할 경우 다른 구현체 보다 효율적이다.
다른 구현체라고 해 봐야 LinkedList 정도가 있다. LinkedList의 경우 데이터가 추가되거나 삭제될 때, 각 노드들 간에 연결 과정이 필요하기 때문에 ArrayDeque가 성능적으로 더 좋다. 또, 노드간의 주소도 필요하지 않기 때문에 메모리적으로도 더 효율적이다
단점
비교군이 없어 크게 단점이랄게 없다. 보통 Deque는 ArrayDeque를 사용하면 된다.
다음으로
