[Java] 4. Collection (List, Map, Set)

Collection

Java Collection 에는 List, Set, Map, Stack, Queue 등의 인터페이스를 기준으로 여러 구현체가 존재합니다. Collection을 사용하는 이유는 다수의 데이터를 다루는데 표준화된 클래스들을 제공해서 데이터 구조를 직접 구현하지 않고도 편하게 사용할 수 있기 때문입니다. 또한 배열과는 다르게 객체를 보관하기 위한 공간을 미리 정하지 않아도 되기 때문에 상황에 따라 객체의 수를 동적으로 정할 수 있습니다. 이로써 프로그램의 공간적 효율성을 높일 수 있습니다.

Collection Interface

Map Interface

Collection 인터페이스가 Iterable 인터페이스를 상속하는 이유

Iterable 인터페이스 안에는 iterator 메소드가 추상 메소드로 선언 되어 있습니다. Iterable의 역할은 하위 클래스에서 iterator()메소드를 무조건 구현하게 하기 위함입니다.

List

- 배열을 사용하기 위해서는 크기를 정해야 하는데 상황에 따라 크기를 알 수 없는 경우가 많습니다. List는 이러한 배열의 한계를 극복하기   위한 자료구조 입니다.

 

# 배열과 리스트의 차이

배열(Array)	리스트(List)
인덱스를 가진 데이터 집합	인덱스 없이 순차적으로 저장된 데이터 집합
메모리에 연속적으로 저장	메모리에 분산되어 저장
랜덤 액세스 가능. 데이터 삽입/삭제가 어려움	랜덤 액세스 불가능. 데이터 삽입/삭제 쉬움

 

- List 인터페이스를 직접 @Override를 통해 사용자가 정의하여 사용할 수도 있습니다. 대표적인 구현체로는 ArrayList가 있으며 이는 Vector를 개선한 구현체입니다. 

 

- java.util.List는 java.util.Collection 인터페이스를 구현한 인터페이스 클래스입니다. List는 아래 클래스들 중 하나로 인스턴스 화 하여 사용할 수 있습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

List listA = new ArrayList();
List listB = new LinkedList();
List listC = new Vector();
List listD = new Stack();

 

1. ArrayList

- 내부적으로 배열을 이용하여 데이터를 관리합니다.

- ArrayList는 인덱스를 가지고 있어 데이터 검색에 적합하고 속도가 빠릅니다.

- resizable-array이면서 비동기입니다. 동기화가 필요할 때는 Collections.synchronizeList() 메소드를 통해 동기화가 보장되는 List를 반환 받아 사용합니다.

 

2. LinkedList

- Queue, Deque 속성과 메소드를 가지고 있고 비동기입니다.

- 내부적으로 연결 리스트를 이용하여 데이터를 관리합니다.

- 데이터 검색시에는 처음부터 노드를 순회하기 때문에 오래 걸립니다.

 

 

 

Map

- 대표적인 구현체로 HashMap이 존재합니다. 

- key/value의 구조로 이뤄져 있으며 구체적인 내용은 데이터 구조 부분의 hashtable과 일치합니다.

- key를 기준으로 중복된 값을 저장하지 않으며 순서를 보장하지 않습니다.

- key에 대해 순서를 보장하기 위해서는 LinkedHashMap을 사용합니다.

 

 

1. HashMap

- 배열의 인덱스를 해시 함수를 통해 계산합니다.

- 내부적으로 해시 값에 의해 어떤 버킷에 담길지 결정됩니다.

 

2. TreeMap

- HashMap과 다르게 red-black-tree 구조로 저장되어 있습니다.

 

3. LinkedHashMap

- 큰 흐름은 HashMap과 동일하지만 before, after Entry가 저장되어 순서를 보장할 수 있습니다.

 

4. SortedMap

- 오름차순의 키 순서로 유지하는 Map입니다.

- TreeMap이 SortedMap 인터페이스를 받아서 구현하고 있습니다.

 

 

 

Set

- 대표적인 구현체로 HashSet이 존재합니다.

- value에 대해서 중복된 값을 저장하지 않습니다.

- 순서를 보장하지 않으며 순서를 보장하기 위해선 LinkedHashSet을 사용합니다.

 

1. HashSet

- 내부적으로 Map을 사용하여 구현되어 있습니다.

- 필드로 HashMap을 가지고 있고 Set에 저장되는 데이터, 즉 value는 HashMap의 Key값으로 저장됩니다. 이 HashMap의 value에는 더미 값이 들어갑니다.

 

2. TreeSet

- 내부적으로 TreeMap을 사용하여 구현됐습니다.

- TreeMap이 근본이 되는 NavigableSet 인터페이스를 구현합니다.

- TreeSet은 이진탐색트리(BST : Binary Search Tree)의 형태로 데이터를 저장합니다. 그 중에서도 성능이 향상된 red-black-tree로 구현됐습니다.

 

3. SortedSet 

- 요소를 오름차순으로 유지하는 Set입니다.

- TreeSet이 SortedSet으로 구현됐습니다.

 

4. Queue

- 기본 컬렉션 작업 외에도 queue 자료구조 연산을 제공합니다.

- LinkedList, PriorityQueue가 Queue 인터페이스로 구현되어 있습니다.

 

5. Deque

- Double Ended queue의 약자로, 양쪽 끝에 요소 삽입 및 제거를 지원합니다.

- Deque 인터페이스로 구현된 클래스는 ArrayDeque가 있다.

 

 

 

 

 

 

 

 

참고링크

[자료 구조] Java Collections Framework(JCF)