자료구조

JCF(Java Collection Framework)

Collection

1. Iterable/Iterator 인터페이스

Collection은 Iterable 인터페이스를 상속받고 있다.
Iterable 인터페이스는 내부에 Iterator 인터페이스를 반환하는 iterator() 메소드를 정의하고 있다.
Collection을 상속받아 List와 Set을 구현하는 클래스에서는 Iterable의 iterator() 메소드를 구현해야 한다.
Itr 내부 클래스를 만들고 implements Iterator 하여 실제 hasNext(), next() 메소드와 기타 필요한 메소드를 구현하여 return 한다.
Iterable :
ㄴ public Iterator iterator(); 메소드를 구현하게 강제하기 위한 인터페이스.

Iterator :
ㄴ public boolean hasNext(); / public E next(); 메소드를 구현하게 강제하기 위한 인터페이스

2. 저장 가능한 데이터

Collection은 기본 데이터형이 아닌, 참조 데이터형만 저장이 가능하다.
따라서 Collection에서의 데이터는 Object 타입의 객체로서 저장이 된다.

그렇다면 기본 데이터형은 어떻게 저장할까?

1. Wrapper 클래스 이용하여 Boxing

Integer num = new Integer(5);

2. Auto Boxing와 Auto Unboxing 사용

• 기본 데이터형을 직접 대입하여 저장해도 컴파일러가 자동으로 Wrapper 클래스로 변환해준다.

collection.add(11)

• 저장된 값을 얻어올 때에도 객체화된 데이터를 기본 데이터형으로 바로 얻어올 수 있다.

collection.get(n);

• AutoBoxing과 AutoUnBoxing 은 단지 기본형 타입과 상응하는 Wrapper class에만 일어나고 아닌 경우 컴파일 에러가 발생한다.

Double obj = 3.14;
int num1 = obj.intValue() ;   (O)
int num1 = obj;               (X)

List 인터페이스

• 동일한 데이터의 중복을 허용한다.
• 데이터 저장 순서가 유지된다.
• 힙(heap) 영역 내에서 List는 객체를 일렬로 늘어놓은 구조를 하고 있다.
• 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고
• 인덱스로 객체를 검색, 삭제할 수 있다.
  • 이 때 List 컬렉션은 객체 자체를 저장하여 인덱스를 부여하는 게 아니라, 해당하는 인덱스에 객체의 주소값을 참조하여 저장한다.
• List 컬렉션에서 공통적으로 사용가능한 추가, 검색, 삭제 메소드를 갖고있다.

Linkedlist

LinkedList 클래스는 List 및 Deque 인터페이스의 Doubly-linked list를 구현한 것이다.
또한 비동기식(non-synchronized)이므로 복수의 스레드가 동시에 LinkedList로 동작할 수 있다.
LinkedList 클래스는 내부적으로 연결 리스트를 이용하여 요소를 저장한다.

ArrayList

// 설정하고 싶은 초기 용량이 n이라고 했을 때에는 아래와 같이 선언한다.
List<T> list = new Arraylist<T>(n);

• Arraylist는 List 인터페이스의 구현 클래스
• 객체는 인덱스로 관리된다.
• ArrayList에 객체를 추가하면 객체가 인덱스로 관리되는 것이다.
• 일반 배열도 인덱스로 관리된다는 점은 같지만 초기화 시 그 크기가 고정되어야하고 사용 중에 크기를 변경할 수 없다

ArrayList의 단점은 저장소의 용량을 늘리는 과정에서 많은 시간이 소요된다는 점이다.

저장 공간 부족으로 ArrayList의 용량을 늘리게 되는 경우
1. 기존의 ArraList에 추가하는 것이 아닌, 확장된 크기의 ArrayList를 새로 생성하고
2. 그 새로 생성된 ArrayList에 기존의 ArrayList 값들을 복사해주는 과정을 거친다.
3. 기존의 ArrayList는 가비지 컬렉션에 의해 메모리에서 제거된다.
따라서 ArrayList에서 용량을 늘린다는 것은 새로운 배열 인스턴스의 생성과 기존 데이터의 복사가 필요한 번거로운 작업이 되는 것이다.

Vector

Vector는 Arraylist와 동일한 내부 구조를 가지고 있다.
Vector를 생성하기 위해서는 지정할 객체 타입을 타입 파라미터로 표기하고 기본 생성자를 호출하면 된다.

List<E> list = new Vector<E>(); 

ArrayList와 다르게, Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드가 실행을 할 수 있다.
따라서 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있다.

객체를 추가하고 삭제하고 가져오는 메소드는 ArrayList와 같다.

Stack

Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다. 스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 LIFO의 구조를 따른다. Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메서드를 5개만 상속받아 사용한다.

boolean empty() : 해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
E peek() : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
E pop() : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
E push(E item) : 해당 스택의 제일 상단에 전달된 요소를 삽입함.
int search(Object o) : 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.

Set 인터페이스

• 집합적인 개념의 Collection
• 순서의 의미가 없다.
• Data를 중복해서 포함할 수 없다.

HashSet

add() method : Data 삽입할 때 사용
remove() method : Data를 삭제할 때 사용
contains() method : Data의 포함여부를 알기 위해 사용
size() method : HashSet의 요소 개수를 얻어낼 때 사용
next() method : Data 추출할 때 사용

HashSet의 Data 추출은 Iterator을 이용하면 된다. Iterator는 Collection내의 모든 Data에 접근할 수 있는 특징이 있다.
그리고 Data의 마지막에 상관하지 않고 검색하기 위한 인터페이스이다.
Set의 Iterator() method로 Iterator를 얻어 낼 수 있으며, Iterator의 hasNext() method를 이용해서 Data 끝을 만날 때까지 next() method를 호출해서 Data를 추출할 수 있다.

Iterator<String iter = set.iterator();
while(iter.hasNext()) {
String temp = iter.next();

System.out.print(temp + ", ");
}

Map

자바에서 제공하는 HashMap과 Hashtable은 Map 인터페이스를 상속받아 구현되어 데이터를 키와 값으로 관리하는 자료구조이다.

큰 특징으로는 키(Key)가 데이터를 추출할 때 구분자로 활용하는 방식을 취하는데 이는 리스트 인터페이스와 같은 자료구조보다 탐색에 있어 더 높은 효율을 기대할 수 있다.

HashMap과 Hashtable의 차이점은 동기화와 반환값이다.

동기화

HashMap의 경우 동기화를 지원하지 않는다.
반면 다중 스레드 환경에서 Hashtable은 동기화를 지원하기 때문에 실행 환경에 따라 구분하여 사용하면 된다.
하지만 한 자바 관련 서적에 의하면 Vector의 상위호환(?)개념인 ArrayList의 사용을 권장하듯 새로운 버전인 HashMap을 활용하고 동기화가 필요한 시점에서는 Java 5부터 제공하는 ConcurrentHashMap을 사용하는 것이 더 좋은 방법이라 표현한다.
추가로 속도적인 측면에서도 구형이라 할 수 있는 Hashtable은 동기화 처리라는 비용때문에 HashMap에 비해 더 느리다고 한다.

반환값

HashMap은 저장된 요소들의 순회를 위해 Fail-Fast Iterator를 반환한다.(ConcurrentHashMap의 경우에는 Fail-Safe Iterator)
Hashtable은 같은 경우 Enumeration을 반환한다.
여기서 Enumeration과 Iterator는 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다.
Enumeration은 컬렉션 프레임워크 이전에 사용되던 인터페이스로 Iterator의 사용을 권장한다.
Iterator엔 remove() 메소드가 추가되었고 메소드 네이밍이 간략화되었다.
그리고 다른 스레드(lock된 상황에서)에서 해당 자료에 요소를 수정(삽입, 삭제, 수정 등)이 발생하면 ConcurrentModificationException을 발생시켜 일관성을 보장한다.
이를 Fail-Fast Iterator라 한다.

ConcurrentHashMap의 경우 Map의 복사본을 참조하는 Iterator를 반환하며 다시 반환받은 시점에 Map에 수정이 있을 경우 해당 Iterator는 반영되지 않는다. 고로 ConcurrentModificationException또한 발생하지 않는다. 이는 약한 일관성(Weakly Consistent)를 제공하지만 다중 스레드상황에서 해당 Map의 무결성(?)을 보장한다.

추가로 ListIterator가 있는데 이는 단방향만을 제공하는 Iterator의 기능을 향상시킨 것이다.

Iterator it = list.iterator();
it.next();

와 같이 사용된다면

ListIterator li = list.listIterator();
li.next();
li.previous();

와 같이 활용할 수 있다.
다만 List 인터페이스를 상속한 컬렉션에서만 사용가능하다.

Sorted

Set과 Map 인터페이스를 상속받아 정렬 기능이 추가된 SortedSet과 SortedMap 인터페이스가 된다. 그리고 이들은 각각 TreeSet 클래스와 TreeMap 클래스로 구성된다. TreeSet과 TreeMap은 Set과 Map의 기능을 가지고 있으면서 정렬 기능이 가미되었다는 것이 특징이다.

• Sorted를 지원하지 않는 클래스

  HashSet, HashMap

• Sorted를 지원하는 클래스

  TreeSet, TreeMap

TreeMap

Key와 Value로 Data를 관리
Key를 기준으로 오름차순으로 정렬된다.
Map 인터페이스를 상속한 SortedMap 인터페이스를 구현한 클래스

TreeSet

Set 인터페이스를 상속한 SortedSet 인터페이스를 구현한 클래스
데이터들이 자동으로 오름차순으로 정렬된다.

Comparator

TreeSet과 TreeMap은 사용자가 직접 정렬의 방식을 지정할 수 있다.
TreeSet과 TreeMap은 정렬을 위한 Comparator 인터페이스를 구현하면 된다.
TreeSet에 Data를 집어 넣으면 기본적으로 오름차순(Ascending) 정렬이 되지만 그것도 문자열이나 기본 데이터 타입과 같은 단순한 것에만 해당된다. 이에 사용자가 직접 비교법을 넣어주기 위해 사용하는 것이 Comparator 인터페이스이다.
Comparator의 구현 방법 : Comparator 내부에 compare() method를 구현하면 된다.

class Mycomparator<T> implements Comparator<T> {
public int compare(T o1, T o2) {
// 비교방법 구현
}

Comparator가 추가된 TreeSet의 생성

TreeSet<Score> tset = new TreeSet<Score>(new MyComparator<Score>());

Comparator가 추가된 TreeMap의 생성

TreeMap<Score, String> tset = new TreeMap<Score, String>(new MyComparator<Score>());

일반적인 정렬기능의 사용
HashSet이나 HashMap을 정렬 기능이 지원되는 TreeSet이나 TreeMap으로 변환해서 사용
HashSet을 이용한 TreeSet 생성

Set<String> set = new HashSet<String>();
...
TreeSet<String> ts = new TreeSet<String>();
ts.addAll(set);

HashMap을 이용한 TreeMap 생성

Map<String, Integer> map = new HashMap<String, Integer>();
...
Map<String, Integer> sortedMap = new TreeMap<String, Integer>();
sortedMap.putAll(map);

NavigableSet

SortedSet을 상속받은 인터페이스로 SortedSet에서 불편한 기능들을 추가적으로 정의한 인터페이스이다.

자세한 내용은 다음 링크 참조
https://www.daleseo.com/java-navigable-set/

출처

JCF - https://joooootopia.tistory.com/13
https://hyeonstorage.tistory.com/168 [개발이 하고 싶어요]
HashMap과 Hashtable 차이점 - https://odol87.tistory.com/3 [IT 인생]
Sorted - 출처: https://withwani.tistory.com/150 [박투(搏鬪)]