자바(Java)에서는 다양한 자료구조를 사용자가 쉽게 활용하도록 성능적으로도 우수하며 코딩에 할애하는 시간을 줄일 수 있는 Collection Framework를 제공하고 있다. 이 Collection Framework는 자료를 저장하고 그것을 처리하는 Logic에 대해서 자바(Java)의 설계 원칙과 표준을 적용하여 구현되었다.
1. Collection Framework
Collection Framework는 자료구조와 그에 긴밀히 연관된 알고리즘 학문에서 필요한 다양한 자료구조들을 구조화하여 제공한다. 자료구조에 대해 간략하게 포스팅한 글에서 자료구조의 종류에 대해 언급한 바 있다.
그러한 자료구조들을 자바(Java)에서는 Interface를 구현하여 사용하고 있다. 여기서는 간단히 아래의 그림을 통해 Collection Framework 구조에 대해 살펴보자.
이 그림은 지금부터 알아볼 자료구조의 자바(Java) 내 Collection Framework의 상속 구조도 중 일부만 표현한 것이다. 모든 인터페이스와 추상 클래스의 내용에 대해 깊이 알 필요까지는 없어보이니 몇 가지만 알아보도록 하자.
우선 Collection Framework 구조에서 최상위 인터페이스는 Collection 인터페이스이다.
자료구조로 사용될 Class에서 필요한 주요 기능들이 Collection 인터페이스에 정의되어 있으며, 그 뒤 각각의 필요 기능에 따라 추가적인 인터페이스와 추상 Class를 구현 / 상속하고 있는 것을 확인할 수 있다.
지금의 그림의 모든 내용을 알 필요는 없다. 그저 Collection Framework가 이러한 방식으로 자바(Java)에서 제공되며 그에 따른 다양한 자료구조를 활용할 수 있게 되면 된다.
위의 내용 중 Map<K, V> 라는 인터페이스도 있는데 이 자료구조는 Key - Value 형식으로 구현되는 자료구조로 여타 구조들과 차이가 있어 별도의 인터페이스로 구현된다.
자바(Java)의 Collection Framework에 대해 더 자세히 알고 싶은 경우 다음의 링크에서 문서를 확인하도록 하자
https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html
The Collections Framework
The Collections Framework The collections framework is a unified architecture for representing and manipulating collections, enabling them to be manipulated independently of the details of their representation. It reduces programming effort while increasin
docs.oracle.com
2. 주요 인터페이스의 특징
우선 가장 최상위 인터페이스인 Collection 인터페이스에 대해서 알아보자. 이 인터페이스는 위의 설명과 같이 여타 자료구조의 베이스가 되는 인터페이스 중에서도 최상위에 속하여 각 Collection 객체(자료구조)들을 다루는데 가장 기본적인 동작이 정의되어 있으며, 그것을 메소도로 제공한다.
Collection 인터페이스의 주요 Method를 살펴본다.
| Collection 인터페이스 내 Method | 설명 |
| boolean add(E o) | 해당 collection에 전달된 요소 추가 |
| boolean addAll(Collection<? extends E> c) | 해당 collection에 전달된 collection의 모든 요소 추가 |
| void clear() | 해당 collection의 모든 요소 제거 |
| boolean contains(Object o) | 해당 collection이 전달된 객체 포함 여부 확인 |
| boolean containesAll(Collection<?> c) | 해당 collection이 전달된 collection의 모든 요소 포함하는지 확인 |
| boolean equals(Object o) | 해당 collection과 전달된 객체의 동일 여부 확인 |
| boolean isEmplty() | 해당 collection이 비어있는지 확인 |
| Iterator<E> iterator() | 해당 collection의 반복자(iterator)를 반환 |
| boolean remove(Object o) | 해당 collection의 전달된 객체 제거 |
| boolean removeAll(Collection<?> c) | 해당 collection에 전달된 collection의 모든 요소를 제거 |
| boolean retainAll(Collection<?> c) | 해당 collection에 전달된 collection의 요소한 남김 |
| int size() | 해당 collection의 요소의 크기를 반환 |
| Object[] toArray() | 해당 collection의 모든 요소를 Object 타입의 배열 형태로 반환 |
다음으로 각 List, Set, Queue, Map인터페이스의 특징에 대해서 알아보자
| 인터페이스 | 설명 | 구현된 클래스 |
| List<E> | 순서가 있는 데이터의 집합으로 데이터의 중복을 허용함 | Vector, ArrayList, LinkedList, Stack |
| Set<E> | 순서를 유지하지 않는 데이터의 집합으로 데이터의 중복 비허용 | HashSet, TreeSet |
| Queue<E> | 순서가 있는 데이터 집합이으로 데이터의 중복을 허용함(List와 유사하나 별도의 기능 존재) | PriorityQueue, LinkedList |
| Map<K, V> | 키와 값의 한 쌍으로 이루어지는 데이터 집합, 순서가 없고 키는 중복 허용되지 않으나 값은 중복 가능 | HashTable, HashMap, TreeMap |
3. Collection Class
위의 표에서 볼 수 있듯이, Collection Framework 내 Collection Interface를 구현한 것이 Collection Class이다. 이들은 각각의 사용 방식에 따라 필요한 인터페이스 및 추상 Class를 구현 및 상속하고 있다.
자바(Java)에서 제공하는 다양한 Collection Class 들에 대해서 알아보자.
① HashSet과 TreeSet
Set 인터페이스를 구현한 클래스들로 말 그대로 집합의 자료구조를 사용하기 위한 Class들이다. 이들은 중복된 값을 여러 번 삽입하여도 하나의 해당 값만 보유한 상태를 유지한다. 그렇다면 그 둘의 차이점은 무엇일까? 간단히 다음의 코드를 통해 알아보자.
package com.test;
import java.util.*;
public class SetTest {
public static void main(String[] args){
// HashSet 의 예제
Set<Integer> hashSet = new HashSet<>();
hashSet.add(19);
hashSet.add(7);
hashSet.add(6);
hashSet.add(8);
hashSet.add(3);
Iterator<Integer> iterator = hashSet.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next() + ", ");
}
// 결과 : 3, 19, 6, 7, 8
System.out.println();
// TreeSet의 예제
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(19);
treeSet.add(7);
treeSet.add(6);
treeSet.add(8);
treeSet.add(3);
Iterator<Integer> iterator2 = treeSet.iterator();
while(iterator2.hasNext()){
System.out.print(iterator2.next() + ", ");
}
// 결과 : 3, 6, 7, 8, 19
}
}
위의 결과에서 보이듯이, HashSet은 자료의 순서에 대한 보장을 해주지 않는다.
TreeSet은 HashSet과 달리 SortedSet이라는 인터페이스를 구현하여 Natural Ordering을 지원하기 때문에 위와 같이 정렬되어서 나온다.
TreeSet을 Natural Ordering이 아닌 별도의 순서로 저장하는 방식을 취하고 싶은 경우, Comparator 인터페이스를 구현(참조)하여 인자로써 전달하면 사용 가능하다.
Natural Ordering : 자연스런 정렬을 의미하여, 일반적으로 자바(Java)에선 작은 수에서 큰 수, 사전 순으로 정렬하는 것을 의미한다.
HashSet을 좀 더 설명하면 HashSet은 내부적으로 Hash 알고리즘과 HashMap 인스턴스를 생성해 요소를 저장한다. Map관련 자료구조는 아래에서 추가로 설명한다.
Set 자료구조의 특성 상, 동일한 자료를 중복하여 저장하지 않게 구조가 형성되어 있는데, 그러한 보장을 위해 다음과 같은 과정을 거쳐 저장한다.
1. 해당 요소에서 hashCode() 메소드를 호출해 반환된 해시값으로 검색할 범위를 결정
- 인스턴스가 다르면 Object 클래스의 hashCode()는 다른 값을 반환
2. 해당 범위 내의 요소들을 equals() 메소드로 비교
- 인스턴스가 다르면 Object 클래스의 equals() 는 false 반환
3. 동일한 요소가 있지 않은 경우 해당 자료 저장
동일한 값으로 판정되려면 hashCode와 equals method를 통해 같은 값 / true를 반환해야 한다. 그러한 경우 동일한 것으로 간주된다.
사용자는 인스턴스가 다르더라도 동일한 형태의 member를 갖는 다면 동일한 값으로 취하고 싶을 수 있다. 그런 경우, hashCode() / equals() method들을 사용자가 overriding하여 정의할 필요가 있다.
Hash 알고리즘이란 Hash 함수(Function)을 이용해 데이터를 Table에 저장해서 검색하는 알고리즘이다.
Hash가 필요한 이유는 필요한 요소의 탐색을 용이하도록 하기 위함이다. 자바(Java)에서는 전달된 요소를 Hash 함수를 이용해 특정 code로 변형하여 그 값을 기반으로 배열 Index 내에 연결리스트를 구현하여 저장하고 있다.
즉, 예를 들어, 숫자 1~10 까지있는데 이들을 Hash Table에 저장하기 위해 3으로 나눈 나머지값을 Index로 하여 배열에 저장한다고 생각해보자.
그러면 (1, 4, 7, 10), (2, 5, 8), (3, 6, 9)으로 3개의 부류로 나누어질 것이다. 3으로 나누었을 때 각각 1, 2, 0의 나머지가 남는데, 이 나머지 값을 Index로 하여 배열 내에 연결리스트를 형성해 저장하는 방식인 것이다.
참고로, LinkedHashSet이라는 Class도 있는데 이는 값을 삽입한 순서대로 Set을 구성하는 방식이다. 삽입한 순서가 유지되기를 원하는 경우 사용할 수 있는 Class이다. 이외에도 SortedSet을 구현한 ConcurrentSkipListSet도 있는데 이에 대해서는 Document를 참고하는 것이 좋다.
② Vector, ArrayList, LinkedList, Stack
이 Collection Class들은 List 인터페이스를 구현한 것들이다. 이 중 Vector와 ArrayList는 배열 기반으로 구현된 크기를 조정할 수 있는 List 형태의 자료구조 이다.
List는 배열처럼 여러 개의 값을 저장할 수 있는 자료구조인데, 그 기반을 배열로 사용한 것이다. 배열은 크기를 한 번 할당하면 다시 변경을 할 수 없으나, 이 Class들은 Resizing이 가능한 Logic을 내부적으로 구현하여 동적으로 크기의 변형이 가능하다.
Vector와 ArrayList의 차이는 다음과 같다.
| 주제 | 내용 |
| Thread-Safe (Synchronize) | Vector는 Multi Thread에 안전하다. 즉, Synchronize 기능이 포함되어 한 번에 하나의 Thread만 접근할 수 있다. ArrayList는 그렇지 않아 복수의 Thread가 동시에 접근이 가능하다. |
| Performance(성능) | 성능적으로는 ArrayList가 더 빠르다. non-Synchronize 방식이기 때문에 Vector가 한 번에 하나의 Thread만 수행 가능하여 그에 비해 빠를 수밖에 없다. |
| Resizing | Vector와 ArrayList는 Resizing이 가능하다고 했는데, 이 방식이 다르다. Vector는 현재 가능한 크기를 넘어서 더 값을 넣고자 하면 2배의 크기로 Resizing하고, ArrayList는 50%를 Resizing한다. 즉, Vector가 더 크게 증분한다. |
| 참조 | Vector는 Iterator / Enumeration을 모두 사용해 데이터를 참조할 수 있고, ArrayList는 Iterator만 사용가능하다. |
| 사용성 | Vector는 사실 하위 버전과의 호환을 위해 남아있다. 자바 초기 Collection 모델이며, ArrayList는 버전업 모델이라서 거의 Vector를 쓰지 않는다. |
이 Collection Class를 코드로 사용하면 다음과 같이 사용할 수 있다.
package com.test;
import java.util.*;
public class ListTest {
public static void main(String[] args){
// ArrayList
List<String> al = new ArrayList<>();
al.add("Practice");
al.add("Makes");
al.add("Perfect");
Iterator<String> a_it = al.iterator();
while(a_it.hasNext()){
System.out.print(a_it.next() + " "); // "Practice Makes Perfect"
}
System.out.println();
// Vector
List<String> vl = new Vector<>();
// add도 사용가능한데, add는 boolean을 반환하고 addElement는 반환값이 void이다.
// List 인터페이스 타입으로 선언했기 때문에 타입에 대해 지정해주어야 한다.(add를 쓰면 안해도 된다.)
((Vector<String>) vl).addElement("Vector");
((Vector<String>) vl).addElement("Is");
((Vector<String>) vl).addElement("Slower");
((Vector<String>) vl).addElement("Than");
((Vector<String>) vl).addElement("ArrayList");
Enumeration<String> e = ((Vector<String>) vl).elements();
while(e.hasMoreElements()){
System.out.print(e.nextElement() + " "); // "Vector Is Slower Than ArrayList"
}
}
}
LinkedList는 그렇다면 어떻게 다를까? LinkedList는 ArrayList, Vector와 달리 배열 구조를 기반으로 하지 않는다.
LinkedList의 각 요소들은 하나의 분리된 Object로써 존재하여 그 Object는 Data 부분과 Address 부분으로 구성되어 있다. 각 요소들은 서로 Pointer와 Address를 이용하여 연결되어 있는 방식으로 이러한 요소들을 Node라고 명명한다.
LinkedList는 배열기반 List와 달리 삽입, 삭제에 있어 더욱 우수한 성능을 보여주지만 배열구조 처럼 Index를 이용한 참조가 불가하여 특정 요소를 찾아내기 위해 첫 Node 부터 마지막 Node까지 순환해야 한다는 단점을 갖고 있다.
LinkedList를 이해하기 위해 다음의 그림을 참조하자
위의 그림과 같은 방식을 Doubly Linked List라고 부른다. 양 방향으로 연결되어 있기 때문이다. 실제로 자바(Java)의 LinkedList는 위와 같이 구현되어 있다.
각각의 Node들은 Previous / Next 라는 Pointer를 이용해서 이전 / 다음 Node의 주소값을 참조하여 보유하고 있다. 만약 Previous Pointer가 없다면 그것을 Singly Linked List라고 부른다.
Head / Tail은 제일 처음과 마지막 부분의 Node를 가리키는 것으로 이 두 노드 마저 상호 연결되어 있는 경우를 Circular Linked List(환형 연결 리스트)라고 부른다.
그렇다면 왜 LinkedList가 ArrayList / Vector보다 삽입 / 삭제가 더 성능이 좋은가? 왜냐면 삽입 / 삭제 시 양쪽 노드의 주소값만 변경해주면 되기 때문이다.
ArrayList / Vector는 배열로 이루어져있기 때문에 중간에 특정 요소를 삽입한다면 그 이후의 모든 요소들의 위치를 +1 씩 이동시켜야 한다.(삭제 시엔 -1씩 이동)
그래서 LinkedList의 삽입 / 삭제 시의 성능은 일반적으로 더욱 좋다고 볼 수 있다.
또한, LinkedList는 배열처럼 크기를 선언하는 구조가 아니고 Node를 추가하면 양 방향의 Node의 Pointer만 변경하면 되기 때문에 Resizing이 필요하지 않다.
배열 기반의 List들은 Resizing 시, 새로운 배열을 크기를 증가/감소시켜 생성 후 기존 배열의 값들을 복사해서 삽입하는 방식이 필요하기 때문에 성능에 영향이 있다.
LinkedList의 실제 사용 코드는 다음과 같다.
package com.test;
import java.util.*;
public class LinkedListTest {
public static void main(String[] args){
// LinkedList
List<String> list = new LinkedList<>();
list.add("LinkedList");
list.add("Is");
list.add("Not");
list.add("Based");
list.add("With");
list.add("Array");
Iterator<String> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
}
}
마지막으로 Stack에 대해서 알아보자.
Stack이란 자료구조는 기본적으로 LIFO(Last-In, First-Out) 방식을 취한다. 즉, 요소를 3가지 넣었다면 3번째에 삽입된 요소가 반환 시 제일 먼저 반환되는 방식을 의미한다.
자바(Java)에서는 Stack의 사용성을 구현한 Stack Class를 별도로 제공하고 있으나, 이 Class는 초기 Collection Class로 기존과의 호환성을 위해 유지하고 있는 Class일 뿐이다.
기존의 Stack Class는 또한 Multi-Thread에 안전하도록 구현되어 성능적으로 느린 부분이 있을 수 있다.
현재는 Deque라는 인터페이스를 새로 생성하여 구현된 ArrdayDeque, LinkedList를 통해 구현할 수 있다.
ArrayDeque는 배열 기반이며 LinkedList는 노드간 연결 기반이다. Deque는 양쪽 방향(처음, 끝)에서 요소를 삽입 / 반환이 가능한 자료구조이다. 즉, Stack이라는 자료구조는 기능적으로 LIFO 방식을 취하는 것이 중요하다. 배열이나 연결리스트를 기반으로 모두 만들 수 있다는 의미이다.
다음의 코드를 통해 Stack Class와 ArrayDeque, LinkedList를 이용한 Stack 자료구조 구현을 알아보자.
package com.test;
import java.util.*;
public class StackTest {
public static void main(String[] args){
// Stack Class 사용
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
while(!stack.isEmpty()){
System.out.print(stack.pop() + ", "); // 4, 3, 2, 1
}
System.out.println();
// ArrayDeque를 사용한 구현
Deque<Integer> arrayDeq = new ArrayDeque<>();
arrayDeq.offerFirst(1);
arrayDeq.offerFirst(2);
arrayDeq.offerFirst(3);
while(!arrayDeq.isEmpty()){
System.out.print(arrayDeq.pollFirst() + ", "); // 3, 2, 1
}
System.out.println();
// LinkedList를 사용한 구현
Deque<Integer> linkedDeq = new LinkedList<>();
linkedDeq.offerFirst(1);
linkedDeq.offerFirst(2);
linkedDeq.offerFirst(3);
while(!linkedDeq.isEmpty()){
System.out.print(linkedDeq.pollFirst() + ", "); // 3, 2, 1
}
}
}
Stack의 구조는 LIFO이므로 offerFirst를 통해 앞으로 요소를 밀어넣었다면 뺄 때도 앞에서부터 빼야 한다.
③ PriorityQueue, LinkedList
이들은 Queue 인터페이스를 구현하여 사용하는 Class들이다.
LinkedList는 List 인터페이스와 Queue 인터페이스를 모두 구현하고 있다. Queue라는 것은 Stack과 달리 FIFO(First-In, First-Out) 방식을 취하는 자료구조이다.
이 자료구조 또한 FIFO 방식의 기능을 활용하는 것이 중요한데, 이 자료구조 또한 ArrayDeque, LinkedList를 이용하여 마땅히 구현할 수 있다.
Queue 자료구조에 대한 코드는 상단의 Stack 자료구조를 알아볼 때 사용한 Code에서 offerFirst로 삽입 시, pollLast 방식으로 빼는 것을 사용하면 된다. 따라서 코드는 생략한다.
그런데, 보통 LinkedList를 Queue 인터페이스 타입으로 생성하여 offer / poll 메소드를 사용해 구현하는 경우가 많다.
그렇다면 PriorityQueue라는 것은 무엇일까? PriorityQueue는 특정 우선순위에 있는 요소를 먼저 반환하도록 구현한 자료구조를 의미한다.
Queue는 보통 삽입된 순서대로 반환되는데, 이 순서를 무조건 지키는 것이 아니라 각 요소별로 우선순위가 있어 우선순위가 있는 요소가 먼저 반환되는 방식이다.
이 자료구조는 Heap(힙)이라고도 불린다. 보통 Natural Ordering을 통해서 요소들을 삽입 시마다 정렬되거나 별도로 Comparator 를 구현하여 제공한 뒤 우선순위를 지정할 수도 있다. PriorityQueue의 특성은 다음과 같다.
1) null값을 허용하지 않는다.
2) 비교 불가한 대상을 기반으로 PriorityQueue를 생성해 삽입할 수 없다.
3) 이 Queue의 Head 요소는 특정 우선순위 기반으로 가장 우선하는 요소가 된다.
PriorityQueue 또한 마땅히 배열 / 연결리스트 기반으로 구현은 가능하다. 자바(Java)에서는 배열을 기반으로 해당 Class를 제공하고 있다. 사용방법은 다음의 코드를 확인하여 PriorityQueue의 사용법을 간단히 익혀보자.
package com.test;
import java.util.*;
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(20);
pq.add(15);
pq.add(1);
pq.add(321);
while (!pq.isEmpty()) {
System.out.print(pq.poll() + ", "); // 1, 10, 15, 20, 321
}
}
}
④ HashTable, HashMap, TreeMap
해당 내용은 다음 포스팅에서 추가하도록 하겠습니다.
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조(Java) - Comparable / Comparator (2) | 2020.07.27 |
|---|---|
| 자료구조(Java) - Iteration (0) | 2020.07.26 |
| 자료구조(Java) - Collection Framework 2 (2) | 2020.07.26 |
| 자료구조(Java) - 배열 (0) | 2020.07.24 |
| 자료구조 / 추상자료형 (0) | 2020.07.21 |
