[정리] 자료구조 정리

🔍 배열과 연결 리스트의 차이점은?

배열은 연속된 메모리 공간에 데이터를 저장하고, 인덱스를 통해 O(1) 시간 복잡도로 접근할 수 있습니다.

반면, 연결 리스트는 노드와 포인터로 구성된 자료구조로, 각 노드는 데이터를 저장하고 다음 노드를 가리키는 포인터를 갖습니다.

삽입과 삭제는 연결 리스트가 더 유리합니다.(특정 위치에서 O(1) 시간), 하지만 탐색 속도의 경우는 배열이 더 빠릅니다. 연결리트의 경우는 O(n)

🔍 배열과 리스트 중 어떤 경우에 무엇을 사용하는지?

데이터의 크기가 고정되어 있고, 임의 접근이 중요하다면 배열을 사용합니다. 반면, 데이터의 크기가 동적이고, 삽입/삭제가 빈번하다면 연결 리스트를 사용합니다.

🔍 배열의 크기를 동적으로 늘리는 방법은?

Java에서는 ArrayList 같은 클래스가 내부적으로 2배씩 크기를 증가시키는 방식(더블링)을 사용합니다. 새 배열을 생성한 후 기존 데이터를 복사합니다.

🔍 단일 연결 리스트와 이중 연결 리스트의 차이는 무엇인가요?

단일 연결 리스트의 각 노드는 다음 노드만 가리키고, 이중 연결 리스트의 각 노드는 이전 노드와 다음 노드를 모두 가리킵니다.

이중 연결 리스트는 양방향 탐색이 가능해 데이터 탐색과 삭제가 더 편하지만, 메모리를 더 많이 사용합니다.

🔍 원형 연결 리스트는 무엇인가요?

원형 연결 리스트는 마지막 노드가 다시 첫 번째 노드를 가리키는 구조입니다. 이러한 구조는 회전형 데이터(스케줄링)에서 유용하게 사용됩니다.

🔍 스택과 큐의 차이점은?

스택은 LIFO 구조로, 마지막에 삽입된 데이터가 먼저 나오는 자료구조입니다. 반면, 큐의 경우 FIFO로 먼저 삽입된 데이터가 먼저 나오는 자료구조입니다.

🔍 해시 테이블의 충돌을 해결하는 방법은?

체이닝

-> 동일한 해시 값을 가지는 데이터를 연결 리스트에 저장합니다.

 

개방 주소법

-> 충돌 시 다른 해시 버킷을 탐색해 데이터를 저장합니다.

-> 선형 탐사 : 충돌이 발생하면 다음 버킷으로 이동합니다.

-> 이차 탐사 : 더 멀리 떨어진 버킷으로 이동합니다.

-> 이중 해싱 : 해시 함수를 두 개 사용합니다.

🔍 해시 테이블의 시간 복잡도와 자바의 HashMap은 어떤 방식으로 충돌을 처리하나요?

평균적으로 삽입, 삭제, 탐색은 O(1)이지만 해시 충돌이 많으면 최악의 경우 O(n)이 될 수 있습니다.

 

Java의 HashMap은 체이닝 방식을 사용합니다. 일정 수준 이상의 충돌이 발생하면 연결 리스트를 트리로 변환해 성능을 최적화합니다.

🔍 이진 트리란 무엇이며, 이진 트리의 순화 방법을 설명하세요.

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.

전위 순회 : Root -> Left -> Right

중위 순회 : Left -> Root -> Right

후위 순회 : Left -> Right -> Root

 

🔍 이진 탐색 트리의 특징을 설명하세요

이진 탐색 트리의 각 노드는 왼쪽 자식노드가 부모 노드보다 작고, 오른쪽 자식 노드가 부모 노드보다 큽니다.

 

평균적으로 탐색, 삽입, 삭제의 시간 복잡도는 O(log n)입니다. 하지만 편향 트리가 되면 O(n)이 될 수 있습니다.

🔍 이진 탐색 트리가 편향되면 어떻게 되나요?

트리가 한쪽으로 치우쳐지면 연결 리스트와 같은 구조가 되어 성능이 O(n) 으로 떨어집니다. 이를 방지하기 위해 균형 트리(AVL, Red-Black Tree)를 사용합니다.