자료구조 3장 연습문제 풀이

1. 배열과 연결리스트 기초

배열은 연속적인 메모리 공간에 데이터를 저장하는 구조로서, 데이터의 인덱스를 통해 빠르게 접근할 수 있다는 것이 가장 큰 장점이다. 예를 들어, 길이 10인 배열이 있다고 할 때 특정 인덱스에 저장된 값은 배열 이름과 인덱스를 조합하여 바로 읽을 수 있다. 이러한 특성은 배열이 데이터 접근에 있어서 O(1)의 시간 복잡도를 갖는다는 것을 의미한다. 따라서 정렬된 데이터를 즉시 검색하거나, 다양한 수학적 계산에 적합하다. 그러나 배열은 크기를 미리 정해야 하며, 크기를 변경하거나 데이터 삽입/삭제 시 상당한 시간이 소요된다. 특히, 중간에 데이터를 삽입하는 경우 모든 이후 데이터의 위치를 변경해야 하므로 평균적으로 O(n)의 비용이 발생한다. 연결리스트는 노드로 이루어진 구조로, 각 노드가 데이터와 다음 노드의 주소를 포함하는 방식이다. 이 구조는 크기 변경이 용이하며, 삽입과 삭제 연산이 배열에 비해 효율적이다. 연결리스트의 가장 큰 장점은 배열과 달리 크기 제한이 없고, 노드의 추가 또는 제거가 중간에서도 빠르게 이루어진다는 점이다. 예를 들어, 1000건의 Insert/Delete 요청이 처리되는 데이터 베이스에…