배열과 List, ArrayList, Dictionary 의 차이점

Reading time ~1 minute

nbcbanner

기술 면접 예상 질문 - 배열과 List, ArrayList, Dictionary 의 차이점을 설명해주세요.

C# 에서는 제네릭 타입의 List가 제공되며 내부적으로 동적 배열을 사용합니다.

제네릭 타입이기 때문에 박싱 언박싱이 팔요없어 타입 안정성과 성능상의 이점이 있습니다.

동적 배열을 사용하기 떄문에 리스트에 끝에서만 추가/삭제할 경우는 1의 시간복잡도

중간에 데이터를 insert하게 될 때 나머지의 데이터를 이동 시켜야 해 n의 시간 복잡도를 가져

insert가 많을 경우 비 효율적일 수 있습니다.

C# 에서 ArrayList는 제네릭이 도입되기 전 주로 사용하던 자료구조로 어떤 타입의 객체든 저장할 수 있습니다.

하지만 박싱 언박싱이 일어나 타입 안정성이 떨어지고 성능이 떨어질 수 있습니다.

Dictionary 자료구조는 Hashtable을 기반으로 Key-Value Pair의 형태로 데이터를 저장합니다.

Hashtable 기반이기 때문에 어떤 데이터를 검색할 때 1의 시간복잡도를 가집니다.

Hashtable은 buckets와 entries라는 두 개의 배열을 통해 동작합니다.

buckets는 해시코드를 기반으로 entries의 인덱스에 해당하는 값을 저장합니다.

entries에는 key와 value가 저장됩니다.

List는 동적 배열을 사용하는 자료구조로 제네릭을 제공합니다.

ArrayList는 어떤 타입의 객체등 저장할 수 있고 박싱 언방싱이 일어나 제네릭 리스트에 비해서

타입 안정성이 떨어지고 성능이 떨어질 수 있습니다.

Dictionary는 hashtable을 기반으로 key-value pair를 저장하는 자료구조 이며 키의 유일성을 보장합니다.

key를 기반으로 검색할 때 List에 비해서 성능 상의 이점이 있습니다.