면접 준비 - 자료구조

배열

논리적 저장순서와 물리적 저장 순서가 같음.

인덱스로 원소에 접근할 수 있으므로 O(1)의 시간으로 접근가능.

삽입, 삭제의 경우 원소를 한칸씩 이동시켜야 하므로 O(n).

 

 

linkedlist

자기 자신다음에 어떤 원소인지만 저장하기 때문에 삭제와 삽입을 O(1)에 해결.

탐색하기 위해 모든 원소를 다 돌아야 하기 때문에 O(n)

 

 

스택 vs 큐

스택은 LIFO의 특성을 갖는 선형 자료구조. 먼저 들어간 원소가 나중에 나온다.

큐는 FIFO의 특성을 갖는 선형 자료구조. 먼저 들어간 원소가 먼저 나온다.

 

 

트리

계층적 관계를 표현하는 비선형 자료구조. 노드와 간선으로 구성.

 

 

이진 트리

각 노드가 2개 이하의 자식노드만 가지는 트리.

 

 

이진탐색 트리

노드에 저장된 키가 유일한 값을 가짐.

왼쪽 자식노드의 키가 부모의 키보다 작고, 오른쪽 자식노드의 키가 부모의 키보다 큼.

 

 

이진 힙

이진 힙을 통해우선순위 큐를 구현할 수 있음.

배열을 기반으로 한 완전 이진 트리. (위에서 아래, 왼쪽에서 오른쪽으로 차곡차곡 채워진 트리)

각 노드의 값이 자식들보다 크거나 같은 최대 힙, 작거나 같은 최소 힙.

 

 

해시 테이블

특정한 값을 해시 함수로 변형시켜 고유한 인덱스 값으로 설정하여 저장함.

 

 

 

* 참고

https://github.com/JaeYeopHan/Interview_Question_for_Beginner

https://dev-coco.tistory.com/category/%F0%9F%93%8CETC