Interview Questions - Data Structures

1. Array와 Linked List의 차이에 대해 설명해주세요.

• 배열은 인덱스를 통해 요소에 접근이 가능하므로 시간 복잡도가 O(1)입니다. 반면에 연결 리스트는 순차적으로만 접근이 가능하므로 시간 복잡도가 O(N)입니다.
• 배열에서의 삽입과 삭제는 시간 복잡도가 O(N)인 반면에, 연결 리스트에서의 삽입과 삭제는 시간복잡도가 O(1)입니다.
• 배열을 저장할 때는 요소들이 인접한 메모리 위치에 연이어 저장되는 반면에, 연결 리스트를 저장할 때는 요소들이 떨어져 있어도 됩니다.
• 요소를 빈번이 접근할 경우 배열을 주로 사용하고, 요소를 앞에 추가해야 할 때 연결 리스트를 주로 사용합니다.

2. Stack과 Queue의 차이에 대해 설명해주세요.

• Stack은 나중에 들어온 요소가 먼저 나오는 자료 구조입니다. 반면에 Queue는 먼저 들어온 요소가 먼저 나오는 자료 구조입니다.
• Stack은 알고리즘에서는 DFS, 재귀에서 사용되고 실생활에서는 콜 스택, 실행 컨텍스트 스택에서 사용됩니다. Queue는 알고리즘에서는 BFS에서 사용되고 실생활에서는 이벤트 큐, 마이크로 테스크 큐에서 사용됩니다.

3. Binary Search Tree에 대해 설명해주세요.

• 부모 노드의 왼쪽 자식 노드가 부모 노드보다 항상 작은 값을 가지고 오른쪽 자식 노드가 부모 노드보다 항상 큰 값을 가지는 이진 트리입니다. 이진 탐색 노드는 요소의 탐색, 추가, 제거시 이진 탐색을 사용할 수 있습니다.
• 이진 탐색 트리는 탐색, 삽입, 삭제시 보통 O(logN) 시간복잡도를 가지며, 최악의 경우인 부모 노드가 자식 노드를 하나만 가질 때 O(N) 시간 복잡도를 가집니다.