TIL79-03 면접준비05: 배열, 링크드리스트

배열, 링크드리스트

• 배열과 링크드 리스트는 데이터를 저장하고 관리하는 자료 구조입니다. 배열은 정적으로 크기가 결정되고 검색이 빠르지만, 데이터 삽입/삭제가 어렵습니다. 반면 링크드 리스트는 동적으로 크기가 조정되고 데이터 삽입/삭제가 용이하지만 검색이 느립니다. 각 구조체는 특정한 상황에서 사용하기 적합합니다.

1. 구성 요소:

   • 배열은 데이터 요소를 메모리 상에 연속적으로 저장하는 것으로, 데이터 요소의 인덱스에 의해 직접적으로 액세스할 수 있습니다.
   • 링크드 리스트는 데이터 요소를 연속된 메모리 위치에 저장하는 것이 아니라, 각 요소가 자신의 다음 요소의 주소를 가리키는 포인터를 가지고 있는 형태로 저장합니다.

2. 크기:

   • 배열은 생성 시에 정적으로 크기를 할당합니다. 크기가 고정되어 있기 때문에 배열에 새로운 데이터를 추가하거나 제거하기 어렵습니다.
   • 링크드 리스트는 동적으로 크기가 조정되므로 새로운 데이터를 쉽게 추가하거나 제거할 수 있습니다.

3. 검색:

   • 배열은 인덱스를 사용하여 데이터를 직접 액세스하므로 검색이 매우 빠릅니다.
   • 링크드 리스트는 요소를 차례로 탐색해야 하므로 검색 속도가 느립니다.

4. 삽입/삭제:

   • 배열은 인덱스 위치에 직접 데이터를 삽입하거나 삭제할 수 있습니다. 그러나 데이터를 삽입하거나 삭제할 때, 해당 위치 이후의 모든 데이터를 이동시켜야 하므로 비용이 높습니다.
   • 링크드 리스트는 해당 위치의 포인터를 변경하여 데이터를 삽입하거나 삭제할 수 있으므로 비용이 덜합니다.
   • 따라서, 배열은 검색이나 인덱스 액세스에 적합하고, 링크드 리스트는 삽입 또는 삭제가 빈번하게 일어나는 경우에 유용합니다.