= - = - = - = - = - = 자료 구조 (Data Structure) = - = - = - = - = - = -
List
ArrayList: 동적 가변 배열 비동기 방식이기 때문에 스레드에 안전하지 못하다. 그렇기 때문에 멀티 스레드 환경에서는 Collection.synchronizedList()를 사용한다. 동기화된 컬렉션은 멀티 스레드 환경에서 하나의 스레드가 요소를 안전하게 처리하도록 도와주지만, 전체 요소를 빠르게 처리하지는 못한다. 왜냐하면 스레드가 작업을 할 때 락이 발생하기 때문이다. (병렬 처리 불가) 자바에서는 멀티 스레드 환경에서 안전하면서도 스레드가 병렬적으로 작업을 처리할 수 있도록 java.util.concurrent 패키지에서 ConcurrentHashMap, ConcurrentLinkedQueue 를 제공한다. 이 구현체들은 부분(segment) 잠금을 사용하기 때문에 병렬적으로 작업 수행이 가능하다. ArrayList는 특정 인덱스에 객체를 삽입하면 전체가 요동치므로 삽입, 삭제가 빈번하면 LinkedList로
LinkedLIst: 이중 링크드 리스트 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결 담당.
Vector: (ArrayList와 비슷함) 오래된 자료구조, 호환성을 위해 남겨놓은 레거시 클래스이다. 동기화를 사용하지만 스레드가 안전하지 못하므로 사용하지 않는 것이 좋다. Collection.synchronizedList() 메소드와 함께 ArrayList를 사용하자.
Stack: (LIFO) Vector 를 상속하여 사용하는 LIFO 방식의 클래스 Stack 대신 Deque 를 사용하여 구현할 것을 권장함.
- Queue
Queue interface: (FIFO) (주로 LinkedList를 이용하여 구현한다) Deque 또는 Queue를 LinkedList처럼 노드 객체로 연결해서 관리하길 원한다면 LinkedList를 쓰면 되고, 오브젝트 배열로 사용하고 싶으면 ArrayDeque를 사용한다. 자바에서 지원하는 컬렉션에서 ‘일반적인 큐’를 사용하고자 한다면 LinkedList를 생성하여 Queue 선언.
Priority Queue: (우선 순위 큐) FIFO가 아닌 특정 우선 순위에 따라 우선 순위가 높은 요소가 먼저 삭제되는 자료구조. 디폴트로 낮은 숫자가 높은 우선 순위를 가진다. (단, 참조 타입일 경우 Compartor 또는 Comparable을 통해 정렬 방식을 구현해야함) null을 허용하지 않습니다.
Deque interface: Queue가 삽입과 삭제가 한 쪽에서만 가능하다면, Deque는 양쪽에서 삽입, 삭제가 가능한 자료구조 사용 방식에 따라 Stack이 될 수 있고 Queue가 될 수도 있다.
ArrayDeque: 사이즈 제한이 없는 가변 배열이며 null 비허용, 비동기 원형 큐 방식 Stack 목적으로 구현했을 때 기존의 Stack보다 빠르고, Queue 목적으로 구현했을 때 LinkedList보다 빠르다. Array는 LinkedList보다 cache-locality에 조금 더 친숙하다고 한다. (LinkedList는 다음 노드가 있는 곳으로 가려고 다른 간접적인 경로를 거쳐감) 또한 ArrayDeque는 다음 노드에 대한 추가 참조를 유지할 필요가 없으므로 LinkedList보다 메모리 효율적이라고 한다. 쉽게 말해서, Queue는 FIFO의 특성을 가지고 있다. 즉, 삽입은 큐의 맨 처음에, 삭제는 큐의 맨 마지막에 일어나기 때문에 중간에 삽입되거나 삭제되지 않습니다. 결국 삽입 삭제의 시간복잡도는 O(1)이므로 리스트와 별반 차이가 없기에 최적화가 잘되있는 배열이 좀더 빠릅니다.
- Set
Set: 말 그대로 집합을 뜻한다. 특징은 “데이터를 중복해서 저장할 수 없음”과 “입력 순서대로의 저장 순서를 보장하지 않는다 LinkedHashSet은 입력순서대로의 저장순서를 보장합니다. 하지만 데이터를 중복해서 저장할 수 없는 것은 같습니다. equals()메서드를 사용하여 들어온 값이 있는지 없는지 확인합니다.
LinkedHashSet: 앞에서 말했듯이 중복은 허용하지 않으면서 순서를 보장받고 싶을 경우 사용합니다. LinkedHashMap을 동해 구현되어 있습니다.
HashSet: 가장 기본적인 Set 컬렉션의 클래스. 해시 알고리즘을 사용하여 검색 속도가 빠르다는 장점 좀더 상세히 말하면 hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인 할 수 있다 즉, Hash 기능과 Set 컬렉션이 합쳐진 것이 HashSet입니다. 그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나이다. HashMap을 통해 구현되어 있습니다.
TreeSet: HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못합니다. 다만 TreeSet은 중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 사용합니다. 정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용합니다. (Tree 라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조입니다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것입니다.) TreeMap을 통해 구현되어 있습니다.
Map Map은 값을 키에 매핑하는 객체입니다. 특징으로는. 데이터의 순서를 보장하지 않습니다. 중복된 Key 값을 가질 수 없습니다. 최대 하나의 Key에 매핑될 수 있습니다. Key를 통해 Value에 바로 접근이 가능하므로 탐색이 빠릅니다. equals()메서드를 사용하여 두 키가 동일한지 다른지 확인합니다.
HashTable Map 인터페이스의 구현 클래스이며, 자바 초기 버전에 나온 레거시 클래스입니다. Key와 Value가 null이면 안되고, Vector처럼 대부분의 메소드가 동기화처리 되어있다는 특징이 있습니다. Key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인텍스로 사용하여 Value를 찾는 방식으로 동작합니다.
HashMap 정렬되지 않은 Map을 제공합니다. 하나의 null key와 다수의 null 값을 허용합니다. 순서에 신경쓰지 않는경우 다른 Map보다 빠르다는 장점이 있습니다. hashCode()를 구현하면 접근 성능이 더 좋아집니다. 동기화 되지 않고 null을 허용한다는 점을 제외하면 HashTable과 거의 동일합니다. (보완했다 생각하면됨) (싱글 스레드 환경에서 성능이 더 좋음 → 멀티 스레드 환경에선 ConcurrentHashMap을 사용)
LinkedHashMap LinkedHashSet과 같이 입력순서대로의 저장순서를 보장합니다. → 순서를 보장하는 LinkedList의 구조를 이용함 삽입 삭제는 HashMap보다 느리지만, 더 빠른 조회를 할 수 있습니다.
TreeMap 정렬된 Map을 제공합니다. Key를 기준으로 원하는 방식으로 정렬을 할 수 있따는 특징이 있습니다. 레드 블랙 트리로 구현이 되이있습니다. 디폴트로 낮은 숫자가 높은 우선순위를 가집니다. (단, 래퍼런스 타입일 경우 Compartor 또는 Comparable을 통해 정렬 방식을 구현해야함)