1. Array (배열)
길이가 고정된 값의 나열로 add() 나 delete() 와 같이 값의 추가 / 삭제는 불가
고정된 개수인 Array 는 코딩테스트를 제외하고는 실제로 사용할일은 그리 많지 않지만, List 와 비교로 필요
import java.util.Arrays;
Integer[] integer_array = new Integer[3]; // 길이 기반 Array 선언 (Integer 요소)
Integer[] integer_array = new Integer[]{1, 2, 3}; // 값 기반 Array 선언 (Integer 요소)
System.out.println(integer_array.length);- 간단한 자바 프로그래밍 시 아래와 같이 깔끔하게 만들어 사용하는 것도 가능
Member[] members = {
new Member(1, "Aaron"),
new Member(2, "Baron"),
new Member(3, "Caron"),
new Member(4, "Daron"),
};2. List 인터페이스 구현체 : ArrayList, LinkedList
값이 자유롭게 추가, 수정, 삭제될 수 있는 값의 나열 = add() 등 리스트 변경 메서드 호출 가능
가장 많이 사용하게될 자료구조로 일렬로 나열한 데이터 집합
- 구현체 종류
- ArrayList : 조회 성능 우수
- LinkedList : 삽입 / 삭제 성능 우수
ArrayList vs. LinkedList
| 특징 | ArrayList | LinkedList |
|---|---|---|
| 구조 | 배열 기반 | 이중 연결 리스트 기반 |
| 요소 접근 속도 | O(1) (인덱스 기반 접근) | O(n) (처음부터 순회 필요) |
| 삽입 삭제 속도 | O(n) (중간 삽입 / 삭제 시) | O(1) (처음 / 마지막 또는 노드 연결 변경 시) |
| 메모리 사용량 | 상대적으로 적음 | 각 노드마다 추가 메모리 필요 |
| 용도 | 읽기 작업이 많은 경우 | 삽입 / 삭제 작업이 많은 경우 |
(1) ArrayList
Arrays.asList
고정 크기의 리스트로 변환된 배열을 생성하며, 이는 원본 배열과 연결되어 java.util.Arrays.ArrayList 라는 내부 정적 클래스의 객체를 반환
- 특징
- 고정 크기 : 리스트의 크기 변경 불가 (get, set, sublist, isEmpty, size 가능)
- 원본 배열 기반 : 리스트와 원본 배열이 연결되어 리스트를 수정하면 원본 배열도 수정
- 제한된 List API : 요소 추가 및 삭제는 지원하지 않지만, 요소 변경은 가능
- 빠른 변환 : 배열을 빠르게 리스트로 변환하기에 적합
Array.asList : 고정 크기의 리스트로 변환된 배열 선언
import java.util.Arrays;
import java.util.List;
List<Integer> integer_list = Arrays.asList(1, 3, 2);get(index) : index 기반 조회
System.out.println(integer_list.get(0));set(index, value) : index 기반 수정
integer_list.set(2, 2);isEmpty() : 검사 (boolean 으로 표현)
System.out.println(integer_list.isEmpty());size() : 개수
System.out.println(integer_list.size());sublist(index, index) : 부분 요소 반환
(n, m)이면 n부터 m-1까지
System.out.println(integer_list.subList(0, 1));contains(value) : 포함 (boolean 으로 표현)
System.out.println(integer_list.contains(1));ArrayList<>
Java의 표준 라이브러리인 java.util.ArrayList 클래스의 인스턴스를 생성
이는 동적 크기의 배열 기반 리스트로 요소 추가 및 삭제 가능
- 특징
- 가변 크기 : 요소를 자유롭게 추가, 삭제 가능
- 구현 클래스 : java.util.ArrayList 의 객체
- 완전한 List API 지원 : 모든 리스트 관련 메서드 지원
- 독립적인 객체 : 원본 데이터와 별도로 동작
ArrayList<> : 동적 크기의 배열 기반 리스트 선언
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
List<Integer> integer_arraylist = new ArrayList<>(Arrays.asList(1, 2, 3));add(value) : 마지막 index로 새로운 value 추가
integer_arraylist.add(4);remove(index) : index 기반 삭제
integer_arraylist.remove(3);sort() : 나열
System.out.println(integer_arraylist.sort(Integer::compareTo));clear() : 리셋
integer_arraylist.clear();Arrays.asList vs. ArrayList<>
| 특징 | Arrays.asList | ArrayList<> |
|---|---|---|
| 크기 | 불가능 | 가능 |
| 원본 배열과 연계 | O | X |
| 사용 사례 | 배열을 리스트로 빠르게 변환해야할 경우 | 동적으로 요소 추가/삭제가 필요한 경우 |
| 클래스 | java.util.Arrays.ArrayList 내부 클래스 | java.util.ArrayList |
| 메모리 독립성 | 원본 배열과 연결 | 원본과 독립 |
ArrayList의 문제점
공간이 다 차거나, 요소 중간에 삽입할 때 기존의 배열을 복사해서 요소를 뒤로 일일히 이동시키는 작업이 필요
(2) LinkedList
java.util.LinkedList 클래스에서 제공하는 자료구조로, ArrayList와는 다르게 요소들을 노드로 연결하여 저장
List, Deque, Queue 인터페이스를 구현하므로 리스트, 스택, 큐의 역할을 수행
LinkedList<> : LinkedList 선언
import java.util.LinkedList;
LinkedList<String> cars = new LinkedList<String>();큐/스택 관련 메서드
- addFirst(E e) : 리스트의 맨 앞에 요소 추가
- addLast(E e) : 리스트의 맨 뒤에 요소 추가
- getFirst() : 맨 앞의 요소 접근
- getLast() : 맨 뒤의 요소 접근
- removeFirst() : 맨 앞의 요소 제거
- removeLast() : 맨 뒤의 요소 제거
- peekFirst() : 맨 앞의 요소 반환
- peekLast() : 맨 뒤의 요소 반환
3. Set 인터페이스 구현체 : HashSet, TreeSet (집합)
들어있는 값들이 모두 고유 (Unique) = 중복 값 불가
List 에서 Element 요소의 중복을 자체적으로 방지해주는 자료구조
- 구현체 종류
- HashSet
- TreeSet : 자동 정렬
HashSet vs. TreeSet
| 특징 | HashSet | TreeSet |
|---|---|---|
| 저장 순서 | X | O (기본 오름차순 정렬) |
| 시간 복잡도 | 평균 O(1) (검색, 삽입, 삭제) | O(log n) (검색, 삽입, 삭제) |
| 정렬 지원 | X | 지원 (기본: 오름차순, 사용자 정의 가능) |
| Null 허용 여부 | O (1개만) | X |
| 구현 구조 | 해시 기반 | Red-Black Tree 기반 |
| 사용 목적 | 빠른 데이터 저장 및 검색 시 | 정렬된 데이터가 필요 시 |
(1) HashSet
해시 기반의 집합으로, 요소를 저장하기 위해 HashMap을 내부적으로 사용
- 특징
- 저장 순서 미보장 : 요소 저장 순서 미보장
- 시간 복잡도 : 추가, 삭제, 검색 작업 시간 복잡도 = 평균 O(1) 즉, 빠른 성능
- Null 허용 : 하나의 null 값 허용
- 요소 비정렬 : 데이터 순서 비유지 / 비정렬
HashSet<> : 해시 기반의 집합 선언
import java.util.Arrays;
import java.util.List;
import java.util.Set;
Set<Integer> integer_set = new HashSet<>(Arrays.asList(1, 2, 3));add(value) : 새로운 value 추가
integer_set.add(4);remove(value) : value 기반 삭제
integer_set.remove(3);contains(value) : 포함 (boolean 으로 표현)
integer_set.contains(1);clear() : 리셋
integer_set.clear();isEmpty() : 검사 (boolean 으로 표현)
integer_set.isEmpty();size() : 개수
integer_set.size();(2) TreeSet
이진 탐색 트리인 Red-Black Tree를 기반으로 구현된 집합으로, 요소를 정렬된 상태로 유지
- 특징
- 정렬된 순서 유지 : 기본적으로 오름차순으로 정렬되지만, 사용자 정의 정렬 기준(Comparator)도 사용 가능
- 시간 복잡도 : 추가, 삭제, 검색 작업 시간 복잡도 = O(log n)
- Null 비허용 : null 값 저장 불가능
- 유일성 보장 : 중복 요소 비허용
- subSet : subSet 을 이용해 부분 요소 반환
TreeSet<> : Red-Black Tree 기반의 집합 선언
import java.util.TreeSet;
TreeSet<Integer> treeSet = new TreeSet<>();subSet(index, index) : 부분 요소 반환
(n, m)이면 n부터 m-1까지
System.out.println(treeSet.subSet(5, 15));4. Map 인터페이스 구현체 : HashMap, TreeMap, LinkedHashMap
Key - Value 기반 자료구조 = 데이터베이스와 유사 = Primary Key - Row(Data)
List 다음으로 많이 사용하는 자료구조로 시간복잡도를 낮추기 위해 공간복잡도를 Map 으로 늘려 활용
-
Entry :
entrySet() -
Key :
keySet(),containsKey() -
Value :
values(),containsValue() -
구현체 종류
- HashMap
- TreeMap : 자동 정렬
- LinkedHashMap : 키 순서 보장
HashMap vs. TreeMap vs. LinkedHashMap
| 특징 | HashMap | TreeMap | LinkedHashMap |
|---|---|---|---|
| 저장 순서 | X | Key 기준 정렬 | 삽입 순서 유지 |
| Null 허용 여부 | Key : 1개, Value : 여러 개 | Key : 비허용, Value : 여러 개 | Key : 1개, Value : 여러 개 |
| 시간 복잡도 | 평균 O(1) | O(log n) | 평균 O(1) |
| 구현 구조 | 해시 테이블 | Red-Black Tree | 해시 테이블 + 이중 연결 리스트 |
| 사용 목적 | 빠른 검색, 삽입, 삭제 | 정렬된 데이터 필요 | 삽입 순서 유지 필요 |
(1) HashMap
해시 테이블 기반의 Map 구현체로, 가장 일반적으로 사용
- 특징
- 저장 순서 미보장 : Key - Value 쌍의 삽입 순서를 미보장
- Null 허용
- Key : null 하나만 허용
- Value : 여러 개의 null 값 허용
- 빠른 성능 :
- 시간 복잡도 : 검색, 삽입, 삭제 시간 복잡도 = 평균 O(1) (충돌이 적은 경우)
- 비동기적 : 동시성 미지원 (멀티스레드 환경에서는 ConcurrentHashMap 사용 권장)
HashMap<> : 해시 테이블 기반의 Map 선언
import java.util.HashMap;
Map<Integer, Integer> integer_hashmap = new HashMap<>();put(Key, Value) : Key - Value 쌍 추가
integer_hashmap.put(1, 1);
integer_hashmap.put(2, 2);
integer_hashmap.put(3, 3);get(Key) : Key 값 기반 조회
integer_hashmap.get(3);set(Key, Value) : Key 값 기반 수정
integer_hashmap.replace(4, 5);remove(Key) : Key 값 기반 삭제
integer_hashmap.remove(3);containsKey(Key) or containsValue(Value) : 포함 (boolean 으로 표현)
System.out.println(integer_hashmap.containsKey(1));
System.out.println(integer_hashmap.containsValue(1));entrySet() or keySet() : Set 형태로 모든 Key - Value or Key 반환
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
Set<Map.Entry<Integer, Integer>> entrySet = integer_hashmap.entrySet();
for (Map.Entry<Integer, Integer> entry : entrySet) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
Set<Map.Entry<Integer, Integer>> keySet = integer_hashmap.entrySet();
Set<Integer> keys = integer_hashmap.keySet();
for (Integer key : keys) {
System.out.println("Key: " + key);
}values() : Collection 형태로 Value 반환
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
Collection<Integer> values = integer_hashmap.values();
for (Integer value : values) {
System.out.println("Value: " + value);
}values() 를 Collection 형태로 반환하는 이유
entrySet()과 keySet()에서는 Set 내부적으로 중복 검사를 위한 추가 작업 수행
Value 값은 중복이 가능하므로 values()는 중복을 허용하는 Collection 형태로 반환
clear() : 리셋
integer_hashmap.clear();isEmpty() : 검사
integer_hashmap.isEmpty();size() : 개수
integer_hashmap.size();(2) TreeMap
이진 탐색 트리인 Red-Black Tree를 기반으로 한 Map 구현체로, Key가 정렬된 상태를 유지
- 특징
- Key 정렬 : 기본적으로 오름차순으로 정렬되지만, 사용자 정의 정렬 기준(Comparator)도 사용 가능
- Key Null 비허용 : Key는 Null 비허용, Value는 여러 개의 null 값 허용
- 시간 복잡도 : 삽입, 삭제, 검색 = O(log n)
TreeMap<> : Red-Black Tree 기반의 Map 선언
import java.util.TreeMap;
Map<Integer, Integer> integer_treemap = new TreeMap<>();(3) LinkedHashMap
HashMap의 기능에 삽입 순서 유지 기능을 추가한 구현체
즉, 해시 테이블과 이중 연결 리스트를 기반
- 특징
- 순서 보장 : Key-Value 쌍의 삽입 순서를 유지
- Null 허용 :
- Key : null 하나만 허용
- Value : 여러 개의 null 값 허용
- 성능 : HashMap보다 느리지만 삽입 순서가 필요한 경우 적합
- 액세스 순서 정렬 옵션 : 생성자에서 설정하면 가장 최근에 접근한 Key-Value 순서로 정렬 가능
LinkedHashMap<> : 해시 테이블과 이중 연결 리스트 기반의 Map 선언
import java.util.LinkedHashMap;
LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
(와.. 정말 Chill하다..)