자료구조의 분류
자료구조는 Data Structure이라고 합니다. 일련의 일정 타입들의 데이터관계를 나타낸 구성체라고 말 할 수 있습니다.
알고리즘을 효율적으로 풀기 위해, 문제를 해석한 다음 문제에 사용할 자료구조를 선택합니다. 혹은 자료구조를 선택하면, 해당 자료구조에 맞는 효율적인 알고리즘을 선택할 수 있습니다.
문제의 성격에 따라 적절한 자료구조를 선택하고, 그 자료구조의 특성을 최대한 활용할 수 있는 알고리즘을 적용하는 것이 중요합니다.
그렇기 때문에, 표준 라이브러리로 다양한 자료구조를 지원하고 있습니다.
이 글에서는 자바의 자료구조인 Collection에 대해 알아보겠습니다.
자료구조는 보통 다음과 같이 선형자료구조와 비선형 자료구조로 나눕니다.
Linear Data Structure
- 데이터가 일렬로 연결된 형태
- ex ) List, Queue, Deque
Nonlinear Data Structure
- 선형 자료구조의 반대
- 각 요소가 여러개의 요소와 연결된 형태
- 그래프, 트리
Set
Set은 보통 집합자료구조로 봅니다. 집합은 데이터가 연결된 형식이 아닙니다.
- Table에 가까운 자료구조
Java Collections FrameWork
Collection은 데이터의 그룹을 의미합니다. 자바에서 컬렉션은 객체들의 모임을 나타내고, 자바의 컬렉션은 다양한 자료구조를 통합하여 다루기 위한 인터페이스와 클래스를 포함합니다.
FrameWork은 직관적으로 단어를 이해한다면, 틀(뼈대)라고 생각하면 됩니다. 즉, 어떠한 문제를 해결하기 위한 뼈대가 되는 기본구조를 의미합니다.
즉, Java Collections FrameWork는 일정타입의 데이터들을 쉽게 관리할 수 있도록 표준화하여 지원하는 자료구조의 기본구조, 표준화된 API집합을 의미합니다.
Collection들은 인터페이스로 나누어져 있습니다.
인터페이스는 크게 List, Queue, Set으로 나누어져 있고, 각 인터페이스별로 클래스로 구현되어있습니다.
그림을 보고 설명하면, List, Queue, Set 세가지 형태에 따른 자료구조들이 있고, Queue, Set 인터페이스들이 조금 더 구체화되어, Deque, SortedSet이라는 형태에 따른 자료구조가 있습니다.
그리고, 형태에 따른 자료구조들이 각각 구현이 되어 class으로 제공됩니다.
하늘색 부분이 구현된 자료구조라고 말 할 수 있습니다.
List
List 인터페이스는 대표적인 선형자료구조로 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스입니다.
일반적인 primitive타입의 배열은 생성 시에 크기가 고정되므로, 비용이 떨어집니다.
이 점을 보완하여, List를 통해 구현된 클래스들은 동적크기를 갖으며 배열처럼 사용할 수 있습니다.
< List 인터페이스를 구현하는 클래스 >
1. ArrayList
2. LinkedList
3. Vector
1. ArrayList
ArrayList는 내부적으로 Object타입의 배열을 사용하여 데이터를 저장합니다.
따라서, 모든 자바 클래스의 인스턴스를 저장할 수 있고, 배열의 특성 상 특정 인덱스의 요소를 접근하는것은 매우 빠릅니다.
이것은 ArrayList도 마찬가지로 적용되기 떄문에, 배열에서 해당 인덱스의 참조값을 바로 가져와서 사용할 수 있기 때문에 요소접근에 탁월한 성능을 보입니다.
그러나, 배열에서 중간요소의 삽입, 삭제가 일어나는 경우, 그 뒤의 요소들은 한칸씩 밀거나 당겨야 하기 때문에 삽입, 삭제 측면에서는 비효율적입니다.
2. LinkedList
LinkedList는 데이터와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식입니다.
이 클래스를 Node라고 말 하는데, 각 노드는 이전의 노드와 다음의 노드를 연결하는 (Doubly Linked List)의 구조로 이루어져 있습니다.
객체끼리 연결되어있다보니, 요소를 검색하려면, 찾으려는 요소가 나올 떄 까지 연결된 노드들을 전부 방문해야 하기 때문에 요소 접근할떄는 성능이 떨어지지만, 노드를 삭제, 삽입하는 경우에는 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제 측면에서는 효율적입니다.
3. Vector
Vector는 기본적으로 ArrayList와 동일하다고 보면 됩니다. Vector는 항상 동기화를 지원합니다. 즉 여러 쓰레드가 동시에 데이터에 접근하려면 순차적으로 처리하게 합니다. 그렇다보니, 멀티쓰레드에서는 안전하지만, 단일쓰레드에서도 동기화를 지원하기 때문에 ArrayList보다는 성능이 느립니다.
< Stack >
- LIFO
- Vector클래스를 상속받고 있고, 스택 클래스의 메소드들도 모두 Vector클래스의 메소드를 이용하여 구현되고 있어 크게 다를건 없습니다.
/*객체 생성 코드
T: 객체 타입 */
ArrayList<T> arraylist = new ArrayList<>();
LinkedList<T> linkedlist = new LinkedList<>();
Vector<T> vector = new Vector<>();
Stack<T> stack = new Stack<>();Queue
Queue 인터페이스는 선형자료구조로 주로 순서가 있는 데이터를 기반으로 FIFO 를 위해 만들어진 인터페이스입니다.
예를들어, a-b-c-d-e 순서로 데이터를 넣었다면(push), a-b-c-d-e 순서로 데이터를 추출하는(poll) 구조입니다.
a: head e:tail 이라고 부릅니다.
Queue를 상속하고 있는 Deque 인터페이스에 대해 알아봅시다.
Deque 인터페이스는 Double Ended Queue의 약자로 Queue는 한쪽 방향으로만 삽입, 삭제가 가능한 반면, 덱은 queue의 특성을 확장한 형태로 양쪽에서 삽입삭제가 가능합니다.
< Queue / Deque 인터페이스를 구현하는 클래스 >
1. LinkedList
2. ArrayDeque
3. PriorityQueue
LinkedList는 List를 구현하기도 하지만, Deque도 구현합니다. 그리고 Deque Interface는 Queue Interface를 상속받습니다.
즉, LinkedList는 효자이다. List, Deque, Queue 세가지 용도로 사용됩니다.
객체를 Node로 관리하길 원한다면, LinkedList를 사용하면 되고, 객체를 Object타입의 배열로 관리하고 싶으면 ArrayDeque 를 사용하면 됩니다.
그리고 Deque는 Queue를 상속받기 때문에, LinkedList, ArrayDeque 둘 다 Queue로도 사용할 수 있습니다.
1. LinkedList
자바 컬렉션에서 일반적인 큐를 사용하고 싶다면, LinkedList으로 생성하여 Queue를 선언하면 됩니다. 덱도 마찬가지 입니다.
Queue<T> queue = new LinkedList<>();
Deque<T> queue = new LinkedList<>();2. ArrayDeque
객체를 Object타입의 배열로 관리하고 싶으면 ArrayDeque 를 사용하면 됩니다.
3. PriorityQueue
큐의 원리는 선입선출입니다. PriorityQueue는 데이터 우선순위에 기반하여 우선순위가 높은 데이터가 먼저 나오는 원리입니다. 따로 지정하지 않는다면, 크기 순서로 오름차순으로 우선순위를 갖습니다.
최댓값, 최솟값 꺼내올때 유용하게 사용됩니다.
Set
Set은 집합입니다. set의 주요 특징 두 가지는 아래와 같습니다.
- 데이터를 중복해서 저장할 수 없습니다.
- 입력 순서대로의 저장순서를 보장하지 않습니다.
List계열은 인덱스(노드)로 관리하기 때문에 순서대로 저장됩니다. Queue계열 또한, 기본적으로 입력한 순서대로 객체가 연결되어 있습니다.
이와 달리, Set은 수학에서의 집합처럼 데이터를 집합으로 다루기 때문에, 일반적으로 순서를 얘기하지 않습니다.
일반적으로 라는 단어를 붙인 이유는, 순서를 말하지 못하는 불편함을 해소하고자 순서를 보장하기 위해, LinkedHashSet이 존재하기 때문입니다.
<Set/SortedSet Interface를 구현하는 클래스>
- HashSet
- LinkedHashSet
- TreeSet
1. HashSet
가장 기본적인 Set컬렉션의 클래스
Hash 에 의해 데이터의 위치를 특정시켜 데이터를 빠르게 찾아낼 수 있습니다.
중복확인을 위해 사용됩니다.
- 중복 허용 X
- 입력 순서 보장 X
2. LinkedHashSet
Set 의 불편함을 해소하고자, 중복을 허용하지 않으면서 순서를 보장받기 위해 존재하는 클래스입니다.
- 중복 허용 X
- 입력 순서 보장 O
- LRU(Least Recently Used)알고리즘에서 LinkedHashMap을 자주 이용함
3. TreeSet
트리구조는 데이터를 일정 순서에 의해 정렬합니다. Tree의 특성과 Set의 중복값 방지 기능을 추가하여 만든 자료구조입니다.
즉, TreeSet 은 데이터를 중복하지 않으면서, 특정 가중치에 따른 순서대로 데이터의 정렬을 보장합니다.
정리하자면, TreeSet은 특정규칙에 의해 정렬된 형태의 집합을 사용하고 싶을때 사용됩니다.
- 중복 허용 X
- 입력 순서 보장 X
- 가중치에 의한 데이터의 정렬 O
- 특정 구간의 집합요소들을 탐색할 때 매우 유용
/*객체 생성 코드
T: 객체 타입 */
HashSet<T> hashset = new HashSet<>();
LinkedHashSet<T> linkedhashset = new LinkedHashSet<>();
TreeSet<T> treeset = new TreeSet<>();
SortedSet<T> treeset = new TreeSet<>();