글의 목적
자료구조에 대해 기본적인 개념을 공부하고, Java 에서 기본적으로 제공하는 Collections Framework에 대해 공부해보자.
자료구조의 분류
형태에 따른 자료구조를 분류해보면
선형 자료구조, 비선형 자료구조, 집합 자료구조가 존재한다.
선형자료구조
선형 자료구조란 데이터가 일렬로 연결된 형태를 의미한다.
ex) List, Queue, Deque가 존재한다.
비선형 자료구조
비선형 자료구조는 선형 자료구조의 반대다. 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결 된 형태를 생각하면 된다. ex) Graph, Tree가 있다.
집합 자료구조
위 자료구조에 해당하지 않는 것은 집합(set)이 있다. 데이터가 연결 된 형식이 아니라 Table에 가까운 자료구조이다.
Java Collections Framework
Collection Framework은 자바에서 데이터들을 원하는대로 사용할 수 있게 위의 자료구조를 미리 구현해 놓은 것이라고 생각할 수 있다.
Collections의 가장 큰 Interface 로는 List()<> , Queue()<>, Set()<> 으로 이루어져 있다.
#cf1) 분명 이전에도 비슷한 글을 쓰면서 이러한 그림을 보았는데,
자바 및 Framework 공부를 더하고 나서 보니까 조금 더 와닿고
이해가 되는 부분들이 있는 거 같다. 각 자료구조를 직접 구현하면서
특징을 이해해보자#cf2)
Map (key-value) ex) hashmap 의 자료구조들은 자바 Colleiton으로 보지 않는다.
Mapping의 개념 때문인것으로 보인다.
Collection Interface & Map Interface의 호환문제도 존재한다.
1. Collection Interface는 단일 데이터를 처리 & Map은 key value 쌍으로 존재한다.
2. Iterable Interface와 Map 간의 문제도 있다.
Iterable을 돌릴 때, key value중 어느 것을 반복할것인지에 대한 문제가 있다.
Map을 자료구조로 보는 것은 맞으나, 자바에서는 Collection Interface를
상속받지 않기 때문에, 이를 알고 이해하는 것이 좋을 것 같다.
List Interface 구현체 Class
1. ArrayList
Object[] 배열을 사용하면서, 내부 구현을 통해 동적으로 관리한다. 우리가 흔히 사용하는 Primitive 배열[]과 유사한 형태이다.
즉 최상위 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에, 요소 접근에는 탁월하나, 중간의 요소 삽입,삭제가 일어나는 경우, 그 뒤의 요소드은 한칸씩 밀거나 당겨야 하기 때문에, 삽입 삭제에서는 상대적으로 비효율적인 모습을 보인다.
2. LinkedList
데이터와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다. 데이터와 주소로 이루어진 클래스를 Node 라고 하는데, 각 노드는 이전노드와 다음 노드를 연결하는 방식이다. 객체끼리연결한 방식, 요소를 검색해야할 경우 , 첫 노드부터 연결된 노드들을 모두 검색해야하는 단점이 있다. 노드를 삭제 삽입 할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에, 삽입, 삭제에서는 매우 좋은 효율을 보인다.
3. Vector
Collection Framework가 도입되기 전부터 지원하던 클래스 였다. 동기화를 지원한다. 멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다.
4. Stack
Stack은 LIFO(Last In First Out) 구조이고,Stack은 Vector를 상속받고 있고 있다.
Queue/Deque Interface 구현체 Class
Queue Interface는 기본적으로 FIFO 구조를 위해 만들어진 인터페이스이다. Queue를 상속받는 Deque Interface도 있따. Queue난 단방향 삽입 ,삭제가 가능하고, Deque는 양쪽에서 삽입삭제가 가능한 자료구조이다.
-
LinkedList
위의 List<T>Interface에서도 LinkedList가 나온 것을 본 기억이 있을 것이다. LinkedList Class를 보면 queue를 상속받는 Deque Interface도 상속받는 것을 알 수 있다.
Deque , Queue를 LinkedList 연결해서 관리하길 원하면 LinkedList로 구현된 Queue, Deque를 사용하면 된다. -
ArrayDeque
ArrayList 처럼 Object[] 로 구현되어 있는 것은 ArrayDeque이다. 물론 LinkedList 와 ArrayDeque 모두 Deque를 구현하고 있기 때문에 상황에 맞는 것을 사용하면 되겠다. -
PriorityQueue
PriorityQueue 우선순위 큐로 데이터 우선순위에 기반하여 높은 데이터가 먼저 나오는 원리다. 따로 정렬방식을 지정하지않는다면, 낮은 숫자가 높은 우선순위를 갖는다. Collections.sort() 와 같은 순서로 데이터 우선순위를 갖게된다. 사용자 지정 객체 타입을 쓸 경우 반드시 Comparator 또는 Comparable 정렬방식을 구현해주어야 한다.
Set Interface 구현체 Class
Set의 가장 큰 특징은 중복되는 데이터를 넣지 못한다는 점이다.
LinkedHashSet을 제외하고 대부분의 Set은 입력 순서대로 저장순서를 보장하지 않는다.
-
HashSet
가장 기본적인 Set 컬렉션의 클래스인데, 입력 순서를 보장하지 않고, 순서도 보장되지 않는다. hash에의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인할 수 있다. hash 기능과 set컬렉션 기능이 합쳐진 것이다. 삽입,삭제,색인이 빠른 Collection 중 하나다. -
LinkedHashSet
Link + Hash + Set이 결합된 형태로 , 순서를 보장하는 Collection 이다. Set의 경우 기본적으로 입력 순서대로 저장순서를 보장하지 않는다. 이 때, 순서를 보장받고 싶을 때 사용하는 것이 LinkedHashSet 이다. -
TreeSet
TreeSet은 HashSet과 마찬가지로 입력 순서대로 저장 순서 보장하지 않으며, 중복데이터 넣지는 못한다. 특별한 점은 SortedSet Interface를 구현한 구현체이다. 가중치에 따른 순서대로 정렬되어 보장한다. 앞서 PriorityQueue와 마찬가지로, 정렬시킬 수 있다.
자바 Collection 에서 지원하는 자료구조는 다음과 같다.
•ArrayList
•LinkedList
•Vector
•Stack
•Queue(by LinkedList)
•PriorityQueue
•Deque(by LinkedList)
•ArrayDeque
•HashSet
•LinkedHashSet
•TreeSet
앞으로 위의 설명한 자료구조를 직접 구현해보면서, 어떻게 작동하는지 알아보는 글을 작성할 예정이다. 아래 Reference의 블로그 정말 잘 되어 있어서 따라 만들어가면서, 각 자료구조의 특징을 알아보도록 하자.
Reference
👍