[기술면접] 자료구조 2

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁

면접 리스트

배열과 리스트는 어떻게 다른가요?

배열은 같은 타입의 데이터를 모은 집합으로 메모리 공간에서 연속적인 공간을 할당받습니다. 런타임에 배열의 크기가 결정되며 랜덤접근을 통해 데이터를 접근하는데에 O(1)의 시간복잡도를 가져 접근이 많은 프로그램에 유용한 자료구조 입니다.

 

리스트는 같은 타입의 데이터를 모은 집합으로 배열과 동일하나 메모리 공간에서 연속적인 공간을 할당받지 않습니다. 리스트는 크기가 동적으로 할당할 수 있으며 순차적인 접근을 하기에 삽입, 삭제에는 O(1)의 시간복잡도를 가지지만 탐색에는 O(N)의 시간복잡도를 가집니다.

스택과 큐에 대해서 설명해주세요?

스택은 선형 자료 구조의 일종으로 나중에 들어간 원소가 먼저 나오는 LIFO 구조인 자료구조입니다. 재귀함수의 콜스택이나 방문 기록 등에 사용되고 있습니다.

큐는 선형 자료구조의 일종으로 먼저 들어간 원소가 먼저 나오는 FIFO 구조의 자료구조입니다. CPU 작업을 기다리는 프로세스나 캐시 등에 사용되고 있습니다.