배열(Array)과 연결 리스트(Linked List)의 주요 차이점은 무엇이며, 각각 어떤 상황에서 더 효율적인 자료구조인지 구체적인 예를 들어 설명해주세요.

배열과 연결 리스트는 데이터를 저장하는 기본적인 자료구조이지만, 메모리 구조와 동작 방식에 큰 차이가 있습니다.

배열은 메모리에 연속적으로 할당되어 있어 인덱스를 통해 상수 시간(O(1))으로 데이터에 접근할 수 있다는 장점이 있습니다. 하지만 크기를 변경하기 어렵고, 중간에 데이터를 삽입하거나 삭제할 때 다른 요소들을 이동시켜야 하므로 비효율적입니다. 예를 들어, 정렬된 데이터를 유지해야 하는 경우, 새로운 데이터를 삽입할 때 배열은 삽입 위치 이후의 모든 데이터를 이동시켜야 합니다.

반면, 연결 리스트는 각 요소가 포인터를 통해 다음 요소를 가리키는 방식으로, 메모리에 비연속적으로 할당됩니다. 따라서 삽입/삭제 연산이 상수 시간(O(1))으로 가능하지만, 특정 위치의 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 하므로 탐색 시간이 오래 걸립니다(O(n)). 예를 들어, 빈번하게 데이터의 삽입/삭제가 일어나는 편집기나 플레이리스트 관리 시스템에 연결 리스트가 더 적합합니다.