자료구조

실무에서 자주 사용하는 List, Set, Map 에 대해 간단히 정리해 본다.

List

순서가 있는 컬렉션으로 중복을 허용한다.

구현체 별 특징

특성	ArrayList	LinkedList	Vector
메모리구조	동적 배열	이중 연결 리스트	동적 배열
동기화 여부	비동기화	비동기화	동기화
접근 속도	O(1)	O(n)	O(1)
삽입/삭제 속도	O(n)	O(1)	O(n)
스레드 안정성	낮음	낮음	높음
용도	랜덤 접근, 읽기	빈번한 삽입, 삭제	멀티스레드 환경

Set

일반적으로는 순서가 없으며, 중복을 허용하지 않는다.

구현체 별 특징

특성	HashSet	LinkedHashSet	TreeSet
메모리 구조	해시 테이블	해시 테이블 + 연결 리스트	레드-블랙 트리
순서 유지	없음	삽입 순서 유지	정렬된 순서 유지
검색 속도	O(1)	O(1)	O(log n)
추가/삭제 속도	O(1)	O(1)	O(log n)
용도	순서가 필요 없는 고유 값 저장	순서가 필요한 고유 값 저장	정렬된 고유 값 저장

Map

Key와 Value의 쌍으로 이루어진 데이터 구조이며, Key는 유일하다.

구현체 별 특징

특성	HashMap	LinkedHashMap	TreeMap
메모리 구조	해시 테이블	해시 테이블 + 연결 리스트	레드-블랙 트리
순서 유지	없음	삽입 순서 유지	정렬된 순서 유지
Null 키 허용 여부	허용	허용	허용하지 않음
검색 속도	O(1)	O(1)	O(log n)
추가/삭제 속도	O(1)	O(1)	O(log n)
용도	순서 필요 없는 키-값 저장	순서가 필요한 키-값 저장	정렬된 키-값 저장

이진 트리 vs 레드-블랙 트리

이진 트리와 레드-블랙 트리는 둘 다 계층 구조로 데이터를 저장하는 자료구조이다. 하지만 트리의 균형을 유지하는 방식에서 큰 차이가 있다. 레드-블랙 트리는 균형을 유지하여 효율적인 탐색을 보장하지만, 일반 이진 트리는 그렇지 않다는 것이 가장 큰 차이점

이진 트리 (Binary Tree)

• 정의: 각 노드가 최대 두 개의 자식을 가지는 트리
• 특성:
  • 각 노드는 왼쪽 자식과 오른쪽 자식을 가질 수 있습니다.
  • 균형 유지 규칙 없음: 이진 트리는 특별한 균형 유지 규칙이 없기 때문에, 특정 구조에 따라 트리의 높이가 크게 증가할 수 있습니다.
  • 불균형 문제: 삽입이나 삭제가 많아지면 트리가 한쪽으로 치우치는 문제가 발생할 수 있으며, 이 경우 시간 복잡도가 최악의 경우 O(n) 에 가까워질 수 있습니다. 예를 들어, 값이 순서대로 삽입되면 한쪽으로 치우친 단순 연결 리스트와 같은 형태가 됩니다.

레드-블랙 트리

• 정의: 이진 탐색 트리(BST)이며, 특정 규칙에 따라 노드가 레드 또는 블랙으로 색칠되는 자기 균형 이진 트리
• 특성:
  • 균형 유지 규칙 존재: 레드-블랙 트리는 삽입, 삭제 시 트리의 균형을 유지하기 위한 엄격한 규칙을 따른다. (예: 루트 노드는 블랙이어야 하고, 레드 노드는 블랙 자식을 가져야 함)
  • 최대 높이 제한: 레드-블랙 트리는 규칙을 통해 트리의 높이가 제한되며, 최악의 경우에도 트리의 높이가 O(log n) 이내로 유지된다. 이로 인해 검색, 삽입, 삭제 등의 연산이 모두 O(log n) 의 시간 복잡도를 가진다.
  • 색상 및 회전 사용: 트리의 균형을 맞추기 위해 노드의 색상을 변경하거나, 트리의 특정 부분을 회전시키는 방법을 사용한다.