| 컬렉션이란?
- 자바에서 자료구조를 구현한 클래스를 말한다.
- 컬렉션을 추상적으로 구분한 분류는 크게 아래와 같다.
- 단, 실제 Collection을 상속하는 건 List와 Set, Queue이며 Map은 별도의 인터페이스이다.
- Collections를 통해서 List를 정렬할 수 있으며,
Set이나 Map의 경우 TreeSet과 TreeMap을 쓰면 data가 정렬되어 저장된다.
| 구분 | 하위 클래스 | 중복 | 순서 |
| List | ArrayList, LinkedList, Vector, Stack(Vector 상속) | o | o |
| Set | HashSet, LinkedHashSet, TreeSet | x | - |
| Map | Hashtable, HashMap, LinkedHashMap, TreeMap | key x, value o | - |
| List / Set / Map 코드
import java.util.*;
public class CollectionTest {
public static void main(String[] args) {
// Collections
// ㄴ List, Set, Queue가 상속 / Map은 별도
// 1. List
// : 순서대로 데이터를 저장하기 위한 리스트 (중복o, 순서o)
// : ArrayList, LinkedList, Vector, Stack(Vector 상속)
// A. ArrayList
// 순차적인 추가/삭제는 빠르나 중간에 데이터를 추가/삭제하게 되면 linkedList보다 느리다.
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(4);
arrayList.add(2);
arrayList.add(3);
arrayList.add(1);
arrayList.add(2);
arrayList.add(1);
System.out.println("arrayList = " + arrayList);
// B. LinkedList
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(4);
linkedList.add(2);
linkedList.add(3);
linkedList.add(1);
linkedList.add(2);
linkedList.add(1);
System.out.println("linkedList = " + linkedList);
// 2. Set
// : 중복을 제거하기 위해 사용한다. 수학의 집합과 연관되어 있다. (중복x)
// : HashSet, LinkedHashSet, TreeSet
// A. HashSet
// - 항상 데이터가 정렬되지 않지만 대체로 정렬되어 나옴 (정렬x, 저장순서 유지x)
System.out.print("hashSet : ");
HashSet<Integer> hashSet = new HashSet<>();
hashSet.add(4);
hashSet.add(2);
hashSet.add(3);
hashSet.add(1);
hashSet.add(2);
hashSet.add(1);
Iterator<Integer> hashSetIterator = hashSet.iterator();
while (hashSetIterator.hasNext()) {
System.out.print(hashSetIterator.next() + " ");
}
System.out.println();
// B. LinkedHashSet : HashSet를 상속한다.
// - 기존 데이터의 저장순서가 그대로 유지된다. (정렬x, 저장순서 유지O)
System.out.print("linkedHashSet : ");
LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(4);
linkedHashSet.add(2);
linkedHashSet.add(3);
linkedHashSet.add(1);
linkedHashSet.add(2);
linkedHashSet.add(1);
Iterator<Integer> linkedHashSetIterator = linkedHashSet.iterator();
while (linkedHashSetIterator.hasNext()) {
System.out.print(linkedHashSetIterator.next() + " ");
}
System.out.println();
// C. TreeSet
// - 데이터가 정렬이 되어 출력된다. (정렬O, 저장순서 유지x)
System.out.print("TreeSet : ");
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(4);
treeSet.add(2);
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
treeSet.add(1);
Iterator<Integer> treeSetIterator = treeSet.iterator();
while (treeSetIterator.hasNext()) {
System.out.print(treeSetIterator.next() + " ");
}
System.out.println();
// 3. Map
// : key 과 value가 entry 형태로 저장된다. (Entry가 Map의 내부 인터페이스다)
// : Hashtable, HashMap, LinkedHashMap, TreeMap
// A. HashMap
// : HashTable과 HashMap은 사용면에서 비슷한데 차이점은 아래와 같다.
// : Hashtable은 Thread-safe & key에 null미사용, HashMap은 Thread-safe X & key에 null사용
// - 데이터가 정렬되지 않은 상태로 출력된다 (정렬x, 저장순서 유지x)
System.out.println("=== HashMap === ");
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("고객3", 1000);
hashMap.put("고객2", 2000);
hashMap.put("고객1", 3000);
hashMap.put("고객0", 4000);
for (String key : hashMap.keySet()) {
System.out.println(key + ":" + hashMap.get(key));
}
// B. LinkedHashMap
// - key 데이터의 저장 순서가 유지된다. (정렬x, 저장순서 유지o)
System.out.println("=== LinkedHashMap === ");
LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("고객3", 1000);
linkedHashMap.put("고객2", 2000);
linkedHashMap.put("고객1", 3000);
linkedHashMap.put("고객0", 4000);
for (String key : linkedHashMap.keySet()) {
System.out.println(key + ":" + linkedHashMap.get(key));
}
// C. TreeMap
// - key 데이터가 정렬된다 (정렬o, 저장순서 유지x)
System.out.println("=== TreeMap === ");
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("고객0", 1000);
treeMap.put("고객1", 2000);
treeMap.put("고객2", 3000);
treeMap.put("고객3", 4000);
for (String key : treeMap.keySet()) {
System.out.println(key + ":" + treeMap.get(key));
}
// - Tip : TreeMap의 key 데이터를 내림차순으로 저장하려면?
System.out.println("=== TreeMap Reverse === ");
treeMap = new TreeMap(Comparator.reverseOrder()); // new TreeMap(Comparator)
treeMap.put("고객0", 1000);
treeMap.put("고객1", 2000);
treeMap.put("고객2", 3000);
treeMap.put("고객3", 4000);
for (String key : treeMap.keySet()) {
System.out.println(key + ":" + treeMap.get(key));
}
}
}>> 결과
arrayList = [4, 2, 3, 1, 2, 1]
linkedList = [4, 2, 3, 1, 2, 1]
hashSet : 1 2 3 4
linkedHashSet : 4 2 3 1
TreeSet : 1 2 3 4
=== HashMap ===
고객2:2000
고객1:3000
고객3:1000
고객0:4000
=== LinkedHashMap ===
고객3:1000
고객2:2000
고객1:3000
고객0:4000
=== TreeMap ===
고객0:1000
고객1:2000
고객2:3000
고객3:4000
=== TreeMap Reverse ===
고객3:4000
고객2:3000
고객1:2000
고객0:1000
| Collections.sort
import java.util.*;
class Customer implements Comparable<Customer>{
private int no;
private String name;
public Customer(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public int compareTo(Customer o) {
return this.no - o.no;
}
public void print() {
System.out.println(this.no + "=" + this.name);
}
}
public class CollectionsSortTest {
public static void main(String[] args) {
// Collection에서 Sort를 하는 방식
// A. List를 정렬할 경우 - Collections.sort(List);
// : 오직 List의 경우에만 Collections.sort()를 쓸 수 있다.
// : Map의 Set의 경우 TreeMap, TreeSet을 쓰는 것이 좋다.
List<Integer> list = new ArrayList<>(Arrays.asList(4, 2, 5, 1, 2, 7));
Collections.sort(list);
System.out.println("list = " + list);
// B. 객체를 정렬할 경우 - 객체 내에서 Comparable인터페이스 구현
// (사실 아래의 경우에는 ArrayList를 쓰고 sort를 하기보다 PriorityQueue를 쓰는게 더 효율적이다)
ArrayList<Customer> customers = new ArrayList<>();
for (int i = 0; i < 5; i++) {
int no = (int)(Math.random() * 9999);
String name = "이름없음" + no;
customers.add(new Customer(no, name));
}
Collections.sort(customers);
for (Customer one : customers) {
one.print();
}
}
}>> 결과
list = [1, 2, 2, 4, 5, 7]
1606=이름없음1606
2047=이름없음2047
4702=이름없음4702
6804=이름없음6804
9098=이름없음9098
| 자바 컬렉션들의 시간 복잡도
1. List
| add() | remove() | get() | contains() | |
| ArrayList | O(1) or O(n) | O(1) or O(n) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
2. Set
| add() | contains() | next() | |
| HashSet | O(1) | O(1) | O(h/n) |
| LinkedHashSet | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) |
3. Map
| add() | containsKey() | next() | |
| HashMap | O(1) | O(1) | O(h/n) |
| LinkedHashMap | O(1) | O(1) | O(1) |
| TreeMap | O(1) | O(1) | O(h/n) |
4. Queue
| offer() | peak() | poll() | size() | |
| LinkedList | O(1) | O(1) | O(1) | O(1) |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) |
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) |
[ 참고 및 출처 ]
부트 캠프 강의를 듣고 정리한 내용입니다.
자바 컬렉션의 시간 복잡도
'Language > Java' 카테고리의 다른 글
| JAVA 라이브러리 - Optional<T> 클래스 (0) | 2022.09.15 |
|---|---|
| SOLID 원칙 (0) | 2022.08.29 |
| JAVA 라이브러리 - 제네릭 클래스 (0) | 2022.08.10 |
| JAVA 라이브러리 - 날짜, 시간 관련 클래스(java.util/java.time..) (0) | 2022.08.10 |
| JAVA 라이브러리 - Java.lang 패키지 (0) | 2022.08.08 |
