[Java] Java Collections Framework 알아보기

 💬 자료구조

 

아마 다들 '자료구조'에 대해서 한번씩은 들어봤을 것이다.

자료구조는 Data Structure (데이터 구조) 라고 하는데 '일련의 일정 타입들의 데이터 모임 또는 관계를 나타낸 구성체' 라고 말할 수 있다.

 

💬 자료구조의 분류

 

가장 대표적으로 많이 분류되는 방법은 선형 자료구조와 비선형 자료구조로 나눌 수 있다.

이러한 분류는 형태에 따른 자료구조라고 볼 수 있다.

아래에는 위 자료구조에 대해 간단하게 정리해 보았다.

 

 1. 선형 자료구조 (Linear Data Structure)

• 데이터가 일렬로 연결된 형태
• 흔히 쓰는 int[] 배열과 같은 것
• 리스트(List), 큐(Queue), 덱(Deque)

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

• 각 요소가 여러 개의 요소와 연결 된 형태
• 거미줄 같다고 보면 이해하기 쉬움.
• 그래프(Graph), 트리(Tree)

3. 기타 자료구조

• 집합(Set) 자료구조
• table에 가까운 자료구조
• 데이터가 연결된 형식이 아님.

4. 파일 구조

• 순차파일
• 색인파일
• 직접파일

---

 

💬 Java Collection Framework

자바 컬렉션 프레임워크는 일정 타입의 데이터들이 모여 쉽게 가공할 수 있도록 지원하는 자료구조이다.

 

단어 자체가 어렵게 느껴질 수 있다.

풀이해서 설명해보자면, Java는 언어를 의미하는 것이고, Collection은 어떤 비슷한 부류의 것들을 수집하여 한 공간에 모아 놓은 것이다.

두 단어를 붙여보면 'Java에서도 비슷한 류의 데이터들을 쉽게 다루기 위해서 모아놓은 것들을 가공 및 처리 할 수 있도록 지원하는 자료구조' 라고 설명할 수 있을 것이다. 그리고, Framework는 문제를 해결하기 위한 구조의 뼈대가 되는 기본 구조이다.

 

기본 구조라고 한다면 떠올려야 할 것이 바로 Interface(인터페이스)이다.

인터페이스 자체가 기본 뼈대(추상 구조)만 있는게 아닌가 생각이 든다. 이렇듯 자바에서 제공하는 Collection은 크게 3가지 인터페이스로 나뉘어 있다. 형태에 따른 자료구조로 List, Queue, Set이 있다.

 

아래에 이미지를 참고하여 설명을 이어가겠다.

 

---

💬 List Interface

리스트는 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스이다.

예를들어, 배열을 쓸 때 int[] array = new int[5]; 쓴다면, 5개의 공간 외에는 더이상 사용하지 못한다.

즉, array[7] = 10;라고 해주더라도 할당된 크기(범위) 밖이기 때문에 IndexOutBoundsException 에러가 발생한다.

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

다음은 List Interface를 구현하는 클래스들이다.

 

1. ArrayList

Object[] 배열을 사용하여 내부 구현을 통해 동적으로 관리를 한다.

최상위 타입 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근에서 탁월한 성능을 보인다.

하지만 중간의 요소의 삽입, 삭제가 일어날 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적이다.

 

 

2. LinkedList

데이터와 주소로 이루어진 클래스(=노드)를 만들어 서로 연결하는 방식이다.

각 노드는 이전의 노드와 다음의 노드를 연결하는 방식으로 이중 연결 리스트라고 부른다.

즉, 객체끼리 연결하는 방식이다.

요소를 검색해야 할 경우 처음 노드부터 찾고자하는 노드가 나올 때까지 연결된 노드들을 모두 방문해야 한다는 점에서 성능이 떨어진다.

하지만 해당 노드를 삽입, 삭제할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 매우 좋은 효율을 보인다.

 

 

3. Vector

ArrayList와 거의 같다고 보면 된다.

Object[] 배열을 사용하며 요소 접근에서 빠른 성능을 보인다.

원래 Vector는 Collection Framework가 도입되기 전부터 지원하는 클래스이다.

항상 동기화를 지원하는데 이 말은 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 하는 것이다.

그러나 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다.

 

 

* Stack

말 그대로 쌓아올리는 것이다.

LIFO(Last in First Out) 또는 후입선출이라고도 한다.

예를 들어, 짐을 쌓는다고 생각하면, 짐을 쌓을 때 가장 마지막 짐이 가장 위에 있고, 뺄 때는 가장 위의 짐부터 빼게 된다.

가장 대표적인 예시로는 '뒤로가기', '실행취소', '수식 괄호 검사' 등이 있다.

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

스택은 Vector 클래스를 상속 받고 있다.

 

 

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

 

---

 

💬 Queue Interface

큐는 순서가 있는 데이터 기반으로 선입선출, FIFO(First In First Out)을 위해 만들어진 인터페이스이다.

Stack과 많이 비교하는 자료구조이다.

예를 들어, 데이터를 10, 20, 30 순으로 넣었다면 꺼낼 때도 10, 20, 30 으로 나오는 구조이다.

 

위의 Collection 구조를 보면, Queue를 상속하고 있는 Deque(덱)이라는 인터페이스도 있다.

예를 들어, 카드 덱(deck)을 생각하면 되는데 카드를 중간에서 뺄 수 없고, 맨 위에 놓거나, 맨 아래에 놓거나, 맨 위에 것을 빼거나, 맨 아래 것을 뺄 수 있는 것이라 생각하면 된다.

 

Queue는 한쪽 방향으로만(단방향) 삽입, 삭제가 가능하다.

Deque은 Double ended queue라는 의미로 양쪽에서 삽입, 삭제가 가능한 자료구조이다.

head, tail 둘다 접근 가능한 양방향 큐라고 보면 된다.

 

아래는 Queue/Deque Interface를 구현하는 클래스들이다.

 

1. LinkedList

LinkedList는 List(리스트)를 구현하기도 하지만, Deque(덱)도 구현한다.

그리고 Deque Interface는 Queue Interface를 상속받는다.

Deque 또는 Queue를 LinkedList처럼 Node 객체로 연결해서 관리하길 원한다면 LinkedList를 사용하면 된다.

 

 

2. ArrayDeque

ArrayList처럼 Object[] 배열로 구현되어 있는 것은 ArrayDeque 이다.

물론 LinkedList와 ArrayDeque 둘 다 Deque을 구현하고 있고, Deque은 Queue를 상속받기 때문에 Queue로도 쓰일 수 있다.

 

 

3. PriorityQueue

단어 해석 그대로 '우선순위 큐'다

PriorityQueue는 '데이터 우선순위'에 기반하여 우선순위가 높은 데이터가 먼저 나오는 원리다.

따로 정렬방식을 지정하지 않는다면 낮은 숫자가 높은 우선순위를 갖는다.

쉽게 생각하면 정렬메소드인 sort()와 같은 순서로 데이터 우선순위를 갖는다는 의미다.

 

PriorityQueue는 주어진 데이터들 중 최댓값, 혹은 최솟값을 꺼내올 때 매우 유용하게 사용될 수 있다.

다만, 사용자가 정의한 객체를 타입으로 쓸 경우 반드시 Comparator 또는 Comparable을 통해 정렬 방식을 구현해주어야 한다.

 

 

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

 

---

 

💬 Set Interface

말 그래도 '집합'이다.

Set의 특징

1. 데이터를 중복해서 저장할 수 없다.

2. 입력 순서대로의 저장 순서를 보장하지 않는다.

 

다만, LinkedHashSet은 Set임에도 불구하고 입력 순서대로의 저장순서를 보장하고 있다.

그러나 데이터를 중복해서 저장할 수 없는 것은 같다.

 

기본적으로 List계열은 index(Node)로 관리하기 때문에 add()같은 메소드를 쓰면 순서대로 저장되었다.

Queue 계열 또한 우선순위 큐(PriorityQueue)를 제외하고는 기본적으로 입력한 순서대로 객체가 연결되어 있다.

하지만 Set의 경우는 일반적으로 입력받은 순서와 상관없이 데이터를 집합시키기 때문에 입력받은 순서를 보장할 수 없다.

 

데이터 중복을 허용하고 싶지 않은데 입력 순서를 보장받고 싶다면 LinkedHashSet을 사용하면 된다.

Set을 상속받고 있는 SortedSet Interface도 있다.

 

Set의 가장 큰 특징은 '중복되는 데이터를 넣지 못한다는 점' 이고,

LinkedHashSet을 제외하고 대부분의 Set은 '입력 순서대로의 저장순서를 보장하지 않는다는 점'이다.

 

아래는 Set/SortedSet Interface를 구현하는 클래스들이다.

 

1. Hashset

입력 순서를 보장하지 않고, 순서도 마찬가지로 보장되지 않는다.

예를 들어, 게임에서 '닉네임'을 만든다거나 아이디를 생성할 때 '중복확인'을 눌러 중복된 닉네임 또는 아이디인지 확인 하는 것이다.

이는 데이터가 정렬되어있을 필요도 없고, 빠르게 중복되는 값인지만 찾으면 되기 때문에 유용한 방법이 될 수 있다.

 

hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다.

즉, Hash 기능과 Set컬렉션이 합쳐진 것이 HashSet이다.

그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나다.

 

 

2. LinkedHashSet

Link + Hash + Set 이 결합된 형태이다.

LinkedList에서 보면 add() 메소드를 통해 요소들을 넣은 순서대로 연결하는데 LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미를 뜻한다.

Set의 경우 기본적으로 입력 순서대로의 저장순서를 보장하지 않아 이를 보완하기 위해 존재하는 것이 바로 LinkedHashSet인 것이다.

 

 

3. TreeSet

HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다.

SortedSet Interface의 이름을 보면 알 수 있듯 이를 구현한 TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 보장한다는 것이다.

 

앞서 PriorityQueue를 생각해보자.

데이터들이 입력한 순서대로가 아닌 값에 따라 정렬되어 Queue에 담아진다.

 

TreeSet은 '중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다.

정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용하다.

 

 

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