자료구조 Collection - List, Set, Map
1. Collection
자바에서 컬렉션이란 데이터의 집합, 그룹을 의미한다.
JCF(Java Collections Framework)는 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미한다.
주요구현체
List, Set, Map
2. List
저장공간이 필요에 의해 자동으로 늘어난다.
입력순서 유지 O, 데이터의 중복 허용 O
| ArrayList | - 단방향 포인터 구조 - 데이터 순차적 접근 (조회에 용이하다) |
| LinkedList | - 양방향 포인터 구조 - 데이터 삽입, 삭제가 빠르다 - 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰인다. - Iterator를 사용한다. |
Iterator : 추출 전용 인터페이스
- 데이터를 추출하기 위한 데이터 임시 저장공간
- 주로 순서가 없는 자료구조의 값들을 추출할 때 사용
- 보통 hasNext()와 next() 메서드를 이용한 while 문으로 값을 추출한다.
LinkedList가 Iterator를 사용하는 이유
LinkedList 특성상 항상 처음부터 같은 경로를 반복적으로 지나면서 데이터의 위치를 검색해야하기 때문에 마지막으로 접근한 데이터를 기준으로 그 다음 데이터를 알아내는 것이 더 쉽다.
2. Set
입력순서 유지 X, 중복 허용 X
데이터에 null 입력 가능하나, 한 번만 저장하고 중복 저장을 허용하지 않음
인덱스가 따로 존재하지 않기 때문에 Iterator를 사용하여 조회
단순 집합의 개념으로 정렬하려면 별도의 처리가 필요하다.
| HashSet | - 입력 순서 보장 X, 데이터 중복 허용 X |
| LinkedHashSet | - 입력 순서 보장 O, 데이터 중복 허용 X |
| TreeSet | - (Default) 입력한 데이터의 크기가 비교 가능하면 오름차순으로 정렬되며, 데이터의 중복 허용 X - 입력하는 데이터가 사용자 정의 객체인 경우 Comparable을 구현하여 정렬 기준 설정 가능 |
3. Map
Key&Value 구조
Key는 입력 순서 유지 X, 중복 허용 X
Value는 중복 허용 O
인덱스가 따로 존재하지 않기 때문에 Iterator를 사용하여 조회
| HashSMap | - key에 대한 입력 순서 보장 X, 중복키 허용 X - key값에 null 허용 O |
| HashTable | - key에 대한 입력 순서 보장 X, 중복키 허용 X - key값에 null 허용 X - 동기화 O |
| LinkedHashMap | - Key에 대한 입력 순서 보장O, 중복 키 허용 X |
| TreeMap | - 레드-블랙 트리(Red-Black Tree)를 기반으로 Key&Value를 저장 - (Default) 입력한 key 데이터의 크기가 비교 가능하면 오름차순으로 정렬되며, 중복 Key 허용 X - 입력하는 데이터가 사용자 정의 객체인 경우 Comparable을 구현하여 정렬 기준 설정 가능 |
4. 그 외
List와 Set의 차이
List는 기본적으로 순서대로 데이터가 들어가며 중복을 허용한다.
Set은 순서가 보장되지 않고 중복을 허용하지 않는다.
List와 ArrayList 차이
List = 인터페이스
ArrayList = 클래스
ArrayList <Object> list = new ArrayList <>();
List <Object> list = new ArrayList <>();
List는 인터페이스이다. 즉, 다형성에 의해서 만약 list를 List 자료형으로 선언한 경우, 그 구현체를 ArrayList로도 구현할 수 있지만 LinkedList로 구현할 수도 있다.
List<Integer> list = new ArrayList<Integer>();
list = new LinkedList<Integer>(); // 요구사항 변경 등의 이유로 구현체가 바뀌어도 호환 가능
ArrayList는 클래스이다. ArrayList 역시 List 인터페이스를 구현하고 있기 때문에 List가 제공하는 기능들을 다 제공할 수 있으므로 List 선언 시 구현 인스턴스의 자료형으로 작성할 수 있다. 하지만, List와 다르게 ArrayList의 자료형으로 생성한 경우 LinkedList로 새롭게 구현체를 만들거나 형변환을 할 수는 없다.
따라서, List를 이용해서 ArrayList를 생성하는 것은 유연성 면에서 효과적이다.
여기서 Generic(제너릭)이라는 것을 사용한다.
Generic은 클래스 내부에서 지정하는 것이 아닌 외부에서 사용자에 의해 지정되는 것을 의미합니다.
한마디로 특정 타입을 미리 지정해주는 것이 아닌 필요에 의해 지정할 수 있도록 하는 일반(Generic) 타입입니다.
즉, 저런 인스턴스의 형 변환을 통해 내부 디테일과 메모리 함축에서 이점과 성능을 개선시킬 수 있습니다.
데이터의 용도에 따라 빠른 탐색을 위해서 ArrayList를 사용할 때도 있고, 삽입/삭제를 위해 LinkedList를 사용해야 하는 경우도 있습니다.데이터의 삽입이나 삭제가 필요한 상황에서 List로 선언한 인스턴스를 LinkedList로 바꾸게 되면 아무런 문제 없이 LinkedList의 장점을 취할 수 있습니다.
배열(Array)와 List 차이
| 크기할당 | 장/단점 | |
| Array | 객체 생성시 크기 할당 필수 (불변) | 장점 : 데이터 조회가 빠르다 단점 : 데이터 삽입/삭제가 느리다 |
| List | 필요에 의해 늘어나므로 크기 할당 필요 없다 (자바에서는 자동으로 1.5배씩 늘어남) |
장점 : 데이터 삽입/삭제가 빠르다 단점 : 데이터 조회가 느리다 |
참고
자바의 정석 - 남궁 성 저