자료구조) Java Collection Framework (List, Set, Map)

알고리즘을 풀 때 보통 문제의 의도를 해석한 뒤에 적합한 자료구조를 선택합니다. 

적절한 자료구조를 선택하여 알고리즘을 풀면 효율적으로 풀 수 있기때문에 자료구조를 정리해보려고 합니다.

---

자료구조의 분류

• 선형 자료구조(Linear Data Structure) : 데이터가 일렬로 연결된 형태. ex) 배열, 리스트, 큐, 덱
• 비선형 자료구조(Nonlinear Data Structure) : 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결된 형태. ex) 그래프, 트리
• 집합(Set) : 원소라는 구별되는 객체들이 연관되어 모인 것. 서로 다른 연관된 원소들의 순서 없는 모임.

 

Java Collection Framewrok(JCF)

---

List, Set, Map 인터페이스의 특징

 

---

List Interface

• ArrayList - 요소 접근에서 상당히 빠르고 크기를 마음대로 조절할 수 있는 배열입니다.
• LinkedList - 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 빠른 성능 보장합니다. 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰입니다.
• Vector - 기본적으로 ArrayList와 비슷한데, 동기화를 지원합니다. 즉 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하기 때문에 멀티쓰레드에서 유용하지만, 단일 쓰레드에서는 성능이 느립니다.
• Stack - LIFO(Last In First Out). 벽돌을 쌓아 올리는 것과 비슷합니다.  마지막에 쌓은 벽돌이 맨 위에 있고 벽돌을 제거 할 때 맨 위의 벽돌부터 제거해야 합니다. Vector 클래스를 상속 받습니다.

 

Queue/Deque Interface

• LinkedList - List 인터페이스 뿐만 아니라 사실상 3가지 용도로 사용될 수 있습니다. List, Deque, Queue
• ArrayDeque - 동기화가 안됩니다. 즉 멀티 쓰레드에서 동시 접속 할 수 없습니다. Stack과 LinkedList보다 빠릅니다.
• PriorityQueue - 데이터 우선순위에 따라 우선순위가 높은 데이터가 먼저 나옵니다. 정렬을 하지 않으면 낮은 숫자가 높은 우선순위를 갖습니다. 최댓값, 최솟값 문제에 유용합니다.

Set Interface

• HashSet - 가장 빠른 임의 접근 속도. 순서를 전혀 예측 불가입니다.
• LinkedHashSet - 추가된 순서, 또는 가장 최근에 접근한 순서대로 접근 가능합니다. 중복은 허용하지 않으면서 순서는 보장받고 싶을때 사용합니다.
• TreeSet - 데이터의 가중치에 따른 순서대로 정렬되어 보장됩니다. 정렬된 순서대로 보관하며 정렬 방법을 지정할 수 있습니다.

 

Map Interface

• HashMap - 중복 허용 X, 순서 보장 X, 키와 값으로 null 허용합니다.
• Hashtable - HashMap 보단 느리지만 동기화가 지원됩니다. 키와 값으로 null 허용 X
• TreeMap - 정렬된 순서로 키/값 쌍을 저장하므로 빠른 검색 가능. 저장시 오름차순으로 정렬 하기 때문에 저장시간 다소 오래 걸립니다.
• LinkedHashMap - Map에 있는 엔트리들의 연결 리스트를 유지되므로 입력한 순서대로 반복 가능합니다.

---

 

 

References

st-lab

Java-Coleection 개요

공대인들이 직접쓰는 컴퓨터공부방