[Java] Collections Framework

컬렉션 프레임웍

컬렉션 프레임웍 : 데이터를 저장하는 클래스들을 표준화한 것.
데이터를 다루는데 필요한 다양한 클래스들을 제공.

컬렉션 프레임웍 핵심 인터페이스

컬렉션 프레임웍은 컬렉션데이터 그룹을 크게 3가지 타입이 존재한다고 인식.

→ 각 컬렉션을 다루는데 필요한 기능을 가진 3가지 인터페이스를 정의함. 인터페이스 List와 Set의 공통 부분을 뽑아 Collection을 추가 정의함. (List, Set은 Collection을 상속받음)

• List - 순서 o 중복 o
  • ArrayList, LinkedList, Stack, Vector
• Set - 순서 x 중복 x .집합.
  • HashSet, TreeSet
• Map - 순서 x 중복 - 키는 x 값은 o. dictionary
  • HashMap, TreeMap, Hashtable, Properties

컬렉션 프레임웍의 모든 클래스들은 위 3개중 하나를 구현하고 있음. 클래스 이름도 포함

• Vector, hashtable 같은 기존의 클래스들은 이전거라 이름 규칙이 다름. 가능하면 사용하지 말자.

Map에서 기존에 저장되어 있는 데이터와 중복된 키를 저장하면 마지막 값으로 덮어씌움.

Map인터페이스 안에 Entry인터페이스 정의되어 있음. Map.Entry인터페이스

of(), copyOf()

List, Set, Map을 생성해서 반환하는 팩토리 메서드.

of()는 가변인자와 오버로딩 이용. ()안에 여러 객체 넣을 수 있음.

List list = List.of("aaa","bbb","ccc");
Set set = Set.of("aaa","bbb","ccc");
Map<String, Integer> map = Map.ofEntries(
    Map.entry("apple", 1),
    Map.entry("banana", 2),
    Map.entry("cherry", 3)
);

copyOf()는 매개변수로 컬렉션을 받아서 복사해 반환. - 반환된 컬렉션은 얕은 복사로 복사된 것. 읽기 전용.

List copy = List.copyOf(list);
copy.add("ddd"); // error. 읽기만 가능.
Set copy = Set.copyOf(set);
Map<String, Integer> copy = Map.copyOf(map);

ArrayList

List를 구현 → 데이터 저장순서 유지, 중복 허용.

기존의 Vector를 개선한 것으로 거의 동일. 주로 ArrayList사용.

• Vector : 동기화 o
• ArrayList : 동기화 x

안에 객체배열이 있고, 관리하기 위해 필요한 메서드들이 있음.

Object배열을 이용해 데이터를 순차적으로 저장.

웬만하면 ArrayList써야함. 배열 대신

ArrayList list = new ArrayList(10);
list.add(1); // list.add(new Integer(5)); 원래 객체배열이라 정수형 안되지만 오토박싱됨.

ArrayList를 생성할 때, 실제 저장할 개수보다 약간 여유있는 크기가 좋다 → 지정한 크기보다 더 많은 객체를 저장하면 자동으로 크기가 늘어나긴 하지만 처리시간이 많이 소요됨.

ArrayList나 Vector는 데이터를 읽어오고 저장하는데는 효율적이지만, 용량을 변경해야할 경우 새로 만들어서 복사해야하기 때문에 효율이 떨어짐.

배열의 중간에 위치한 객체를 추가하거나 삭제하는 경우, 다른 데이터 위치를 이동시켜줘야 하기 떄문에 오래걸림.

LinkedList

배열의 단점 보완.

• 크기 변경 불가. 새로운 배열을 생성해 복사해야함.
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸림.

배열은 모든 데이터가 연속적으로 존재하지만 LinkedList는 불연속적인 데이터를 연결한 형태임.

LinkedList의 각 요소(node)
class Node{
	Node next; // 다음 요소의 주소 저장.
	Object obj;  // 데이터 저장.
}

삭제 → 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경.

단방향. 건너뛰는게 안되고 뒤로가기도 안됨. 이동이 불편함.

뒤로가기 안되는 문제 해결 → 더블 링크드 리스트

DoubleLinkedList. 이중 연결. 실제 자바의 LinkedList는 더블 링크드 리스트임.

class Node{
	Node next; // 다음 요소의 주소 저장.
	Node previous; // 이전 요소의 주소 저장.
	Object obj;  // 데이터 저장.
}

이걸 향상시킨 더블 써큘러 링크드 리스트도 있음. 처음과 끝을 연결한 것.

순차적으로 추가/삭제하는건 ArrayList가 빠르고 중간에 추가/삭제 하는건 LinkedList가 빠름

배열의 주소

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기.

링크드리스트는 불연속적으로 위치한 요소들이 연결된거라 처음부터 n번째까지 따라가야함.

Stack과 Queue

스택 : 마지막에 저장한 데이터를 먼저 꺼냄. LIFO. 배열 적합-ArrayList.

큐 : 먼저 저장한 데이터를 먼저 꺼냄. FIFO. LinkedList 적합.

Stack은 클래스
컬렉션 프레임웍 이전에 존재해서 ArrayList가 아닌 Vector를 상속받아 구현.

Queue는 인터페이스임.
→ Queue q = new Queue(); 불가능.
→ 구현해놓은 클래스들 중에 골라 사용. 13개 종류 있음. Queue q = new LinkedList();

활용

• 스택 : 수식 계산, 수식 괄호 검사, 웹브라우저 뒤로/앞으로, 워드프로세서의 undo/redo
• 큐 : 최근 사용 문서, 인쇄작업 대기 목록, 버퍼

PriorityQueue

우선순위 큐. Queue인터페이스의 구현체 중 하나. 저장 순서 상관없이 우선순위 높은 것부터 꺼냄. 저장공간으로 배열 사용. 각 요소를 힙(자료구조)의 형태로 저장. null저장 불가.

Deque(덱,디큐)

큐의 변형으로 한쪽 끝으로만 추가/삭제하는 큐와 달리 양쪽 끝에 추가/삭제 가능. 스택 + 큐

Deque의 조상은 Queue구현체 -ArrayDeque, LinkedList

Iterator

컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스.
Iterable은 Iterator를 반환하는 메서드를 정의한 인터페이스.

• Iterator

  하나씩 꺼내. 없을 때까지. 하지만 총 몇개 있는진 관심 없음. 그냥 달라고만 함. 단방향

• Iterable

  Iterator 제공. Collection은 Iterable의 자손임. List, Set을 구현한 클래스는 iterator()가 정의되어 있음. 컬렉션의 읽기 표준화. 컬렉션의 종류와 관계없이 같은 방식으로 모든 요소 조회 가능.

boolean hasNext() // 읽어올 요소 있니?
Object next() // 다음 요소 읽어옴
void remove() //next()로 읽어온 요소 삭제. next먼저 호출해야함.

둘다 인터페이스임

ListIterator : 양방향. 잘 안씀. Iterator에 양방향 조회 기능 추가(List를 구현한 경우에만 사용가능)

Enumeration : Iterator의 구버전.

Map인터페이스를 구현한 컬렉션 클래스는 키와 값을 쌍으로 저장하고 있기 때문에 iterator()를 직접 호출할 수 없고 keySet()이나 entrySet()과 같은 메서드를 통해 키와 값을 각각 따로 Set의 형태로 얻어 온 후에 다시 iterator()를 호출해야 호출시 Iterator를 얻을 수 있다.

Iterator it = map.entrySet().iterator();

Arrays

유틸 클래스

• Objects
• Arrays
• Collections

배열을 다루는데 유용한 메서드가 정의되어 있음.

배열 복사 - copyOf(), copyOfRange()

int[] arr = {0,1,2,3,4};

int[] arr2 = Arrays.copyOf(arr, arr.length); //[0,1,2,3,4]
int[] arr3 = Arrays.copyOf(arr, 7); // [0,1,2,3,4,0,0]

int[] arr4 = Arrays.copyOfRange(arr, 2, 4); // [2,3]
int[] arr5 = Arrays.copyOfRange(arr, 0, 7); // [0,1,2,3,4,0,0]

배열 채우기 - fill(), setAll()

int[] arr = new int[5];
Arrays.fill(arr, 9); // [9,9,9,9,9]
Arrays.setAll(arr, () -> (int)(Math.random()*5) +1); // [1,4,2,3,3]

배열의 정렬과 검색 - sort(), binarySearch()

int[] arr = {3,2,0,1,4};
int idx = Arrays.binarySearch(arr,2);  // idx = -5. 잘못된 값. **배열이 정렬되어 있어야 사용가능.**
Arrays.sort(arr);
int idx = Arrays.bianrySearch(arr,2); // idx = 2

이진탐색(binarySearch)은 정렬이 되어 있는 경우에만 사용 가능.

배열의 비교와 출력 - toString(), equals(), compare(), mismatch()

• toString(): 배열의 모든 요소를 문자열로 출력.
  • 다차원 배열 : deepToString()
• equals(): 두 배열에 저장된 모든 요소를 비교.
  • 다차원 배열 : deepEquals()
• compare(): 두 배열을 비교. 정렬을 목적으로 비교함.
• mismatch(): 두 배열이 일치하지 않는 첫 요소의 index반환. 두 배열이 같으면 -1반환.

int i = Arrays.compare(new int[][1], new int[]{1,2}); // -1
int idx = Arrays.mismatch(new int[][1], new int[]{1,2}); // 1

배열을 List로 변환 - asList(Object… a)

List list = Arrays.asList(new Integerp[]{1,2,3,4,5}); // [1,2,3,4,5]
List list = Arrays.asList(1,2,3,4,5); //[1,2,3,4,5]
배열을 List에 담아 반환. asList가 반환한 리스트의 크기 변경 불가.(추가/삭제 불가). 값 수정은 가능.

크기 변경하고 싶으면)
List list = new ArrayList(Arrays.asList(1,2,3,4,5));

parallelxxx(), spliterator(), stream()

• parallelxxx: 여러 쓰레드가 작업을 나누어 처리하도록 함. (빠른 결과를 얻기 위해)
• spliterator(): 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환.
• stream(): 컬렉션을 스트림으로 변환.

Comparator와 Comparable

비교 기준 제공.

Arrays.sort()를 하면 컴퓨터가 알아서 정렬해주는 것 같지만 사실 Character클래스의 Comparable의 구현에 의해 정렬된 것.

두가지 모두 인터페이스로, 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있다.

기본적으로 오름차순으로 정렬하도록 되어있음.

Comparable을 구현한 클래스는 정렬이 가능함.

• Comparable : 기본 정렬기준을 구현하는데 사용.
• Comparator : 기본 정렬기준 외에 다른 기준으로 정렬할 때 사용.

배열 정렬할 때도 정렬 기준 안주면 String의 Comparable에 의한 정렬을 수행함.

Comparator지정해주지 않으면 저장하는 객체가 구현한 comparable에 의해 정렬된다.

public interface **Comparator** {
	int **compare**(Object o1, Object o2);  // o1,o2비교
	boolean equals(Object obj);
}
public interface **Comparable** {
	public int **compareTo**(Object o); // 자기 자신과 o비교
}

HashSet

set인터페이스를 구현한 가장 대표적인 컬렉션.

중복x 순서x. 정렬 안됨.

중복 x - 객체 기준. String 1이랑 Integer 1은 다른 객체 → 중복으로 간주 x

Object[] arr = {"1",new Integer(1),"2","2","3","3","3"};
Set set = new HashSet();

for(int i=0; i < arr.length; i++){
	set.add(arr[i]);
}
print // [1,1,2,3]

중복제거 + 순서 유지하고 싶다면 → LinkedHashSet 사용.

TreeSet

이진 탐색 트리의 형태로 데이터를 저장하는 컬렉션 클래스. LinkedList의 변형.

• 이진 트리 - 자식이 최대 2개

  class TreeNode {
  	TreeNode left;
  	Object element;
  	TreeNode righr;
  }

  • 이진 탐색 트리 - 이진트리인데, 왼쪽에 작은값, 오른쪽에 큰 값 저장.

Set인터페이스를 구현했으므로 중복된 데이터 저장 x. 정렬된 위치에 저장하므로 저장 순서 유지 x. 정렬에 유리

정렬되어 있기 때문에 단일값 검색과 범위 검색이 빠름. 데이터 추가/삭제시 링크드리스트보다 오래걸림. but 검색과 정렬기능이 더 뛰어남.

트리 읽는 법

• preorder 루 왼 오
• inorder → 정렬된 결과 왼 루 오
• postorder 왼 오 루
• level

HashMap과 Hashtable

HashMap : 해싱을 이용한 자료구조.

Hashtable은 HashMap의 구버전 느낌. HashMap사용하도록.

키와 값을 각각 Object타입으로 저장함. 하지만 키는 주로 String을 사용.

키는 유일, 값은 중복 가능.

해싱 : 해시함수를 이용한 읽고 쓰기. 해시함수는 데이터가 저장되어 있는 곳을 알려줌.

• HashSet, HashMap, Hashtable

TreeMap

이진검색트리의 형태. 키와 값의 쌍으로 이루어진 데이터 저장.

검색과 정렬에 적합.

대부분의 검색에선 TreeMap보단 HashMap이 띄어남. 범위검색이나 정렬이 필요한 경우 TreeMap사용.

Properties

Hashtable을 상속받아 구현함.

키,값 → string, string

주로 애플리케이션의 환경설정과 관련된 속성을 저장하는데 사용됨.

데이터를 파일로부터 읽고 쓰는 편리한 기능 제공.

Collections

유틸 클래스. 컬렉션과 관련된 메서드 제공.

Vector - 동기화 o / ArrayList - 동기화 x

무조건 동기화하면 비효율적이니까 동기화 안하게 하고 대신 메서드 제공해서 필요한 경우에만 동기화

변경불가 컬렉션 만들기 - unmodifiablexxx() 읽기만 가능하게.

한 종류의 객체만 저장하는 컬렉션 만들기 - checkedxxx()

ArrayList는 Object타입을 다 받기 떄문에 각 타입을 따로 검사하지 못함 → checked로 컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한. → 이후 지네릭스 도입됨. T 하나의 타입. 뭔진 모르지만 여러개가 아니라 하나의 타입임.