[JAVA] Chapter 16. Collection Framework (2)

① List

- 데이터의 저장 순서를 유지한다.
- 중복된 데이터를 허용한다.

어떤 컬렉션 클래스가 나왔을 때 클래스 이름이 어떻게 끝나는지를 살피면 어떤 자료구조를 구현하고 있는지 알 수 있다.
List는 대표적으로 다음과 같은 method를 사용한다.

add(v) : v 추가
add(i, v) : i 번째에 위치에 v 추가
size() : 데이터의 개수 반환
remove(i) : i 번째 원소 삭제
set(i, v) : i 번째 값을 v로 수정
indexOf(v) : v의 인덱스 반환
contains(v) : v 값을 포함하는지 check
clear() : 공간과 데이터를 전부 지운다.
isEmpty() : 비었는지 확인

List 인터페이스를 구현하고 있는 대표적인 자료구조인 ArrayList와 LinkedList에 대해 살펴보자.

 

1) ArrayList
- import java.util.ArrayList;
- ArrayList<DataType> list = new ArrayList<DataType>()

ArrayList는 내부적으로 배열로 구현되어 있다. insert나 remove를 할 때 데이터를 다시 이동해 주어야 하지만, framework가 알아서 처리해 줄 뿐이므로 데이터를 추가하거나 삭제하는 것이 느리다.

 

2) LinkedList
- import java.util.LinkedList
- LinkedList<DataType> list = new LinkedList<DataType>();

LinkedList는 내부적으로 노드(Node)와 포인터(Pointer)로 구현되어 있다. 데이터를 추가하거나 삭제할 때 노드의 포인터를 바꾸면 되기 때문에 배열보다 빠르다. 하지만 탐색을 할 때 무조건 시작 노드부터 탐색을 시작해야 하기 때문에 검색이 느리다는 단점이 있다.

 

※ Collection을 사용하는 이유는 개발자가 저장소의 디자인을 잘못 설계했더라도, Class만 바꾸면 코드를 수정하지 않아도 되기 때문이다. 예를 들어 검색이 중요한 프로젝트라고 생각해서 배열을 사용했는데, 점점 삽입과 삭제가 많이 나온다고 가정하자. 그렇다면 자료구조를 LinkedList로 바꾸는 것이 좋을 텐데, 자바에서 제공해 주는 collection을 사용했다면 코드를 하나도 바꾸지 않아도 된다. Method가 동일하기 때문이다. (List끼리가 아니라 Queue나 Set으로 바꾸더라도 같은 클래스를 상속받았기 때문에 코드 대량 수정을 피할 수 있다.)
C에서는 LinkedList를 사용하려면 구조체로 만들어야 하는데 배열과 구조체를 핸들링하는 코드는 전혀 다르기 때문에 저장소를 바꾸는 순간 코드를 완전히 수정해야 한다.

 

 

② Set

- 데이터의 저장 순서를 유지하지 않는다.
- 중복 데이터를 허용하지 않는다.

add(v) : v 추가
size() : 데이터의 개수 반환
hasNext() : 다음 원소가 있는지 check
next() : 다음 원소

Set은 데이터의 순서가 없기 때문에 for 문을 사용하지 못한다. 대신 while과 iterator를 사용하는데, List를 Set 클래스로 바꾸었을 때 Method 이름이 같아도 for 문으로 인해 에러가 발생할 수 있다. 따라서 Collection안에서 사용되는 반복문은 iterator를 사용하는 것이 권장된다. (자바의 23가지 디자인 패턴 중 iterator 패턴은 행위 패턴에 속한다.)

 

Set 인터페이스를 구현하고 있는 대표적인 자료구조인 HashSet과 TreeSet에 대해 살펴보자.

 

1) HashSet
- import java.util.HashSet
- HashSet<DataType> hashSet = new HashSet<DataType>();

HashSet은 해시 테이블을 기반으로 구현된 클래스이다.
삽입/삭제/탐색에 O(1)의 시간 복잡도를 가지지만 해시 충돌이 발생할 경우 성능이 저하된다.

 

2) TreeSet
- import java.util.TreeSet
- TreeSet<DataType> treeSet = new TreeSet<DataType>();

TreeSet은 이진 검색 트리를 기반으로 구현된 클래스이다. default가 오름차순으로 정렬된 상태를 유지하며 삽입/삭제/탐색에 O(logN)의 시간 복잡도를 가진다.

 

③ Map

앞서 말했듯이, Map은 Collection을 상속받지 않기 때문에 Method 이름이 다를 것을 추측할 수 있다. Map의 예시로는 HashMap이 있다.

put(k, v) : k(key)와 v(value)를 삽입
get(k) : key 값이 k인 value를 반환
remove(k) : key 값이 k인 k, v 쌍을 삭제

현업에서 꼭 한 번은 봤을 자료구조가 map인데, Map은 저장소를 저장하는 저장소로 사용되기 때문이다.

collection은 인스턴스만 저장하는데, collection도 클래스이기 때문에 클래스를 생성하면 인스턴스가 된다. 따라서 collection 안에 collection을 저장할 수 있다.

cellphone        [			]
semiconductor    [			]
tv               [			]

위와 같은 각각의 자료구조에 대해

    Key	    	 	   Value
[cellphone]        [			]
[semiconductor]    [			]
[tv]               [			]

위와 같이 map에 저장하여 사용한다.

추가로 spring에서는 map을 만든 적이 없어도 코드에 put이 나온다. 이는 spring 자체적으로 가장 바깥쪽이 map으로 되어 있기 때문이다.

 

④ Check Point
- 저장소를 선택할 때 시간 복잡도와 공간 복잡도를 고려하여 어떤 클래스를 선택할지 결정해야 한다.
- 자바에서 저장소를 collection을 사용하는 이유는 map을 제외한 다른 클래스끼리는 중간에 클래스를 바꾸어도 코드의 변화 없이 기능만 바꿀 수 있기 때문이다.
- Collection 클래스의 개수가 많기 때문에 공통적인 특징을 찾아 학습해야 한다.
- Collection에는 VO Class로 저장된 데이터들을 많이 저장한다.