[C#] 자료구조 정리 표

자료구조	추천 사용 상황	접근	검색	삽입/삭제
Array	크기 변동 거의 없음, 인덱스 접근 속도 최우선, 캐시 효율 중요한 경우	O(1)	O(n)	O(n)
List<T>	범용, 순차/인덱스 접근이 잦고 크기 변동이 가끔 있는 경우	O(1)	O(n)	O(n)
Dictionary<TKey, TValue>	키 기반 빠른 검색 필요, 대량 데이터 매핑	-	O(1) 평균 O(n) 최악	O(1) 평균 O(n) 최악
Queue<T>	순서대로 처리(FIFO)	O(n)	O(n)	O(1) (양끝)
Stack<T>	마지막 데이터 우선 처리(LIFO)	O(n)	O(n)	O(1) (양끝)
HashSet<T>	포함 여부 체크, 중복 제거 필요	-	O(1) 평균O(n) 최악	O(1) 평균 O(n) 최악
LinkedList<T>	중간 삽입/삭제가 빈번, 데이터 크기 변동 많음	O(n)	O(n)	O(1) (노드 참조)

 

배열(Array)이 List<T>보다 나은 점

메모리 사용 효율

• List<T>는 capacity가 Count보다 클 수 있으므로, 실제 필요한 데이터보다 메모리를 더 차지할 수 있음.
• Array는 길이가 곧 데이터 개수이므로, 추가 메모리 낭비 없음.

GC 부하 감소

• List<T>가 capacity를 확장할 때마다 새 배열 할당 + 기존 데이터 복사 → GC 대상 생성.
• Array는 한 번 할당하면 크기 변동이 없으니, 재할당 없이 안정적.