Collection의 자료 구조

1. ArrayList(List) : ArrayList는 동적으로 크기를 조정하는 배열을 기반으로 합니다. fast random access를 제공하며 읽기가 많은 작업에 효율적입니다. 하지만 자료 중간이나 처음에 값을 삽입하거나 제거하면 속도가 느리다.

배열 기반

• 배열기반이기에 조회를 index로 하기때문에 빠르다. (조회에 1번이 걸린다)
• 삭제,삽입 그 자리를 다음 걸로 매꾸기 때문에 그 이후의 자료들의 인덱스를 전부 하나씩 땡겨오는 작업이 필요. (삭제, 삽입에 n번이 걸린다.)

2. LinkedList(List, Queue, Deque) : LinkedList는 각 값이 이전 값과 다음 값에 대한 참조를 갖는 링크된 리스트 입니다. 처음이나 끝에서 값을 빠르게 삽입하고 제거할 수 있지만 중간에 있는 값에 접근하려면 링크를 계속 타고 가야 하므로 속도가 느릴 수 있습니다.

노드 기반

• 자료는 값과 다음 번 자료의 주소를 저장하고 있습니다.
• 노드 기반이기에 하나씩 하나씩 주소를 타고 올라가야되서 조회가 오래 걸립니다.(n번)
• 삭제, 삽입시 다음 주소를 바꾸기만 하면 되기 때문에 쉽게 가능합니다.(1번)

3. Vector(List) : 벡터는 동적으로 크기를 조정하는 배열에 구축되므로 ArrayList와 유사합니다. 그러나 Vector는 Thread safe하게 설계된 구조. 그렇기 때문에 싱글 스레드에서 오버헤드가 일어날 수 있다.

4. HashSet(Set) : HashSet은 hashing function를 사용하여 값을 해당 버킷에 매핑하는 해시 테이블에 구축됩니다. HashSet은 평균적으로 일정한 시간 복잡도로 빠른 삽입, 삭제 및 검색 작업을 제공합니다. 그러나 값의 순서는 유지하지 않습니다.

5. LinkedHashSet(Set) : LinkedHashSet은 해시 테이블과 LinkedList의 조합입니다. HashSet과 동일한 성능을 제공하지만 값의 삽입 순서를 유지합니다.

6. TreeSet(Set) : TreeSet은 균형 잡힌 이진 검색 트리(일반적으로 Red-Black 트리)를 기반으로 합니다. 삽입, 삭제 및 검색 작업을 위해 값의 정렬된 순서와 로그 시간 복잡도를 제공합니다.

7. PriorityQueue(Queue) : PriorityQueue는 일반적인 Queue처럼 FIFO이 아닌 우선순위를 지정해서 받는다. 삽입 및 제거 작업을 위해 우선 순위가 가장 높고 로그 시간 복잡도가 높은 값에 대한 빠른 액세스를 제공합니다.

8. ArrayDeque(Deque) : ArrayDeque는 동적으로 크기가 조정되는 배열을 기반으로 합니다. 양쪽 끝에서 빠른 삽입 및 제거 작업을 제공하며 LinkedList보다 메모리 효율적입니다.

9. HashMap(Map) : HashMap은 HashSet과 유사한 해시 테이블에 구축됩니다. 평균 일정 시간 복잡도로 key-value에 대한 빠른 삽입, 삭제 및 검색 작업을 제공합니다. 그러나 값의 순서는 유지하지 않습니다.

10. LinkedHashMap(Map) : LinkedHashMap은 LinkedHashSet과 유사한 HashTable과 LinkedList 조합입니다. HashMap과 동일한 성능을 제공하지만 키-값 쌍의 삽입 순서를 유지합니다.

11. TreeMap(Map) : TreeMap은 TreeSet과 유사한 균형 잡힌 이진 검색 트리로 구축 됩니다. key-value의 정렬된 순서와 삽입, 삭제 및 검색 작업을 위한 로그 시간 복잡도를 제공합니다.