JAVA 자료구조

Collection

• Iterable 인터페이스 확장
• add(), addAll()
• contains(), containsAll(), isEmpty(), equals(), size()
• clear(), remove(), removeAll()

 

List 인터페이스

• 각 데이터에 대한 위치 존재 (순서가 있음)
• 데이터 중복 허용
• 순서대로 들어오는 데이터에 유리
• Collection 인터페이스 확장
• ArrayList, LinkedList, Vector, Stack ...

ArrayList
- 배열 !
- 중간 인덱스 요소 삭제 시 다음 인덱스의 요소들이 한 칸씩 앞으로 이동

Vector
- ArrayList와 동일한 기능
- 동기화 : 멀티쓰레드 환경에서 안전 / 성능 저하 발생 가능

LinkedList
- 포인터를 통해 링크 체인 형태로 객체 관리
- 중간 인덱스 요소 삭제 시 링크를 끊고 연결하는 작업을 통해 해당 인덱스 번호는 비어있게 되지만 빈 공간 없이 관리됨
- 삽입 삭제의 빈도가 높은 경우 유리

Stack
- Vector 클래스 상속받음
- LIFO(후입선출) 시 유리하지만 상황에 따라 ArrayDeque와 Stack 중 선택해 사용하기
* ArrayDeque : 성능 빠름. 동기화가 없어 멀티쓰레드 환경에서 안전하지 않음
* Stack : 성능 저하 발생 가능. 동기화되어 멀티쓰레드 환경에서 안전함

 

 

Set 인터페이스

• 데이터 위치 지정 x (순서 없음)
• 중복 허용 x (null도 1개까지만 저장됨)
• 중복된 데이터를 없애고 유일한 값만을 뽑을 경우 유리
• contains() ≫ 데이터가 포함되어 있는지를 확인할 때 유리
• Collection 인터페이스 확장
• HashSet, TreeSet ...

HashSet
- 순서 없이, 중복 없이 데이터 저장

TreeSet
- Comparator를 통해 비교되어 삽입되는 값이 정렬된 자리로 들어감

SortedSet
- 인터페이스, 구현체는 없음
- TreeSet을 통해 정렬된 리스트에서
* headSet() : 가장 작은 값부터 인자값 직전까지의 요소들을 셋으로 리턴
* tailSet() : 가장 큰 값부터 인자값을 포함한 요소들을 셋으로 리턴
* subSet() : 인자값 A, B 사이의 요소들을 셋으로 리턴 (A 포함 / B 미포함)
* first() : 가장 작은 값
* last() : 가장 큰 값

	SortedSet<Integer> sortedSet = new TreeSet<>();
        
        // 요소 추가
        sortedSet.add(5);
        sortedSet.add(1);
        sortedSet.add(3);
        sortedSet.add(7);
        sortedSet.add(2);

        // 정렬된 요소 출력
        System.out.println("SortedSet: " + sortedSet);

        // headSet() 사용 예시
        SortedSet<Integer> headSet = sortedSet.headSet(5);
        System.out.println("headSet(5): " + headSet); // 5보다 작은 요소들

        // tailSet() 사용 예시
        SortedSet<Integer> tailSet = sortedSet.tailSet(3);
        System.out.println("tailSet(3): " + tailSet); // 3 포함, 3 이상 요소들

        // subSet() 사용 예시
        SortedSet<Integer> subSet = sortedSet.subSet(2, 5);
        System.out.println("subSet(2, 5): " + subSet); // 2 포함, 5 직전까지의 요소들

        // 가장자리 요소 접근
        Integer firstElement = sortedSet.first();
        Integer lastElement = sortedSet.last();
        System.out.println("First Element: " + firstElement); // 가장 작은 값
        System.out.println("Last Element: " + lastElement);   // 가장 큰 값

 

 

Queue 인터페이스

• 데이터를 순차적으로 처리하기 위한 인터페이스
• FIFO(선입선출) 구조
• 데이터가 들어온 순서대로 빨리 처리할 때 유리
• Collection 인터페이스 확장. Collection 메소드 사용 권장되지 않음
• offer() : 데이터 삽입
• poll() : 가장 앞의 데이터를 꺼내고 삭제
• peek() : 가장 앞의 데이터를 보여줌
• ArrayDeque, LinkedList, PriorityQueue ...

LinkedList
- List 인터페이스 뿐 아니라 Queue, Deque 인터페이스도 구현함
- FIFO(선입선출) 기능에 유리
- 보통 Queue를 위해 LinkedList가 많이 사용됨

PriorityQueue
- 우선순위 큐
- default 오름차순 / Comparator를 통해 정렬할 수 있음
- 정렬된 값을 기준으로 가장 높은 우선순위의 요소부터 처리됨
- 동기화 지원 x : 멀티쓰레드 환경에서 안전하지 않음
- null값 허용 x

 

Deque 인터페이스

• 양쪽 끝에서 모두 요소를 추가하거나 제거할 수 있음
• FIFO(선입선출), LIFO(후입선출) 모두 가능
• List로도 구현할 수 있지만, 다음과 같은 경우에 유리
  • 인덱스를 지정해서 값을 참조해야 하는 연산이 필요하지 않은 경우
  • 양 끝에서 삽입/삭제 연산이 발생하는 경우
  • 높은 빈도의 푸시/팝 연산이 발생하는 경우

 

중간에서 삽입/삭제가 많은 경우 ≫ LinkedList
양끝에서 푸시/팝이 많은 경우 ≫ Deque

 

 

Map 인터페이스

• 중복되지 않는 키-값의 쌍
• key-value 쌍으로 데이터 관리
• key는 중복 불가능 / value는 중복 가능
• 키로 식별 가능한 데이터를 담고, 데이터의 위치와 상관 없이 키값만으로 꺼낼 필요가 있을 때 유리
• Collection 인터페이스를 확장하지 않음
• put() : 데이터 저장
• get() : 키로 데이터 꺼내기
• 부모 인터페이스 존재하지 않음
• HashMap, Hashtable, TreeMap ...

HashMap
- null 키와 null 값 허용
- 저장 순서가 없음
- key는 중복 허용 x / value는 중복 허용
- 동기화 지원 x : 멀티쓰레드 환경에서 안전하지 않음
- 평균적으로 O(1)의 시간복잡도의 빠른 조회, 추가, 삭제 가능

Hashtable
- null 키와 null 값 허용하지 않음
- 저장 순서가 없음
- key는 중복 허용 x / value는 중복 허용
- 동기화 : 멀티쓰레드 환경에서 안전함
- 평균적으로 O(1)의 시간복잡도이지만, HashMap보다 성능이 떨어질 수 있음

TreeMap
- 이진 탐색 트리를 기반으로 함
- 키의 저장 순서가 있음 : default 키 오름차순 정렬, Comparator를 통해 정렬 순서 지정 가능
- null 키 허용하지 않고 null 값은 허용
- 동기화 지원 x : 멀티쓰레드 환경에서 안전하지 않음
- 평균적으로 O(log n)의 시간복잡도의 조회, 추가, 삭제